  Rescheduling problems arise in a variety of situations where a previously
planned schedule needs to be adjusted to deal with unforeseen events. A common
problem is the arrival of new orders, i.e. jobs, which have to be integrated
into the schedule of the so-called old jobs. The maximum and total absolute
time deviations of the completion times of these jobs are modeled as a
disruption constraint to limit the change in the original schedule. Disruption
constraints affect the shape of an optimal schedule, particularly with respect
to the sequencing of old jobs and the insertion of idle time. We therefore give
a classification into idle and no-idle problems for a set of single-machine
rescheduling problems with different objective functions. We then prove the
complexity of five rescheduling problems that have been left open in the
literature.
