Memetic Algorithm With Meta-Lamarckian Learning and Simplex Search for Distributed Flexible Assembly Permutation Flowshop Scheduling Problem

Abstract

This paper studies a novel and practical distributed flexible assembly permutation flowshop scheduling problem with makespan criterion, which has attracted wide attention due to important applications in modern manufacturing. The problem integrates two machine environments of distributed production and flexible assembly, which can process and assemble the jobs into customized products. We first present a mixed integer linear programming model to characterize the problem essence and to solve small-size problems. Due to the NP-hard, we further propose an efficient memetic algorithm, which consists of a global exploration optimizer designed based on improved social spider optimization and two local exploitation optimizers designed based on meta-Lamarckian learning and simplex search, respectively. To implement the algorithm, a problem-specific encoding scheme is presented. Algorithmic parameters are calibrated by a design of experiments, and a comprehensive computational campaign is conducted to evaluate the performance of the mathematical model and algorithms. Statistical results show that their problem-solving abilities are effective, and especially the proposed memetic algorithm outperforms the existing algorithms significantly.

Keywords

• Distributed flowshop scheduling
• flexible assembly
• memetic algorithm
• meta-Lamarckian learning
• simplex search