In this chapter, we provide a panorama of the PSO-based memetic algorithm (MA) for traditional permutation flowshop scheduling problem (PFSP) and its several variants. In the proposed algorithm, the global exploration ability of PSO and the local refinement ability of simulated annealing (SA) are delicately integrated and balanced. Some specific techniques related to the nature of PFSP are introduced to further improve the effectiveness of PSO-based MA. The key features in the proposed algorithm are detailed as follows. First, to apply PSO in solving combinatorial optimization problems such as PFSP, we rely on the ranked-order value (ROV) rule that uses random key representation to transform the continuous position information to scheduling permutations. Second, NEH and NEH-based constructive heuristics are introduced to guarantee a proportion of initial particles to be of good qualities. Third, to avoid the premature convergence problem of PSO, an adaptive SA-based local search is proposed to strengthen the exploitation in an efficient way. Forth, for the variation of PFSP that considers distributed processing factories, single assembly factory, and no-wait constraint (DAPFSP-NW), we include an extra encoding layer to represent the factory dispatch; thus, the proposed SA-based MA can still be applied. Moreover, the corresponding heuristic-based initialization and the neighborhoods adopted for local search are redefined. Last but not the least, for the variation with stochastic processing time and assembling time, the technique of hypothesis test (HT) is integrated into PSO-based MA; therefore, the solutions generated in each iteration can be effectively compared in a statistical way. Our experimental results strongly indicate the superiority of the PSO-based MA for solving PFSP, DAPFSP-NW, and stochastic DAPFSPNW at the aspects of optimization quality and robustness.

Chapter Contents:

• Abstract
• 16.1 Introduction
• 16.2 Related work
• 16.2.1 Permutation flowshop scheduling problems
• 16.2.2 Particle swarm optimization
• 16.2.3 Memetic algorithm
• 16.3 Permutation flowshop scheduling problem
• 16.4 A unified particle swarm optimization-based memetic algorithms framework for scheduling
• 16.4.1 Solution representation and evaluation
• 16.4.2 Population initialization
• 16.4.3 PSO-based global search
• 16.4.4 Local search techniques
• 16.4.4.1 NEH-based local search
• 16.4.4.2 Meta-Lamarckian learning strategy guided SA-based local search
• 16.4.4.3 Pairwise-based local search
• 16.4.5 Particle swarm optimization-based memetic algorithms framework
• 16.5 Numerical test and comparisons
• 16.5.1 Experimental setup
• 16.5.2 Simulation and comparisons
• 16.5.2.1 Comparison of PSO-based MA and NEH heuristic
• 16.5.2.2 Comparison of variants of PSO based MA
• 16.5.2.3 Effects of parameters in PSO-based MA
• 16.6 PSO-based MA for no-wait distributed assembly permutation flowshop problem
• 16.6.1 Distributed assembly permutation flowshop problem with no-wait constraint
• 16.6.2 PSO-based MA for DAPFSP-NW
• 16.6.2.1 ROV-based solution representation
• 16.6.2.2 Compositive heuristic-based initialization
• 16.6.2.3 SA-based local search
• 16.6.2.4 Framework of PSO-based MA for no-wait DAPFSP
• 16.6.3 Experimental study
• 16.6.3.1 Experimental setup
• 16.6.3.2 Simulation results
• 16.7 PSO-based MA for stochastic distributed assembly permutation flowshop problem
• 16.7.1 Stochastic DAPFSP-NW
• 16.7.2 PM-HT for stochastic DAPFSP-NW
• 16.7.2.1 PSO-based global search with HT
• 16.7.2.2 SA-based local search combined with hypothesis test
• 16.7.2.3 PSO-based MA with HT (PM-HT)
• 16.7.3 Experimental study
• 16.7.3.1 Experimental setup
• 16.7.3.2 Simulation results
• 16.8 Conclusion
• Acknowledgments
• References

Inspec keywords: convergence; stochastic processes; assembling; flow shop scheduling; combinatorial mathematics; particle swarm optimisation; search problems; simulated annealing

Other keywords: stochastic processing time; assembling time; particle swarm optimization; scheduling permutations; memetic algorithms; premature convergence problem; hypothesis test; simulated annealing; global exploration ability; combinatorial optimization problems; statistical analysis; ranked-order value rule; planned distributed flowshops scheduling; optimization quality; SA-based local search

Subjects: Systems theory applications; Other topics in statistics; Production management; Optimisation; Statistics; Systems theory applications in industry; Optimisation techniques; Assembling