Premium
An effective algorithm for flexible assembly job‐shop scheduling with tight job constraints
Author(s) -
Lin Wenhui,
Deng Qianwang,
Han Wenwu,
Gong Guiliang,
Li Kexin
Publication year - 2022
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12767
Subject(s) - job shop scheduling , crossover , computer science , benchmark (surveying) , mathematical optimization , algorithm , scheduling (production processes) , job shop , job scheduler , encoding (memory) , decoding methods , taguchi methods , operator (biology) , genetic algorithm , flow shop scheduling , mathematics , artificial intelligence , schedule , cloud computing , machine learning , biochemistry , chemistry , geodesy , repressor , transcription factor , gene , geography , operating system
Thus far, the available works on the flexible assembly job‐shop scheduling problem (FAJSP) consider job processing and assembly separately. However, in some real production systems, if equipment is composed of thousands of jobs and assembled in many stages, some jobs and assemblies cannot be processed simultaneously. Therefore, this work proposes an FAJSP with tight job constraints (FAJSP‐JC) in which jobs and assemblies can be processed simultaneously, and each assembly is treated as an operation. A job constraint genetic algorithm (JCGA) is presented to solve the proposed FAJSP‐JC with the goal of minimizing the makespan. In the JCGA, a novel two‐dimensional encoding method (2D‐encoding) is designed to conveniently express the operating constraints and tight job constraints, and an effective decoding method is proposed to decode the 2D‐encoded information. Furthermore, a crossover operator and a mutation operator are designed to improve the computational efficiency and expand the solution space. Ten benchmark instances of the FAJSP‐JC are constructed to test the JCGA. The Taguchi method is used to obtain the best combination of the key parameters that are used in the JCGA. Computational experiments carried out confirm that the JCGA is able to easily obtain better solutions compared to the genetic algorithm (GA) with a division encoding method and the classical GA, demonstrating its superior performance over these algorithms in terms of both solution quality and computational efficiency.