A clustering-based modified variable neighborhood search algorithm for a dynamic job shop scheduling problem

The dynamic job shop scheduling (DJSS) problem occurs when some real-time events are taken into account in the ordinary job shop scheduling problem. Most researches about the DJSS problem have focused on methods in which the problem’s input data structure and their probable relationship are not considered in the optimization process while some useful information can be extracted from such data. In this paper, the variable neighborhood search (VNS) combined with the k-means algorithm as a modified VNS (MVNS) algorithm is proposed to address the DJSS problem. The k-means algorithm as a cluster analysis algorithm is used to place similar jobs according to their processing time into the same clusters. Jobs from different clusters are considered to have greater probability to be selected when an adjacent for a solution is made in an optimization process using the MVNS algorithm. To deal with the dynamic nature of the problem, an event-driven policy is also selected. Computational results obtained using the proposed method in comparison with VNS and other common algorithms illustrate better performance in a variety of shop floor conditions.