Reactive scheduling for a single machine: problem definition, analysis, and heuristic solution

In this paper we address one of the most commonly occurring dynamic scheduling problems—the machine-breakdown problem. After formally defining the problem we study how optimality of a schedule is continuously affected as breakdown time increases. Our approach is to solve the problem incrementally, i.e., a schedule is continuously revised during breakdown time to maintain optimal scheduling. Since a fully optimal revision algorithm could be too expensive computationally, we propose a heuristic approach which adjusts the order of jobs dynamically to achieve local optimality. Experiments show that this heuristic strategy results in optimal schedules most of the time at a very low cost.