A modified memetic algorithm with multi-operation precise joint movement neighbourhood structure for the assembly job shop scheduling problem

Abstract

This paper presents an adaptive memetic algorithm based on a new neighbourhood structure (AMA) for solving the assembly job shop scheduling problem, with the aim of minimising the maximum completion time (makespan). To utilise the knowledge of problem, a theoretical analysis is conducted to explore the criteria for feasible and effective movement of operations under assembly constraints, and a multi-operation precise joint movement neighbourhood structure is proposed accordingly. In the AMA, to ensure the feasibility of solutions during the evolution process, a feasible encoding mechanism based on the constraint degree of operations is designed, a greedy active decoding method as well as feasible crossover operation based on independent operation chains are designed specifically for this encoding method. To avoid premature convergence of the population, a population update operator with diversity adaptive control is proposed. Finally, by comparing the results with five state-of-the-art algorithms, the superiority of AMA in terms of solution quality and stability is verified, particularly with the update of known optimal solutions for 11 instances.

KEYWORDS:

• Memetic algorithm
• assembly constraints
• multi-operation precise joint movement
• constraint degree of operations
• diversity control

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data used in this study are all obtained from publicly available literature, and all the relevant references have been cited in the references section.

Additional information

Funding

This work was supported by the National Natural Science foundation of China [grant numbers 71961029].

Notes on contributors

Zhiyong Ba

Zhiyong Ba received the bachelor's degree in Industrial Engineering from Xinjiang University, Urumqi, China, in 2016 and the M.S. degree in mechanical engineering from Xinjiang University, Urumqi, China, in 2019. He is currently pursuing the Doctor degree with the School of Mechanical engineering, Xinjiang University, Urumqi, China. His current research interest includes manufacturing systems intelligent optimisation and scheduling.

Yiping Yuan

Yiping Yuan received the M.S. degree in mechanical engineering from Xinjiang University, Urumqi, China, in 1994 and the Ph.D. degree in Mechanical Manufacturing and Automation from Shanghai University, Shanghai, China, in 2006. She is currently a Professor with the School of Mechanical engineering, Xinjiang University, Urumqi, China. She has published over 60 journal papers. She current research interests include intelligent system optimisation and control, and production scheduling.

Jinduo Liu

Jinduo Liu received the bachelor's degree in Mechanical Engineering from Xinjiang University, Urumqi, China, in 2016 and the Ph.D. degree in mechanical engineering from Xinjiang University, Urumqi, China, in 2021. She is currently a lecturer with the School of Mechanical engineering, Anhui Polytechnic University, Wuhu, China. She current research interests include manufacturing systems intelligent optimisation and scheduling.