Abstract

Operating room (OR) scheduling is becoming increasingly important and poses a challenging problem due to the presence of uncertainty. Motivated by OR scheduling, we study the single machine scheduling problem with uncertainty in both dynamic arrivals and stochastic processing times. We use rescheduling to handle uncertainty and study both efficiency and instability (a measure of schedule deviation). The chosen efficiency metric, final total weighted tardiness (FTWT), is the total weighted tardiness of the final schedule. We develop a discrete-event simulation framework with embedded optimization to conduct two computational experiments. The first experiment analyzes the joint effect of different processing time distributions and rescheduling policies for the single machine scheduling problem with deterministic processing times and dynamic arrivals. Secondly, we analyze the joint effect of different processing time distributions and rescheduling policies for the single machine problem with stochastic processing times and dynamic arrivals. For both experiments, we find that the variance of the processing time distributions has a greater impact than the shape of the distribution. Furthermore, the eventJobCompletion policy, which reschedules every time a job finishes processing, performs well across all distributions in both experiments.
For the stochastic experiment, the eventJobCompletion policy also stood out as being the most consistent across all processing time distributions. Finally, in both experiments, we find that the average length of the rescheduling interval does not have an effect on total instability and FTWT.