求解零空闲置换流水车间调度问题的离散烟花算法

针对以最小化最大完工时间为目标的零空闲置换流水线调度问题,提出了一种带有局部搜索的离散烟花算法.首先,结合调度问题的置换特征,定义了基于工件序列的编码方式;其次,结合反转和交换等操作重新定义了爆炸算子和变异算子;再次,开发了基于插入邻域的局部搜索策略,以增强烟花算法的局部搜索能力;最后,采用实验设计探讨了关键参数对算法性能的影响.基于Taillard基准问题的对比分析结果表明:所提方法在寻优精度、稳定性等指标上优于标准烟花算法、离散萤火虫算法、离散蛙跳算法、离散粒子群算法和遗传算法,且不劣于结合变邻域搜索的粒子群优化、混合离散粒子群优化、杂草优化等算法.

A discrete fireworks algorithm for solving no-idle permutation flow shop problem

In this paper, a discrete fireworks algorithm enhanced with local search is proposed to solve the no-idle permutation flow shop scheduling problem with respect to makespan minimization. Firstly, according to the characteristic of permutation, a job sequence-based encoding scheme is employed; secondly, a novel discrete fireworks algorithm is developed by redefining the explosion and mutation operators; thirdly, to enhance the local search, an insertion based local search is incorporated into the discrete fireworks algorithm; furthermore, the effects of key parameters on searching performance are investigated. Numerical results on the Taillard benchmark instances demonstrate that the proposed algorithm is superior to the standard fireworks algorithm, discrete firefly algorithm, discrete shuffled frog leaping algorithm, discrete particle swarm optimization and genetic algorithm in terms of solution accuracy and stability; meanwhile, the proposed algorithm also achieves competitive performance against particle swarm optimization with variable neighbour search, hybrid discrete particle swarm optimization and invasive weed optimization algorithm.