Sensitivity analysis for scheduling problems

This paper represents a first attempt at a systematic study of sensitivity analysis for scheduling problems. Because schedules contain both combinatorial and temporal structures, scheduling problems present unique issues for sensitivity analysis. Some of the issues that we discuss have not been considered before. Others, while studied before, have not been explored in the context of scheduling. The applicability of these issues is illustrated using well-known scheduling models. We provide fast methods to determine when a previously optimal schedule remains optimal. Other methods restore an optimal schedule after a parameter change. The value of studying the sensitivity of an optimal sequence instead of the sensitivity of an optimal schedule is demonstrated. We show that, for some problems, sensitivity analysis results depend on the positions of jobs with changed parameters. We identify scheduling problems where performing additional or different computations during optimization facilitates sensitivity analysis. To improve the robustness of an optimal schedule, selection among multiple optimal schedules is considered. We discuss which types of sensitivity analysis questions are intractable because the scheduling problem itself is intractable. We also study how heuristic error bounds vary when the data of a scheduling problem are continuously modified. Although we focus on scheduling problems, several of the issues we discuss and our classification scheme can be extended to other optimization problems.