Application research of a new neighbourhood structure with adaptive genetic algorithm for job shop scheduling problem

Abstract

The job shop scheduling problem (JSSP) is to find the optimal jobs sequence to optimise one or more performance indicators and makespan is the most common optimisation target. In solving NP-hard problems such as JSSPs by genetic algorithm (GA), trapping in local extremum, low search efficiency and instability are often encountered, especially unable to find the optimisation direction. To restrain this condition, a new neighbourhood structure with adaptive GA was put forward. The crossover probability (Pc) and mutation probability (Pm) can be adjusted in nonlinear and adaptive based on the dispersion of the fitness of population in the evolution. The idle time before critical operations can be made full use of through the multi-operations combination and adjustment. To research the performance of the proposed method in solving JSSPs, a detailed application scheme was given out for the process of it. In the solving scheme, the chromosome active decoding algorithm with the objective function of maximum makespan was proposed. From the results of testing of 28 JSSP benchmark instances in 3 adaptive strategies and 3 neighbourhood strategies, the new neighbourhood structure with adaptive GA has been significant improvement in solution accuracy and convergence efficiency.

KEYWORDS:

• Job shop scheduling problem
• genetic algorithm
• adaptive method
• neighbourhood search
• makespan

Disclosure statement

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

Data availability statement

The data sets that support the findings of this study are available at http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt, reference [Hoorn, Jelke Van. 2018]. The data analysed during the present study are available from the corresponding author, Professor Zhong ([email protected]) on request.

Additional information

Funding

This work was supported by the Natural Science Foundation of Shandong Province (ZR202103070107).

Notes on contributors

Zhongyuan Liang

Zhongyuan Liang received the M.S degree in mechanical engineering from Shandong University of Science and Technology, Shandong, China, in 2015. Now he is studying the Ph.D. degree with college of mechanical and electronic engineering and Advanced Manufacturing Technology Centre. His current research interests include Intelligent decision, Optimisation algorithm research, Optimisation and numerical simulation, Job shop scheduling, Operational research.

Mei Liu

Mei Liu is a Senior Experimenter in the Experimental Centre of College of Mechanical and Electronic Engineering, Shandong University of Science and Technology. Her research interests include CAD/CAM, numerical control and robot, knowledge-based system, machine vision and deep learning, concurrent engineering and cloud manufacturing.

Peisi Zhong

Peisi Zhong received the Ph.D. degree in mechanical electronic engineering from Harbin Institute of Technology (HIT), Harbin, China, in 1999. He was a Postdoctoral Fellow at the National CIMS Engineering Research Centre, Department of Automation, Tsinghua University. His research interests include knowledge-based system, numerical control and robot, exoskeleton and mobile robot.

Chao Zhang

Chao Zhang received the M.S degree in Mechanical engineering from Shandong University of Science and Technology, Shandong, China, in 2015, where he is currently pursuing the Ph.D. degree in Mechanical Design manufacture and Automation Major with the College of mechanical and electronic engineering. His current research interests include Deep Reinforcement Learning and Robot Control.