The Just-In-Time Job-Shop Rescheduling with Rush Orders by Using a Meta-Heuristic Algorithm

In the real manufacturing system, rescheduling is inevitable because of rush orders. To improve the rush order inserting problem of rescheduling, this paper focuses on the just-in-time job-shop rescheduling problem (JIT JSRP), in which each job has its own due date and any earliness /tardiness leads to the penalty. A mixed integer programming model is established to minimize the weighted penalty cost of earliness/tardiness and the starting time deviations. The paper develops a hybrid tabu-variable neighborhood search (HTVNS) algorithm to solve the problem. Moreover, the adaptive shake operator selection algorithm and two improved N5 neighborhood structures are introduced to improve the efficiency of the algorithm. In numerical experiments, the improved algorithm is testified using 36 cases with different scales and arrival times of rush orders, and compared with classical meta-heuristic algorithms. The computational results show the effectiveness of the proposed improved algorithm.