求解无等待流水车间问题的若干算法

Some meta-heuristics for no-wait flow shop problem

提出了解决无等待流水车间问题的离散粒子群优化、离散差异进化、变邻域搜索和阈值接收算法。在离散粒子群优化和离散差异进化中,采用基于工件排列的编码,设计了新的个体生成公式。同时研究了基于串行结构、嵌入结构和协同结构的12种混合算法。仿真计算表明,混合算法具有较高的优化性能。

Discrete Particle Swarm Optimization （DPSO）, Discrete Differential Evolutions （DDE）, Variable Neighborhood Search （VNS） and Threshold Accepting （TA） were proposed for the no-wait flow shop problem with makespan criterion. Both DPSO and DDE adopted the natural encoding scheme based on job permutation and employed newly designed methods to produce new individual. To improve solution quality, 12 hybrid algorithms based on serial structure, embedded structure and collaborative structure were studied. Simulation results based on the well known benchmark suites in the literature showed that hybrid heuristics had better optimization performance.