We consider reoptimization problems arising in production
planning. Due to unexpected changes in the environment (out-of-order
or new machines, modified jobs’ processing requirements, etc.), the production
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. The
goal is to find a good modified schedule, which is as close as possible to
the initial one. We consider the objective of minimizing the total flow
time, denoted in standard scheduling notation by P|| Sum Cj .
We study two different problems: (i) achieving an optimal solution
using the minimal possible transition cost, and (ii) achieving the best
possible schedule using a given limited budget for the transition. We
present optimal algorithms for the first problem and for several classes
of instances for the second problem.