An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling Problem
Authors:
- 3 April 2015
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Vol. 46 (1) , 139-149
Abstract
In this paper, an estimation of distribution algorithm (EDA)-based memetic algorithm (MA) is proposed for solving the distributed assembly permutation flow-shop scheduling problem (DAPFSP) with the objective to minimize the maximum completion time. A novel bi-vector-based method is proposed to represent a solution for the DAPFSP. In the searching phase of the EDA-based MA (EDAMA), the EDA-based exploration and the local-search-based exploitation are incorporated within the MA framework. For the EDA-based exploration phase, a probability model is built to describe the probability distribution of superior solutions. Besides, a novel selective-enhancing sampling mechanism is proposed for generating new solutions by sampling the probability model. For the local-search-based exploitation phase, the critical path of the DAPFSP is analyzed to avoid invalid searching operators. Based on the analysis, a critical-path-based local search strategy is proposed to further improve the potential solutions obtained in the EDA-based searching phase. Moreover, the effect of parameter setting is investigated based on the Taguchi method of design-of-experiment. Suitable parameter values are suggested for instances with different scales. Finally, numerical simulations based on 1710 benchmark instances are carried out. The experimental results and comparisons with existing algorithms show the effectiveness of the EDAMA in solving the DAPFSP. In addition, the best-known solutions of 181 instances are updated by the EDAMA.Keywords
Funding Information
- National Key Basic Research and Development Program of China (2013CB329503)
- National Science Foundation of China (61174189)
- Doctoral Program Foundation of Institutions of Higher Education of China (20130002110057)
This publication has 43 references indexed in Scilit:
- An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machinesThe International Journal of Advanced Manufacturing Technology, 2013
- Improving Grammar Inference by a Memetic AlgorithmIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2012
- An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problemComputers & Operations Research, 2012
- A review on estimation of distribution algorithms in permutation-based combinatorial optimization problemsProgress in Artificial Intelligence, 2012
- A Memetic Algorithm for Periodic Capacitated Arc Routing ProblemIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2011
- Guidelines for developing effective Estimation of Distribution Algorithms in solving single machine scheduling problemsExpert Systems with Applications, 2010
- An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problemsComputers & Operations Research, 2009
- A Multiobjective Memetic Algorithm Based on Particle Swarm OptimizationIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007
- A Memetic Algorithm for VLSI FloorplanningIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007
- Estimation of Distribution Algorithms2002