学位论文 > 优秀研究生学位论文题录展示

多目标排序中的几个结果

作　者: 冯琪
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 排序多目标多项式时间算法 NP-困难
分类号: O223
类　型: 硕士论文
年　份: 2005年
下　载: 87次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

第一章引言  8-14
第二章单机多代理排序问题  14-29
  §2．1 预备知识  14-16
  §2．2 复杂性的证明  16-27
  §2．3 其它的结果  27-29
参考文献  29-31
附录  31-32
结束语  32-33
致谢  33

多目标排序中的几个结果

内容摘要

全文目录

相似论文