论文部分内容阅读
本文对一些在线分批排序问题进行了研究,我们设计了在线算法,并进行了竞争比分析。在经典排序中,同一时刻机器只能最多加工一个工件,而对于分批排序的平行批(parallel batch)模型,批处理机器一批最多可以同时加工B个工件,这里B被称为批处理机器的容量。本文中的在线模型是工件实时到达(overtime)的,在每个工件到达之前,我们不知道它的任何信息。当它到达以后,它的信息便被完全知晓,我们需要决定是否开始加工或者是等待更多的信息,一且决策,将来不可更改。
本文主要由五个部分组成。首先,我们给出了组合优化和排序问题的一些概念,并对在线排序和分批排序问题的研究进行了综述。
第二章讨论加工时间有限制的在线单机分批排序问题,我们假设工件加工时间满足pj∈[p,(1+φ)p],这里p为参数,φ=(∫5-1)/2。目标分别是极小化最大完工时间和最终送达时间,这些问题的下界均为1.618,我们分别给出了最优算法。
第三章研究了m台同型批处理机上工件带运输时间的在线排序问题,目标为极小化最终送达时间。当所有工件加工时间相等时,我们对于容量无限和有限两种情形,都给出了最优在线算法。当工件加工时间为一般的情形时,对于机器容量无限的情形,当m=2或m=3时,我们分别给出了竞争比为2的在线算法;当m>4时我们给出了竞争比严格小于2的在线算法,当m趋于无穷时,竞争比趋近于1.5。
第四章研究了单台容量无限的批处理机上的在线排序间题,目标是极小化加权完工时间和。对于这个问题的一般情形,不存在竞争比小于2的在线算法。陈礴等人给出了一个10/3-competitive的算法。在此基础上,我们给出了一个在线算法,并证明了它的竞争比为3.236。当所有工件的加工时间都相等时,我们给出了一个1.618-competitive的算法,并证明了它是最优的。
第五章研究了单台容量无限的批处理机上带批运输在线排序问题。工件在批处理机上加工后需要用一台运输车辆运输到目的地,目标是极小化最终所有工件被送达日的地并且车辆返回的时间。对于加工时间都相等的情形,我们给出了下界。对运输车辆容量无限的情形,我们给出了最优在线算法;并对车辆容量有限的情形,我们给出了在线算法IHc和MIHc,并证明当p≥2T等情形时,我们的算法是最优的,这里p为加工时间,T为车辆一次运输与返回所需时间。对于加工时间一般的情形,问题的下界不小于1.618,当车辆容量无限时,我们给出了最优算法;当车辆容量有限时,我们给出了2-competitive的算法。
最后,我们对本文中研究的问题进行了总结与展望。