An effective multi-stage evolutionary algorithm for distributed scheduling with splitting jobs in heterogeneous factories

Abstract

This article examines an alliance of heterogeneous factories operating as a production network, in which jobs can be divided into several sub-jobs and independently processed in distributed factories. This problem is considered as a distributed unrelated parallel machine scheduling with splitting jobs (DUPMSP/S). A mathematical model and an effective multi-stage evolutionary algorithm (EMSEA) are proposed, aiming to minimize the total tardiness and total cost of production and transportation. In the EMSEA, the optimization process is divided into three stages according to the population in each generation, and four problem-based initial methods and three knowledge-based local exploitation strategies are embedded to improve its performance. Extensive experiments are conducted to compare the EMSEA with four other algorithms and to compare the scheduling model with no splitting jobs. The results demonstrate that EMSEA is the most promising method in solving the DUPMSP/S, and the job splitting mode is effective.

KEYWORDS:

• Scheduling
• distributed parallel machine
• heterogeneous
• splitting jobs
• evolutionary algorithm

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

Instances of this study are openly available via the link: https://github.com/wshndxgx/DUPMSP-S.git.

Additional information

Funding

This work was supported by the National Key Research and Development Program of China [grant number 2020YFB1712100], the Foshan Technological Innovation Project [grant number 1920001000041] and the Postgraduate Scientific Research Innovation Project of Hunan Province [grant number CX20230386].