【作者】 高洁；

【导师】 李文华；

【作者基本信息】 郑州大学 ， 运筹学与控制论， 2011， 硕士

【摘要】 列表在线排序是一类重要的现代排序模型.本文主要研究的是单机批容量有界的列表在线排序问题,口标函数为极小化工件的最大完工时间.所谓单机上的列表在线排序：工件是一个接一个的到来,在下一个工件到来之前,我们要对刚到来的这个工件做出安排,要么将其安排在已存在的一个非满批中,要么将其安排为一个新的非满批.每个批至多只能有b个工件.论文的主要内容如下：第一章简要介绍了排序问题的一些相关定义、记号及相关知识.在第二章中,我们考虑的是批容量为2的情形,用Graham等人(1979)引入的三参数法,该问题可表示为：1|online-list,p-batch,b=2|Cmax.我们先给出了该问题的一个下界1+a,这里α是方程α(1+α)2=1在((?)-1,1/2)内的一个正根.接着给出了一个竞争比为(?)/2的在线算法.最后,我们给出了一个猜想竞争比更好的在线算法.在第三章中,我们考虑的是批容量为3的情形,用Graham等人(1979)引入的三参数法,该问题可表示为：1|online-list,p-batch,b=3|Cmax.我们给出了一个下界1+α′,其中α′是方程(1+α’)(1+(α’)2)=2在(1/2,(?))内的一个正根.接着给出了一个竞争比为2的在线算法.最后,我们总结全文并指出了下一步要研究的问题.更多还原

【Abstract】 Online-list scheduling is an important modern scheduling. We study the problem of online-list scheduling jobs on a batch machine of finite capacity with the objective of minimizing the makespan. So called online-list scheduling on a bounded batch machine, the jobs are presented one by one, and we have to assign each job upon arrival to a scheduled batch before we see the next one. Each batch can accommodate up to b jobs. The paper is organized as follows.In chapter 1, we introduce some definitions, notations and basic information about scheduling.In chapter 2, we consider the problem of online-list scheduling jobs on a batch ma-chine of capacity 2 with the objective of minimizing the makespan, using the 3-parameter notation convention of Graham et al. (1979), the problem is denoted by 1|online-list, p-batch, b=2|Cmax. For the problem, we present a lower bound 1+α, where a is a positive solution of the equation a(1+α)2=1 in (1/2 - 1,1/2). And we give an algorithm with competitive ratio 1/5+1/2. Then, we design an on-line algorithm which may be better for the further research.In chapter 3, we consider the problem of online-list scheduling jobs on a batch ma-chine of capacity 3 with the objective of minimizing the makespan, using the 3-parameter notation convention of Graham et al. (1979), the problem is denoted by 1|online-list, p-batch, b=3|Cmax.For the problem, we present a lower bound 1+α’, whereα’ is a positive solution of the equation (1+α’)(1+(α’)2)=2 in (1/2,1/5-1/2)-And we give an algorithm with competitive ratio 2.Finally, we summarize the dissertation and put forward some problems which we will consider further.更多还原