Reoptimization of the Minimum Total Flow-Time Scheduling Problem

摘要

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‖Σ C_j. 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.