零空闲置换流水车间总延误最小迭代贪婪算法

Iterative Greedy Algorithm for Minimizing Total Tardiness in No-Idle Permutation Flow Shop

研究以总延误时间为目标且具有释放时间约束的零空闲置换流水车间调度问题。基于贪婪选择和作业对交换,设计基本迭代贪婪算法IGA;结合先到先服务FCFS排产规则对初始解的构建进行改进,并提出作业对多次循环交换对邻域搜索进行优化,递进设计了3种迭代贪婪算法FIGA、MIGA、FMIGA。通过不同规模的数据实验和与对比算法的比较分析,验证了FMIGA算法的有效性。结果显示该算法不仅能提高解的质量,而且具有良好的稳定性,为求解具有释放时间的零空闲置换流水车间总延误问题提出了一种新方法。

In this paper,the no-idle permutation flow shop scheduling problem with total tardiness time as objective and release time constraint is studied.A basic iterative greedy algorithm IGA is designed based on greedy selection and job pair exchange;the construction of the initial solution was improved by combining the first-come-first-served FCFS scheduling rules,and the optimization of the neighborhood search was proposed for multiple cyclic switching,and three iterative greedy algorithms FIGA,MIGA and FMIGA were designed progressively.The effectiveness of FMIGA algorithm is verified by different scales of data experiments and comparison analysis with the comparison algorithm.The results show that the algorithm can not only improve the quality of the solution,but also has good stability.A new method is proposed for solving the total tardiness problem of no-idle permutation flow shop with release time.