机器带不可用约束的在线排序问题研究

In most research of online scheduling problems, machines are assumed available all the time generally. However, the processing machine may be broken down to need repair or maintenance for a period during which the machine can not process any job in real manufacturing. Recently, researchers introduce a new scheduling model named online scheduling with machine unavailability constraint. This scheduling model fits the real manufacturing very well and has broad application prospects and important research value. Based on the results of the scheduling problems with machine unavailability constraint, using the theory, methods and skills in combinatorial optimization, we will make a thorough study of online scheduling problems with machine unavailability constraint in this project. By analyzing the properties of the optimal solution, we provide online algorithms and lower bounds for the online scheduling problems with machine unavailability constraint and show the competitive ratios of the algorithms. Then, we will do some numerical simulation to test the algorithms. The results of this project not only enrich and develop the theory and algorithm of online scheduling problems, but also provide useful tools to study some problems in reality.

在大量在线排序问题的研究工作中，一般情况下都假设在线排序问题中的机器是一直可用的。但在现实生产中，机器可能因为维修、保养等因素而停下来，在这段时间内机器不能加工任何工件。近些年，研究者提出了一类新的在线排序模型，即机器带不可用约束的在线排序模型。这类排序模型与实际生产背景非常吻合，具有广阔的应用前景和重要的研究价值。本项目以机器带不可用约束的排序问题的研究成果为基础，借用经典在线排序问题的一些算法，结合机器带不可用约束的在线排序问题的特点，运用组合最优化中的理论、方法和技巧，对一些机器带不可用约束的在线排序问题进行深入地研究。通过分析最优解的性质，我们给出这些在线排序问题相应的在线算法和下界，并进行算法竞争比分析。然后，我们再做一些数值模拟计算来检验算法。本项目的研究结果不仅可以丰富和发展在线排序问题的理论和算法，而且可以为解决实际生产生活中的问题提供有力的工具。

在大量在线排序问题的研究工作中，一般情况下都假设在线排序问题中的机器是一直可用的。但在现实生产中，机器可能因为维修、保养等因素而停下来，在这段时间内机器不能加工任何工件。近些年，研究者提出了一类新的在线排序模型，即机器带不可用约束的在线排序模型。这类排序模型与实际生产背景非常吻合，具有广阔的应用前景和重要的研究价值。本项目以机器带不可用约束的排序问题的研究成果为基础，借用经典在线排序问题的一些算法，结合机器带不可用约束的在线排序问题的特点，运用组合最优化中的理论、方法和技巧，对一些机器带不可用约束的在线排序问题进行深入地研究。通过分析最优解的性质，我们给出这些在线排序问题相应的在线算法和下界，并进行算法竞争比分析。然后，我们再做一些数值模拟计算来检验算法。本项目已经发表SCI论文2篇，中文核心论文3篇，正在审稿中的论文2篇，还有部分成果正在整理之中。本项目的研究结果不仅可以丰富和发展机器排序问题的理论和算法，而且可以为解决实际生产加工，运输问题提供有力的理论指导。