两类复杂机器环境的现代排序研究

In modern scheduling, the machine environments are becoming more and more complicated, among which, the environment with machine non-availability periods and that with machine eligibility restrictions might be of most significance. This project mainly concerns scheduling in such two machine environments, where the primary focus is on the design and analysis of approximation algorithms and online algorithms. For scheduling with non-availability periods, we study either problems in parallel-machine environment or those to minimize the total (weighted) completion times. Problems with periodic, flexible or even random non-availability periods are considered. If jobs are resumable or there are crossover jobs, our interest is in their influence on design and analysis of algorithms. For scheduling with machine eligibility restrictions, the complexity and approximability of problems are studied, as well as the design of online algorithms and the competitive ratio analysis. Moreover, we aim to give optimal algorithms for both the online model when partial information of jobs is given in advance and the online model when jobs arrive over time. We also do some applied research for scheduling with machine eligibility restrictions. It should be emphasized that our research not only helps develop the scheduling theory, but also can be a technical support for its applications. Hence, this project is both theoretical and practical, and it must be a prospective and innovative research.

现代排序的发展趋势是机器的环境趋于复杂化，其中机器有禁用区间和机器带加工权限是两类典型情形，本项目主要研究这两类复杂机器环境的现代排序，核心内容是近似算法、在线算法的设计与分析．对有禁用区间的排序问题，重点研究机器环境为平行机或者目标函数为极小化（赋权）总完工时间的情形，研究禁用区间周期性出现、禁用区间可移动和随机禁用区间等模型，并分析工件可恢复、工件可跨越对算法设计和算法性能的影响．对带加工权限的排序问题，研究问题的计算复杂性和可近似性，研究在线算法的设计和竞争比的分析，特别是预知部分信息的（半）在线模型和工件实时到达的在线模型，考虑设计问题的最优算法．我们还将开展带加工权限排序的应用研究．对这些问题的研究一方面有益于排序理论的发展，另一方面也为排序到实际应用中的转化和推广提供技术支撑．因此本项目的研究既有理论价值，又有实际意义，是一项有创造性和前瞻性的研究工作．

基于现代排序研究复杂机器环境的趋势，本项目重点考虑了两类典型情形：机器有禁用区间的排序和机器带加工权限的排序，项目从问题的计算复杂性、算法设计与分析等方面对这两大类问题进行了深入研究。当两台平行机上有禁用区间、加工不可恢复、目标为极小化总完工时间时，分析了不同禁用区间分布下SPT算法的最坏情况性能比；当单台机上有一个操作禁用区间，即允许工件跨越禁用区间加工时，证明了极小化总完工时间的问题是一般NP-hard的，设计了不同于SPT的近似算法，并给出了算法最坏情况性能分析；当机器带有等级型加工权限、目标为极小化最大完工时间时，设计了工件可分割情形的在线算法，并基于线性规划对偶原理证明了算法的最优性；对三台机两个等级的可中断排序，分别设计了允许引入空闲和不允许引入空闲的在线算法，并证明了算法的竞争比；对两台机、工件加工时长落在区间[p, rp]的半在线排序，设计了对任意r都是最优的在线算法并给出了算法的参数竞争比。此外，项目还研究了混合车间作业排序、加工与运输协作排序等其他复杂机器环境的排序问题，取得了许多算法和复杂性方面的理论结果。本项目的这些研究都是当前国际上排序研究的热点问题，通过本项目研究不仅丰富了排序理论的研究内容，而且发展了近似算法、在线算法的设计方法和分析技巧，达到了项目的预期目标。