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

项目名称： 最小化加权完工时间和的在线排序研究

项目编号： No.11501171

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 马冉

作者单位： 河南理工大学

项目金额： 18万元

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

中文关键词： 排序；在线算法；竞争比；加权完工时间和

英文摘要： 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.

英文关键词： scheduling;online algorithms;competitive ratio;total weighted completion time