可及时下线的批处理在线排序研究

Online algorithm is a hot topic in the scheduling research. In this project we will study a new online scheduling problem: online scheduling on drop-line batch machines. In this model, several jobs can be processed in a batch as many as the batch capacity is not exceeded. All jobs in a batch have the same starting time. The completion time of a job is equal to the starting time of a batch, which contains the job, plus the job's processing time. The objective functions of the problems under research include: the maximum flow time of the jobs, the maximum delivery completion time of the jobs, and the total weighted completion time of the jobs. The scheduling models with family jobs and restarts are combined into our research to form an extensive research content. By studying the structure feature of the off-line optimal schedules and based on totally new theoretical tools in online scheduling, we seek for the online algorithms with better performance properties. For the online scheduling on drop-line batch machines, we will establish fundamental theoretical framework and obtain a series of innovative research achievements.

在线算法是排序论中的热点研究课题。本项目研究一类新型的在线排序模型：可及时下线的批处理在线排序。在该模型中，在批容量允许的情况下，多个工件可以放在一批中进行加工。同一批的工件具有相同的开工时间，但每一工件的完工时间等于该工件所在批的开工时间与其自身的加工时间之和。所研究问题的目标函数包括：工件的最大流程、工件的最大送货完成时间、工件的加权完工时间和等。本项目的研究还将与分组工件和允许重启等排序模型相结合形成更为广泛的研究内容。通过探讨离线最优排序的结构特征并以全新的在线排序理论工具为基础，寻求性能良好的在线算法；对可及时下线的批处理在线排序建立基本的理论构架并取得一系列创新性的研究成果。

在线算法是排序论中的热点研究课题。本项目主要研究了几类平行批处理机上的线排序问题。目标函数包括：最大完工时间，最大送货完成时间以及加权完工时间和等。对于可及时下线的平行批处理机上的在线排序问题，借助问题转化和实例归结的方法，我们最终设计出了与竞争比下界相吻合的最优在线算法。这一结果从理论上彻底地解决此问题，同时也推动了可及时下线的平行批处理机上的在线排序问题的后续研究。对于由一台传统单机和一台平行批处理机混合组成的在线排序问题，研究的重心主要集中在在线算法的设计方面。我们最终给出了竞争比1.809的性能较好的在线算法。这一结果对此问题最优在线算法的设计有很好的借鉴意义。对于工件具有单位长度的批允许重启的批有界平行批在线排序问题，当批容量等于2时，我们给出了竞争比为1.29的最好可能在线算法；当批容量等于3时，我们给出了竞争比为1.38的最好可能在线算法；当批容量大于3时，我们给出了竞争比为1.40的最好可能在线算法。这些结果丰富了文献中关于允许重启的批处理机上在线排序问题的理论研究。对于单机上目标函数为时间表长和加权完工时间和的折衷在线排序问题。我们提供了一个具有非支配竞争比的在线算法，彻底地解决了此问题。这一结果推动了折衷在线排序问题的后续研究。对于多台批有界平行批处理上最小化加权完工时间和的在线排序问题，我们给出了一个性能较好的在线算法，并通过数据实验验证了我们提供的在线算法是非常有效的。这一结果对此问题最优在线算法的设计有很好的借鉴意义。