  We investigate a single machine rescheduling problem that arises from an
unexpected machine unavailability, after the given set of jobs has already been
scheduled to minimize the total weighted completion time. Such a disruption is
represented as an unavailable time interval and is revealed to the production
planner before any job is processed; the production planner wishes to
reschedule the jobs to minimize the alteration to the originally planned
schedule, which is measured as the maximum time deviation between the original
and the new schedules for all the jobs. The objective function in this
rescheduling problem is to minimize the sum of the total weighted completion
time and the weighted maximum time deviation, under the constraint that the
maximum time deviation is bounded above by a given value. That is, the maximum
time deviation is taken both as a constraint and as part of the objective
function. We present a pseudo-polynomial time exact algorithm and a fully
polynomial time approximation scheme, the latter of which is the best possible
given that the general problem is NP-hard.
