Title: An enhanced genetic algorithm for the distributed assembly permutation flowshop scheduling problem

Authors: Xin Zhang; Xiang-Tao Li; Ming-Hao Yin

Addresses: Department of Information Science and Technology, Northeast Normal University, Changchun, 130117, China ' Department of Information Science and Technology, Northeast Normal University, Changchun, 130117, China ' Department of Information Science and Technology, Northeast Normal University, Changchun, 130117, China

Abstract: The distributed assembly permutation flowshop scheduling problem (DAPFSP) is a new generalisation of the distributed permutation flowshop scheduling problem (DPFSP) and the assembly flowshop scheduling problem (AFSP), aiming to minimise makespan. This production mode is more complicated and competitive in the real production process and includes two phases: production and assembly. Firstly, the production is conducted in several identical factories, and the production in each factory can be considered to a permutation flowshop scheduling problem (PFSP) with multi-machines. Then, the jobs produced in the first stage are assembled into final products. An enhanced population-based meta-heuristic – genetic algorithm (GA) is proposed for this problem. A greedy mating pool is designed to select promising parents in the selection operation, and an effective crossover strategy is designed based on the local search for speeding up convergence. To enhance the exploitation capability, several different local search strategies are incorporated into the algorithm, which are based on two neighbourhood structures. The exhaustive experiment and statistical analysis show that the proposed algorithms outperform the existing algorithms.

Keywords: distributed assembly scheduling; permutation flowshop; meta-heuristic; genetic algorithm; crossover; local search.

DOI: 10.1504/IJBIC.2020.106443

International Journal of Bio-Inspired Computation, 2020 Vol.15 No.2, pp.113 - 124

Accepted: 12 Apr 2019
Published online: 07 Apr 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article