An effective memetic algorithm for the distributed flowshop scheduling problem with an assemble machine
Authors:
- 17 March 2022
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 61 (6) , 1755-1770
Abstract
The distributed flowshop has been a hot topic in research in recent years. This paper considers a distributed permutation flowshop scheduling problem with an assemble machine, so-called the distributed assembly permutation flowshop scheduling problem (DAPFSP), with total tardiness criterion. We propose an effective memetic algorithm (EMA). Firstly, a constructive heuristic combining the well-known earliest due date rule and largest processing time rule is presented for producing a seed sequence. On this basis, an effective initialisation method is used to generate an initial population with a high level of quality and diversity. The EMA uses a new structure of a small iteration nested within a large iteration. Moreover, an improved crossover and mutation expand the solution space in a good direction. According to different operation situations and objects, we design four targeted and flexible local search methods. We evaluate the strategies of the EMA, compare and analyse it with seven efficient algorithms based on the 810 benchmark instances. The experimental results confirm the effectiveness and efficiency of the proposed EMA.Keywords
Funding Information
- National Science Foundation of China (61973203, 51575212)
- Shanghai Key Laboratory of Power Station Automation Technology
This publication has 38 references indexed in Scilit:
- Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup timesInternational Journal of Production Economics, 2015
- Multiobjective Local Search Algorithm-Based Decomposition for Multiobjective Permutation Flow Shop Scheduling ProblemIEEE Transactions on Engineering Management, 2015
- An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling ProblemIEEE Transactions on Systems, Man, and Cybernetics: Systems, 2015
- A scatter search algorithm for the distributed permutation flowshop scheduling problemEuropean Journal of Operational Research, 2014
- The Distributed Assembly Permutation Flowshop Scheduling ProblemInternational Journal of Production Research, 2013
- Memetic algorithms and memetic computing optimization: A literature reviewSwarm and Evolutionary Computation, 2012
- A differential evolution algorithm for the no-idle flowshop scheduling problem with total tardiness criterionInternational Journal of Production Research, 2011
- A comprehensive review and evaluation of permutation flowshop heuristicsEuropean Journal of Operational Research, 2005
- An efficient constructive heuristic for flowtime minimisation in permutation flow shopsOmega, 2003
- Sequencing Jobs Through a Multi-Stage Process in the Minimum Total Time—A Quick Method of Obtaining a Near OptimumJournal of the Operational Research Society, 1965