Scheduling Under Uncertainty: Applications to Aviation, Healthcare and Aerospace

Abstract

When scheduling a project or a mission, it is often challenging to know in advance the exact duration of each task or which resource will be available. Processing times and resource availability are often subject to variability and may only be known at the last minute. Ignoring this uncertainty when planning a project can lead to adverse outcomes such as additional costs, missed deadlines or failed tasks. Conversely, modeling uncertainty in the scheduling decision process has potential to create more robust schedules that will mitigate these negative outcomes. However, the complexity of deterministic scheduling problems is further increased in their stochastic counterpart and many challenges arise when attempting to model and solve scheduling problems subject to uncertainty.

In this dissertation we specifically study four scheduling problems arising from the transportation and the healthcare industries. In each of these four examples, we consider the limitations of deterministic approaches and the impact of uncertainty on the solution's structures and costs. Two problems come from the airline industry. We first create a model to generate flights gate assignments so as to reduce the probability of conflict between planes and mitigate delays. Then we develop a simulation tool to analyze delay recovery strategies under uncertainty. A third project deals with scheduling patient appointment times for chemotherapy infusion under uncertainty of their treatment time. The last area of application that we consider is satellite mission scheduling. We develop several models to solve the download planning problem for a single satellite while considering uncertainty in the availability of multiple receiving ground stations distributed across Earth.