An effective two-stage memetic algorithm for the dynamic flexible job-shop scheduling problem with job inspection

The existing researches on flexible job shop scheduling problem (FJSP) mainly focus on the processing process of jobs and neglect the quality inspection of the completed jobs. However, the processing quality of the jobs is uncertain and the inspection results are dynamic, so that the job inspection is crucial to reduce the flow of unqualified jobs to the next manufacturing units or customers. Hence, a mathematical model is formulated for the dynamic flexible job shop scheduling problem with job inspection (FJSPI). An effective two-stage memetic algorithm (ETMA) is developed to solve the proposed FJSPI. In ETMA, a multi-neighborhood search operator (MSO) comprising four neighborhood structures are devised to accelerate the convergence of the algorithm, and a well-designed available gap rescheduling strategy (GIR) considering three cases is utilized to address the different inspection results. Extensive experiments demonstrate the superior performance of ETMA in solving the FJSPI.