用差异进化和变邻域搜索解决无等待流水线调度问题

Effective Heuristics Based on Differential Evolution and Variable Neighborhood Search for No-wait Flow Shop

提出了解决无等待流水线调度问题的离散差异进化(DDE)算法和变邻域搜索(VNS)算法。与标准差异进化(DE)算法不同,DDE算法采用了基于工序的编码和新的个体生成方法,因而能直接用于求解生产调度这类复杂问题;VNS算法采用多重移动邻域以提高性能。为了进一步提高求解质量,将DDE和VNS结合,得到三种混合算法:DDE—VNS、DDE_(VNS)和DDE&VNS。仿真试验表明:上述算法都是有效的,混合算法优于单一算法,VNS、DDE—VNS、DDE_(VNS)和DDE&VNS等4种算法优于国际上同类研究的最新成果。

The discrete differential evolution(DDE)and variable neighborhood search(VNS) were developed for the no-wait flow shop problem.In the DDE,the natural encoding scheme based on job permutation and newly designed methods to produce new individual were employed.While in the VNS,the multimoves were adpoted that consisted in performing several moves simultaneously in a single iteration of algorithm and allowed us to accelerate the convergence to good solutions.In order to improve solution quality,three hybrid heuristics(DDE-VNS,DDE_(VNS) and DDE&VNS)which combined DDE with VNS effectively were presented.Computational results based on the well known benchmark suites in the literature show that VNS,DDE-VNS,DDE_(VNS) and DDE&VNS produce slightly better results than that by the taboo search of Grabowski and Pempera's for the makespan cri- terion.