多目标排序中的几个结果

论文摘要

排序论具有广泛的实际应用背景,而多目标排序则是排序论的一个重要分支。在多目标排序中,我们有两个或两个以上的目标函数,目的是寻求一种排序使得所有的目标函数都达到最优或满意。 多代理（multi—agent）排序是多目标排序中的新的研究课题。在这个模型中,我们有m≥2个代理（客户）,分别具有工件集J1,J2,…,Jm。所有的工件必须在同一台机器上加工,而同一时刻机器只能加工一个工件。设代理i的目标函数为γ,1≤i≤m,则我们研究的问题包括以下几种形式。 1‖α1γ1+α2γ2+…+αmγm。在此问题中,我们寻求一种排序使得所有代理的目标函数加权和达到最优。该问题也记为1‖（γ1,γ2,…,γm）。 1‖γi≤Qi,1≤i≤m:在此问题中,我们寻求一种可行排序使得所有代理的目标函数均取得满意值。 1‖γ1∶γ2:此问题中,m=2,我们寻求一种排序使得在γ2取得满意值的条件下γ1取得最优值。 本文的工作是Baker,Smith,Agentis等人的研究工作的发展。研究的目标函数有Cmax,∑Cj,Lmax,maxWjCj,∑WjCj以及maxVj。本文的主要结果如下: 定理1 问题1‖∑Ci+maxWi′Ci′是多项式时间可解的,算法如下: Step 1 令u∶=n1,v∶=n2,F∶=0。 Step 2 如果u=0,则定义π（i）=Ji′,1≤i≤v,停止。 Step 3 如果u=0,则定义π（i）=Ji,1≤i≤u,令F∶=F+sum from 1≤i≤u t（i,0）,停止。 Step 4 若maxWv′t（u,v）>y,则定义π（u+v）=Ju,令u∶=u-1,F∶=F+t（u,v）;转Step 2。若maxWv′t（u,v）≤y,则定义π（u+v）=Jv′,令v∶=v-1;转Step 2。 定理2 问题1‖∑Ci:maxWi′Ci′是多项式时间可解的,算法如下: Step 1 令u∶=n1,v∶=n2。

论文目录

• 第一章 引言
• 第二章 单机多代理排序问题
• §2.1 预备知识
• §2.2 复杂性的证明
• §2.3 其它的结果
• 参考文献
• 附录
• 结束语
• 致谢