流水车间调度问题的一种启发式算法

A Heuristic Algorithm for Flowshop Scheduling Problem

在过去的20多年中，NEH算法一直被认为是解决以最小完工时间为目的的流水车间问题的最好启发武算法，该算法在实际的工件调度中也得到了广泛的应用。近年来，在对流水车间工件调度问题的研究过程中，也有不少的启发式算法被提出，但是，这些算法提出的大多是对NEH算法的继承和改进，算法性能的提升并不明显。在对流水车间调度问题充分分析和研究的基础上，提出了一种全新的启发式算法，该算法引入任意两个工件的相对位置对于完工时间的影响比较机制，有效提高了算法效率和性能。仿真实验表明，新算法的性能和稳定性均优于包括NEH算法在内的经典和常见的构造型启发式算法。

In this paper, we propose a new heuristic algorithm based on the analysis and research, the new method of introducing an evaluate mechanism of the relative position of any two jobs at the completion time, and the efficiency and performance has been improved. The result of simulation experiments shows that, our new heuristic algorithm has good performance, and the average quality and stability of scheduling sequences generated by the new method are significantly better than other heuristic algorithm which has the same complexity.