Rescheduling on a single machine with part-type dependent setup times and deadlines

The authors consider the problem of rescheduling a facility modeled as a single machine in the face of newly arrived jobs with part-type dependent setup times. The facility contains a number of jobs that have been assigned due dates and scheduled so as to meet them. They wish to insert the new jobs into the existing schedule in a manner that will minimize the disruption of the jobs in the system and minimize the total weighted completion time or the maximum completion time of the new jobs. The authors provide a polynomial-time algorithm for the maximum completion time problem, prove that the total weighted completion time problem is NP-hard in the strong sense and study several of its special cases. In particular, we show that the case with reverse-agreeable weights (of which the unit weight problem is a special case) can be solved in polynomial time when the number of part types is fixed. The authors also present two heuristics for the problem with arbitrary weights and develop data-dependent worst-case error bounds. Extensive computational experiments show that the heuristics consistently obtain near-optimal solutions in very reasonable CPU times.