Many real-life applications involve systems that change dynamically over
time. Thus, throughout the continuous operation of such a system, it is required
to compute solutions for new problem instances, derived from previous instances.
Since the transition from one solution to another incurs some cost, a natural goal is
to have the solution for the new instance close to the original one (under a certain
distance measure).We study reoptimization problems arising in scheduling systems.
Formally, due to changes in the environment (out-of-order or newmachines,modified
jobs’ processing requirements, etc.), the schedule needs to be modified. That is, jobs
might be migrated from their current machine to a different one. Migrations are
associated with a cost – due to relocation overhead and machine set-up times. In
some systems, a migration is also associated with job extension. The goal is to find a
good modified schedule, with a low transition cost from the initial one.We consider
reoptimization with respect to the classical objectives of minimum makespan and
minimum total flow-time. We first prove that the reoptimization variants of both
problems are NP-hard, already for very restricted classes. We then develop and
present several heuristics for each objective, implement these heuristics, compare
their performance on various classes of instances and analyze the results.