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

单机在线继列分批排序与离线混合分批排序

作　者: 李旭海
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 继列批平行批竞争比在线不相容工件混合排序
分类号: O223
类　型: 硕士论文
年　份: 2011年
下　载: 9次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究单机上的在线继列分批和离线混合分批排序.在线继列分批排序中,一个工件的信息只有当它到达后才被释放出来.一台批处理机可以同时将多个工件作为一个继列批进行加工,每个工件都有它自己的安装时间,批的加工时间为这一批里的所有工件的加工时间之和,批安装时间为这一批里工件的最大的安装时间,目标是最小化时间表长.利用排序问题的三参数表示法,该问题可表示为l|s-batch,on-line,b=+∞,ri≤rj(?)si≥sj|Cmax.混合分批排序中：我们有两组工件(?)A和(?)B,分别称为A工件和B工件.这两组工件要在同一台可以对工件进行分批的机器上进行排序.但是,A工件和B工件不能放在同一批内进行加工.此外,A工件批为平行批,容量为b(A)；B工件批为继列批,容量为b(B),安装时间为s(B).利用排序问题的三参数表示法,该问题可表示为l|s-p-batch,s(B),(b(A),b(B))|γ.其中,γ∈{Cmax,Lmax,∑Cj,∑wjCj,fmax}.本文的主要内容如下：第一章介绍了排序问题的背景和本文所研究问题的相关发展,并给出了相关排序问题的术语和记号.第二章研究在线继列分批排序,给出排序问题l|s-batch,on-line,b=+∞,ri≤rj(?) si≥sj|Cmax的一个最好可能的在线算法,其竞争比为((?)5+1)/2.第三章研究单机两组工件继列分批与平行分批混合排序.主要结果如下：·排序问题l|s-p-batch,s(B),(∝,∝c)|Lmax在O(nAnBBn)时间可解.·排序问题l|s-p-batch,s(B),(∞,b(B))|∑Cj在O(nAnBn)时间可解.·排序问题l|s-p-batch,pj=1,s(B):(b(A),b(B))|∑wjCj在O(nAnBn)时间可解.·排序问题l|s-p-batch,s(B):(∞,b(B))|fmax可以在时间界为O(log(maxjfj(M))×(nlogM+nAnBn))内可解.其中,M是工件完工时间的一个上界.文章最后总结了全文内容并提出了下一步需要做的问题.

全文目录

摘要  4-5
Abstract  5-8
第一章引言  8-15
  §1.1 排序问题介绍  8-10
  §1.2 相关概念和记号  10-11
  §1.3 相关文献综述  11-13
  §1.4 本文主要结果  13-15
第二章单机上批容量无界的在线继列分批排序  15-27
  §2.1 预备知识  15-16
  §2.2 一个最好可能的在线算法  16-25
  §2.3 进一步讨论  25-27
第三章单机上两组不相容工件继列分批与平行分批混合排序  27-40
  §3.1 预备知识  27-29
  §3.2 排序问题1|s-p-batch,s(B),(∞,∞)|L_(max)  29-31
  §3.3 排序问题1|s-p-batch,s(B),(∞,b(B))|∑C_j  31-34
  §3.4 排序问题1|s-p-batch,p_j=1,s(B),(b(A),b(B))|∑w_jC_j  34-37
  §3.5 排序问题1|s-p-batch,s(B),(∞,b(B))f_(max)  37-40
后记  40-41
参考文献  41-45
致谢  45

单机在线继列分批排序与离线混合分批排序

内容摘要

全文目录

相似论文