A competitive memetic algorithm for the distributed two-stage assembly flow-shop scheduling problem

Abstract

This article addresses the distributed two-stage assembly flow-shop scheduling problem (DTSAFSP) with makespan minimisation criterion. A mixed integer linear programming model is presented, and a competitive memetic algorithm (CMA) is proposed. When designing the CMA, a simple encoding scheme is proposed to represent the factory assignment and the job processing sequence; and a ring-based neighbourhood structure is designed for competition and information sharing. Moreover, some knowledge-based local search operators are developed to enhance the exploitation ability. The influence of parameter setting on the CMA is investigated using the analysis of variance method. Extensive computational tests and comparisons are carried out, which demonstrate the effectiveness of the proposed CMA in solving the DTSAFSP.

Keywords:

• distributed two-stage assembly flow-shop scheduling
• memetic algorithm
• makespan

Additional information

Funding

This work was supported by the National Key Basic Research and Development Program of China [grant number 2013CB329503]; the National Science Fund for Distinguished Young Scholars of China; the National Science Foundation of China [grant number 61174189]; the Doctoral Program Foundation of Institutions of Higher Education of China [grant number 20130002110057].