在线排序问题研究中的位势理论

为了促进国内外在线排序问题方面的研究，对于文献中已有的关于时间在线排序模型，我们将进行深入的探讨和分析，建立一套完整的位势理论。借助于位势理论，我们将主要对批允许重启的在线排序、带有分组工件的多台平行批处理机在线排序以及一致机上的平行批在线排序等问题进行研究。在成果表现方面，我们不仅要建立一套应用性较强的位势理论，还要在在线算法竞争比下界的实例构造和在线算法的设计两方面寻求突破，力求在上述三种在线排序模型的研究过程中取得创新性的成果。

对于一个在线排序问题，我们一般通过在线算法给出排序方案，所谓最好可能的在线算法，指的是该算法的竞争比与该排序问题任意在线算法竞争比的下界相等。本项目“在线排序问题研究中的位势理论”旨在，针对一些排序问题，给出一套完善的理论体系，用来设计在线算法并分析该算法的竞争比。通过对一些已经给出最好可能在线算法的排序问题的研究，我们得出以下结论：在线算法设计的关键点在于确定工件或批的开工时刻，而最好可能的在线算法中，工件或批的开工时刻与该排序问题的竞争比下界的证明过程又有着紧密的联系。 我们按照如下方式来定义位势函数： 根据排序问题的目标函数，位势函数的变量可能由工件的到达时间、加工时间、运输时间、当前最大的开工时间等部分组成的，该函数的函数值代表的是每个等待加工的工件或批的较为理想的开工时刻。 根据位势函数的这一特点， 结合前期的一些研究工作，我们得到了一些创新性的研究成果，主要体现在以下几点：.　 (1) 对于工件属于个不同工件组的单台平行机最小化最大完工时间的在线排序问题，给出了一个最好可能的在线算法，其竞争比是与工件组个数有关的，从而彻底解决了该在线排序问题。.　 (2) 对具有个不相容工件组的台平行机在线排序模型，证明了该问题所有在线算法竞争比的下界约为1.618，并且给出了一个在线算法。当m=2或者同一组工件具有相同加工时间时，该算法是一个最好可能的在线算法；当m>2时，该算法的竞争比约为1.707。该结果将具有不相容工件族的平行批处理机最小化最大完工时间的在线排序模型推进到的情形，对该问题的一般情形下的彻底解决具有很好的借鉴意义。. (3) 对于带有运输时间的单台平行批处理机，目标函数是最小化最大运输时间的在线排序模型，给出了一个竞争比约为1.828的在线算法。该结果第一次给出了一般情形下一个竞争比小于2的在线算法，对进一步彻底解决该问题有很重要的借鉴意义。. 另外，对批容量不等的多台平行批处理机上的在线排序问题以及多目标排序问题，我们也给出了创新的研究结果。