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

具有前瞻区间的分批在线排序问题

作　者: 杨素芳
导　师: 李文华
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 在线排序不可相容的工件组最大完工时间平行分批竞争比
分类号: O223
类　型: 硕士论文
年　份: 2011年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

平行分批排序是一种重要的现代排序模型.在平行分批排序中,一台容量为b的机器可以把b个工件作为一批同时加工.同一批中的工件具有相同的开工时间和完工时间.每一批的加工时间和该批中最长工件的加工时间相同.在LKβ模型下,在时刻t,在线算法能预见到将在时间区间(t,t+β]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工.在本文中,我们主要研究了四个能够前瞻下一个时间区间内工件信息的单位长度工件的平行分批处理机的在线排序问题,包括单机和平行机,其中批容量是无界的.目标函数是使所有工件的最大完工时间最小.采用Graham等人(1979)提供的三参数表示法,这些问题分别表示为Pm|on-line,p-batch,b=∞,pj=1,LKβ|Cmax, 1|on-line,p-batch,b=∞,pj=1,LKβ,two families|Cmax, 1|on-line,p-batch,b=∞,pj=1,LKβ,families|Cmax, Pm|on-line,p-batch,b=∞,pj=1,LKβ,f=m|Cmax.下面我们具体地给出本文的主要结果.在第二章中,对于第一个排序问题Pm|on-line,p-batch,b=∞,pj=1,LKβ|Cmax,当β≥1/m时,我们给出了一个最优的在线算法H∞(β≥1/m).当0≤β<1/m时,我们首先证明了该问题的所有的在线算法的竞争比的下界是1+αm,其中0<α。<1是方程(1+αm)(m+1)=αm+2-β∑i=1m(1+αm)i的一个根,然后提供了一个竞争比为1+αm的最好可能的在线算法H∞(β<1/m).在第三章中,对于后三个带有不可相容的工件组的在线排序问题,我们分别证明了这些问题的竞争比的下界至少是1+α2,1+af和1+a,其中α2,af和α分别是方程2α22+(β+1)α2+β-2=0,f·αf2+(β+1)αf+β-f=0和α2+(β+1)α+β-1=0的一个正根.然后依次提供了最好可能的在线算法H2(β),Hf(β)和Hm(β).

全文目录

摘要  4-5
Abstract  5-8
第一章绪论  8-13
  §1.1 问题的背景  8-11
  §1.2 本文主要结果  11-13
第二章具有前瞻区间的分批在线排序问题  13-20
  §2.1 相关介绍  13-14
  §2.2 β≥1/m时的一个最优的在线算法  14-15
  §2.3 β  15-20
第三章具有前瞻区间的工件组在线排序问题  20-46
  §3.1 相关介绍  20-22
  §3.2 单机两个工件组的情形  22-32
  §3.3 单机多个工件组的情形  32-39
  §3.4 工件组个数和机器台数相等的情形  39-46
后记  46-47
参考文献  47-51
致谢  51

具有前瞻区间的分批在线排序问题

内容摘要

全文目录

相似论文