Single-machine rework rescheduling to minimize maximum waiting-times with fixed sequence of jobs and ready times

• We model a single machine rescheduling problem and analyze its complexity.
• We develop a pseudo-polynomial algorithm for a special case.
• A heuristic procedure is developed and its worst case performance is derived.
• Several structural properties of the problem are formally presented and utilized to optimally solve six instances.
• The numerical experiments show that the heuristic yield close to optimal solutions.

This paper studies a single machine rescheduling problem in which a set of newly arrived rework jobs must be inserted into an existing schedule. The original jobs have ready times, and the objective is to minimize the maximum waiting time of any job in the final schedule. The problem is demonstrated to be NP-hard. Properties of the optimal solution are developed, enabling the development of a pseudo-polynomial algorithm for a special case and a heuristic algorithm for a general problem. A heuristic procedure is developed, and its worst case performance is derived. Experimental results suggest that the heuristic yields optimal and close-to-optimal solutions to problems similar to those present in practice.