有效的混合粒子群算法求解阻塞流水车间调度问题

摘要

针对以最小化完工时间为目标的阻塞流水车间调度问题，提出了一种混合粒子群算法进行求解。该算法将粒子群算法与迭代贪婪算法进行了结合。利用改进的迭代贪婪算法产生问题初始优化解，利用粒子群算法进行全局优化。针对粒子群算法易早熟收敛的特点，提出一种判断粒子停滞和粒子群早熟的方法，并在发现种群早熟后利用迭代贪婪算法的构造操作和毁坏操作对相关粒子进行变异，同时按照一定比例对最差的部分粒子进行重新初始化，以增加种群多样性。通过标准实例测试，验证了所提算法的有效性。%Aiming at the blocking flow shop scheduling problem with minimum makespan as objective, a Hybrid Particle Swarm Optimization (HPSO) algorithm which combined Particle Swarm Optimization (PSO) with Iterated Greedy (IG) algorithm was proposed. Improved IG algorithm was applied to get the initial optimized solution, while PSO was used for global optimization. Aiming at the premature convergence of PSO algorithm, a method to judge the particles' stagnation status and the particle swarm's premature convergence condition was put forward. The construction and deconstruction operation of IG algorithm was employed to mutate the correlative particles when discovering particle swarm prematurity, and to reinitialize the worst particles according to a certain proportion to maintain the diversity of particle swarm. The effectiveness of proposed algorithm was validated through a group of benchmark instances.