On the identical parallel-machine rescheduling with job rework disruption

This paper investigates an issue of rescheduling on identical parallel machines where the original jobs have already been scheduled to minimize the total completion time, when a single set of jobs to be reworked re-arrives and creates a job rework disruption. Two conflicting rescheduling criteria are considered: the total completion time, as the measure of scheduling cost (efficiency); and the number of jobs assigned to different machines in the original schedule and newly generated schedule, as the measure of disruption cost (stability). Further, the rescheduling problem is defined as a bi-criteria scheduling problem. Two polynomial time algorithms are proposed to lexicographically optimize the two criteria. Besides, the set of all efficient schedules with respect to the two criteria can be also generated in polynomial time.