一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

摘要

This paper considers the scheduling problem of hybrid flow shop scheduling which the involves total number of tardy jobs.An improved simulated annealing algorithm is proposed for its solution.The initial seed solution is obtained by a heuristic algorithm,then optimizes the solution by the simulated annealing algorithm.New schedule can be obtained by selecting two jobs randomly and interchanging them.In conjunction with the first come first service rule and first available machine rule to construct a schedule for the overall stages.Numerical results indicate the algorithm is feasible and efficient.%针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法.该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进.通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度.实验仿真表明算法是可行有效的.