Single machine rescheduling for new orders with maximum lateness minimization

Rescheduling problems typically arise from production facilities that have to deal with incoming new orders for which it is not optimal to be simply scheduled at the end of an existing schedule of old jobs. A rescheduling of all jobs, old and new, is therefore allowed without disrupting too much the existing schedule. This kind of approach enables flexibility in the system while not disturbing too much the commitments with the customers. In this paper, we provide structural properties and a Branch & Memorize algorithm to solve a rescheduling problem on a single machine, where no idle times are allowed. To the authors knowledge, this is the first exact algorithm that solves a rescheduling problem with a constraint on the total absolute time-based disruption over all old jobs. The algorithm uses a fast heuristic to compute an initial upper bound and then exploits memorization techniques to cut dominated schedules. This solution method is shown to outperform an Integer Programming formulation solved by CPLEX and it is able to solve within 900 CPU seconds all instances with 10, 20, 30 jobs and most of those with 40 jobs.