同类机上的若干排序问题研究

Scheduling theory is an important research direction in Operations Research and Combinatorial Optimization. Parallel machine scheduling is a classical research topic in scheduling theory. But most of the parallel machine scheduling problems studied in the literature are identical machine scheduling problems, and the uniform machine model (in which the speeds of machines are not identical) was rarely studied. This project studies four new uniform machine scheduling problems, which include the following contents: online batch scheduling, online scheduling with lookahead, off-line or online scheduling with rejection, and off-line scheduling under deterioration. We will also extend the researches by combining the above models with incompatible-job-family scheduling and delivery-time scheduling. The objective functions of the problems are to minimize the maximum weighted completion time, the total weighted completion time, and the maximum delivery completion time, etc. The goal of the project is to establish totally new theoretical tools; for off-line problems, present computational complexity analysis, design polynomial-time algorithms or polynomial-time approximation algorithms; for online problems, based on the analysis for the interrelationships between the time potentials and the optimization criteria, design online algorithms with good competitive ratios. The four problems include abundant scheduling models and have theoretically sufficient difficulty. The project will take deep research for these problems and achieve a series of innovation achievements.

排序论是运筹学与组合最优化领域的重要研究方向。平行机排序是排序论的经典研究课题，而文献中研究的平行机排序大都为同速机情形，对同类机(机器的速度不尽相同)模型的研究并不多见。本项目将研究四种新型同类机上的排序问题，包括：分批在线排序、具有前瞻性的半在线排序、工件可拒绝的离线和在线排序及工件具有退化效应的离线排序。同时我们还研究将上述模型与不相容工件组以及带有运输时间等结合得到的多种新模型。目标是最小化最大加权完工时间、总加权完工时间及最大运输完工时间等等。本项目的目的是建立全新有效的理论工具；对离线问题进行计算复杂性分析，并设计多项式时间算法或近似算法；对在线问题在分析时间位势与优化指标之间的内在联系的基础上设计具有良好竞争比的在线算法。上述问题包含了丰富的排序模型并具有相当的难度，而文献中几乎未见过对它们的研究。本项目将针对上述同类机上的排序模型进行深入研究，并获得一系列具有创新性的成果。

排序理论是运筹学与组合优化领域非常活跃的研究分支。文献中对于机器速度不同的同类机排序问题研究并不多见，而对该类问题的研究在理论和应用中均有深远意义。本项目研究了一系列同类机和恒同机上的若干新型排序问题，给出了有关在线模型的算法及其竞争比分析、离线模型的计算复杂性分析等等。受本项目资助共发表学术论文37篇，其中29篇论文发表在国际SCI期刊上。研究成果分类如下：在线算法研究发表论文15篇，主要是分批在线排序、工件具有退化效应的在线排序、工件可拒绝的在线排序及多种工件约束的在线排序；离线排序研究发表论文22篇，主要是双代理折衷排序、工件具有退化效应的排序、工件可拒绝的排序及算法的复杂性分析。本项目的代表性成果如下：（1）研究了两种速度的多台同类机上的最小化最大完工时间的平行批在线排序问题。按速度取值范围的不同讨论了竞争比的下界，并设计了最好可能的在线算法。（2）研究了医学检验中关于加权流程时间的分批排序问题。对于批容量无界情形，给出了权重任意时的最好可能在线算法；对于有界情形，给出权重取值1到2时最好可能的在线算法。（3）研究了工件带有序约束的多台恒同机上最小化最大完工时间的按时在线排序问题，给出了最好可能的在线算法。（4）研究了带有资源限制和学习效应的若干排序问题。对于单机和多台无关机的多种情形，设计多项式时间算法找到最优解决方案。（5）研究了一系列继列分批排序问题：批容量有界、最小化时间表长和最大费用的双指标折衷排序；工件有序约束、批容量为2、最小化最大延迟的单指标排序；工件有序约束、批容量无界、最小化时间表长和最大费用的双指标折衷排序。对于这些问题，要么多项式时间内可找到所有Pareto最优点，要么给出了强NP-困难性证明。