带有运输的单机平行分批在线排序问题

摘要

所谓排序，就是在一定的约束条件下分配时间资源去完成一些任务，使一个或多个目标达到最优。近年来，在线排序和分批排序是两个发展比较迅速的排序模型。在线排序是指工件信息在其到达之前是一无所知的，并且一旦工件被安排后就不允许再改变。平行分批排序是指机器可以同时加工多个工件，每批的加工时间是这批工件中所有工件加工时间的最大者。一旦批开始加工就不能被中断，直到该批被加工完毕。 本文中，我们研究了一种在线排序模型：带有运输的单机平行分批在线排序问题。在这里，我们有一台批处理机和充分多的车辆。有n个工件J1，J2，Jn，每个工件都分别有一个到达时间rj，加工时间pj和运输时间qj。工件的这些信息在其到达之后我们才能获得。在此问题中，每个工件需要在机器上加工，并且工件一旦完工就由车辆将其运送到目的地。我们的目标函数是最小化所有工件被运到目的地所花费的时间。用Graham等人[4]提出的三参数表示法，我们的问题可以表示为：1|on-line,rj，qj，B|Dmax，其中Dmax=max{Dj|Dj=Cj+qj，1≤j≤n}.本文的主要结果如下： (1)给出了排序模型1|on-line,rj，qj，B=∞|Dmax的一个竞争比不超过2的在线算法。 (2)给出了排序模型1|on-line,rj，qj，pj=p，prec,B=∞|Dmax一个竞争比为(√5+1)/2的在线算法。该在线算法是最好可能的。 (3)给出了排序模型1|on-line,rj，qj,B＜n|Dmax的一个竞争比不超过3的在线算法。 (4)给出了排序模型1|on-line,rj，pj，pj=p，B＜n|Dmax一个竞争比为(√5+1)/2的在线算法。该在线算法是最好可能的。 (5)给出了排序模型1|on-line,rj，qj，pj=p，prec,B＜n|Dmax一个竞争比不超过2的在线算法。

目录

郑重声明

摘要

第一章引言

第二章带有运输的单机平行分批在线排序问题

后记

参考文献

致谢