流水车间调度问题的启发式算法研究

针对以完工时间最小为目标的流水车间调度问题,对问题的定义进行了全新的推导和分析,从数学的角度进一步挖掘出问题的本质特征.在控制第一台机器和最后一个工件加工时间的基础上,尽量压缩每个工件在加工前的等待时间,以提高算法的实际效果.模拟实验的结果表明,新的启发式算法具有很好的性能,使用新算法计算得到的调度序列平均质量以及算法本身的稳定性方面均明显优于与之具有相当算法复杂度的其他启发式算法.

Research of Heuristic Algorithm for Flow Shop

For the flow shop scheduling problem which aims to minimize makespan, this paper gives a new derivation about its mathematical definition. A new heuristic method is proposed to shorten the waiting time of each job as much as possible on the basis of reducing the processing time of the first machine and last job. The result of simulation experiments shows that, the new heuristic algorithm has good performance, and the average quality and the stability of scheduling sequences generated by new method are significantly better than other heuristic algorithms with same complexity.