DOI: 10.3724/SP.J.1004.2013.02100

Acta Automatica Sinica (自动化学报) 2013/39:12 PP.2100-2110

Rescheduling with Release Time to Minimize Sum of Waiting Time Considering Waiting Constraint of Original Loads

In this paper, we consider the rescheduling problem to minimize the sum of waiting times of rework jobs and the original loads with release time on a single machine, and the waiting time of each original load is constrained by a value. The problem of rescheduling for reworks on a single machine (RRSM) is formulated and proved to be NP-hard. A dynamic insert heuristic (DIH) algorithm of polynomial-time is designed and proved with three properties. With respect to two special cases of the identical processing time of rework jobs or the machine without idle times in the original schedule, the DIH algorithm can obtain an optimal solution. A discrimination condition is proved for the optimal solution and effectiveness of the DIH algorithm is explained by cases with regard to general RRSM problems.

Key words:Rescheduling, single machine, rework, heuristic algorithm, waiting time

ReleaseDate:2014-07-21 17:04:35

Funds:National Science Foundation for Distin-guished Young Scholars of China (71325002, 61225012), National Natural Science Foundation of China (71071028, 70931001, 71021061, 71171040), the Specialized Research Fund of the Doctoral Program of Higher Education for the Priority Development Areas (20120042130003), Specialized Research Fund for the Doctoral Program of Higher Education (20110042110024), the Fundamental Research Funds for the Central Universities (N110204003, N120104001)