An Efficient Metaheuristic Algorithm for Job Shop Scheduling in a Dynamic Environment

Abstract

This paper proposes an Improved Multi-phase Particle Swarm Optimization (IMPPSO) to solve a Dynamic Job Shop Scheduling Problem (DJSSP) known as an non-deterministic polynomial-time hard (NP-hard) problem. A cellular neighbor network, a velocity reinitialization strategy, a randomly select sub-dimension strategy, and a constraint handling function are introduced in the IMPPSO. The IMPPSO is used to solve the Kundakcı and Kulak problem set and is compared with the original Multi-phase Particle Swarm Optimization (MPPSO) and Heuristic Kalman Algorithm (HKA). The results show that the IMPPSO has better global exploration capability and convergence. The IMPPSO has improved fitness for most of the benchmark instances of the Kundakcı and Kulak problem set, with an average improvement rate of 5.16% compared to the Genetic Algorithm-Mixed (GAM) and of 0.74% compared to HKA. The performance of the IMPPSO for solving real-world problems is verified by a case study. The high level of operational efficiency is also evaluated and demonstrated by proposing a simulation model capable of using the decision-making algorithm in a real-world environment.

Keywords

• metaheuristic algorithm
• improved Multi-phase Particle Swarm Optimization
• cellular neighbor network
• Dynamic Job Shop Scheduling
• simulation modelling