最小化加权完工时间和的在线排序研究

Online scheduling has been extensively applied in the areas of operations research and theoretical computer science. It is an important research direction motivated by practical problems in combinatorial optimization. This project studies online scheduling with the objective to minimize the total weighted completion time, which includes: the classical online scheduling on parallel machines, online scheduling with job rejection, online scheduling with job preemption, and online scheduling with job deterioration. In the online scheduling models studied in this project, the jobs arrive online over time, and the information of each job is unknown in advance until it is released. The theoretical difficullty of such problems originates from the lack of the complete information. Based on deep and refined investigation for the structure properties of the optimal (offline) schedules and the worst-case instances, we design online algorithms by taking the waiting strategy and the potential method with job priority into consideration, and analyze the competitive ratios by utilizing the techniques of instance reduction and pseudo-schedule. The project will engage in finding new ideas for designing online algorithms, developing new research methods to analyze the competitive ratio, and establishing a relatively complete theoretical system for online scheduling to minimize the total weighted completion time.

在线排序广泛地应用于运筹学和理论计算机科学，是问题驱动的组合最优化领域的重要研究方向。本项目研究目标为最小化加权完工时间和的在线排序，包括：经典平行机上的在线排序、工件可拒绝的在线排序、工件可中断的在线排序和工件加工时间恶化的在线排序。本项目研究的在线排序中，工件依时间在线到达，工件的信息只有在其到达后才能释放出来。此类问题的理论难度在于其完整信息的缺乏。在对最优解的结构性质以及最差实例的特点进行深入研究的基础上，我们利用工件赋有优先级的在线等待策略以及时间位势策略设计在线算法，并运用实例归结方法、虚拟排序方法等技巧综合分析算法的竞争比。本项目致力于寻求新的算法设计思想，发展新的竞争比分析方法，并在解决问题的基础上得到较为完整的最小化加权完工时间和的在线排序理论体系。

在线排序作为一种信息匮缺情况下的组合优化问题，广泛存在于生产制造、并行计算及公共服务等领域。本项目针对多个目标为最小化加权完工时间和的时间在线排序模型进行了研究，分析这类问题对应的在线算法由于缺乏完整信息而所面临的困境，挖掘相应算法所对应最差实例的特点与共性，展开以最差实例为中心的算法设计与分析。在分析问题竞争比下界时，用对手策略构造一系列特殊实例以导出较紧的下界；在设计算法时，构造基于工件优先级的在线等待策略,以保证其能兼顾到各类最差实例；在竞争分析时，通过调整任意实例的某些参数使其向最差实例可能的结构靠近，逐步将一个任意实例归结到结构整齐的实例，只需要对此结构整齐的实例进行竞争比分析即可。本项目不仅旨在为最小化总加权完工时间的各类平行机在线排序,以及加工时间有界的相应半在线问题,提出具有更好竞争性能的在线或半在线算法，还意在发展一种更具一般性与系统性的基于实例归结的竞争分析方法。