FLOW SHOP调度问题的启发式算法

Heuristic for flow shop scheduling problems

针对以总完工时间最小为目标的Flow Shop调度问题,基于全局插入和任务交换两种方法,提出一个启发式算法RP。RP算法的种子序列采用分组加权规则产生,并在调度改进阶段依据种子序列应用全局插入和任务交换方法对当前调度进行改进,以提高算法的搜索能力。模拟实验表明,在调度结果的平均质量、最好调度的获取能力和算法稳定性方面,RP算法优于目前最好的启发式算法RZ、WY、IX和FL。

A heuristics RP（ Rapid Pratical algorithm） is developed for flow shop with total flowtime minimization which is based on RZ-insertion and pair-wise exchange. The proposed is a constructive heuristic algorithm in which a seed was resulted by sorting jobs with weighted processing times and the current schedule was improved by RZ-insertion and pair-wise exchange. RP was compared with other four existing heuristic algorithms RZ（ described by Rajendran ＆ Ziegler）, WY（ developed by Woo ＆ Yim）, IX （described by Xiao-ping Li ＆ Cheng Wu） and FL（proposed by Framinan ＆ Leisten）. Computational resuits show that RP is the best in α （average relative percentage deviation）, β（standard deviation） and χ（number of best solutions obtained for a given size of problems） among the compared algorithms.