机器带使用限制的排序问题研究

In most research of 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 the manufacturing. In recent years, researchers introduce a new scheduling model named scheduling with machine availability constraint. This scheduling model is consistent with actual production background and has broad application prospects and important research value. Based on the results of the classic scheduling problems, by using the algorithms in classic scheduling, combining the features of the scheduling problems with machine availability constraint, using the theory, methods and skills in combinatorial optimization, we will make a thorough study of scheduling problems with machine availability constraint in this project. By analyzing the properties of the optimal solution, we provide algorithms for the scheduling problems with machine availability constraint and show the worst-case 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 of scheduling problems, but also provide powerful tools to study some problems in reality.

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

在大量排序问题的研究工作中，一般情况下假设排序问题中的机器是一直可用的。但在现实生产中，机器可能因为需要维修、保养等因素而停下来，在这段时间内机器不能加工任何工件。在供应链排序中，将运输车看成是加工机器，运输车在运输货物时，可能受到路线的约束，这也可以看成是机器 带使用限制的排序问题模型。这类机器带使用限制的排序模型与实际非常吻合，具有广阔的应用前景和重要的研究价值。本项目以经典排序问题的研究成果为基础，借用经典排序问题的一些算法，结合机器带使用限制的排序问题的特点，运用组合最优化中的理论、方法和机器，对一些机器带使用限制的排序问题进行了深入研究。本项目已经发表SCI论文一篇，正在审稿中的论文一篇，还有部分成果正在整理之中。本项目的研究结果不仅可以丰富和发展机器排序问题的理论和算法，而且可以为解决实际生产加工，运输中问题提供有力的理论指导。