An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers |
| |
Authors: | Bo Liu Ling Wang Yi-Hui Jin |
| |
Affiliation: | 1. Department of Automation, Tsinghua University, Beijing 100084, China;2. School of Computer Science, Liaocheng University, Liaocheng 252059, China |
| |
Abstract: | In this paper, an effective hybrid algorithm based on particle swarm optimization (HPSO) is proposed for permutation flow shop scheduling problem (PFSSP) with the limited buffers between consecutive machines to minimize the maximum completion time (i.e., makespan). First, a novel encoding scheme based on random key representation is developed, which converts the continuous position values of particles in PSO to job permutations. Second, an efficient population initialization based on the famous Nawaz–Enscore–Ham (NEH) heuristic is proposed to generate an initial population with certain quality and diversity. Third, a local search strategy based on the generalization of the block elimination properties, named block-based local search, is probabilistically applied to some good particles. Moreover, simulated annealing (SA) with multi-neighborhood guided by an adaptive meta-Lamarckian learning strategy is designed to prevent the premature convergence and concentrate computing effort on promising solutions. Simulation results and comparisons demonstrate the effectiveness of the proposed HPSO. Furthermore, the effects of some parameters are discussed. |
| |
Keywords: | Flow shop scheduling Limited buffers Hybrid algorithm Particle swarm optimization Adaptive meta-Lamarckian learning Simulated annealing |
本文献已被 ScienceDirect 等数据库收录! |
|