Minimizing Earliness/Tardiness costs on multiple machines with an application to surgery scheduling

Early or tardy surgeries are frustrating for both patients and personnel, and cause inefficient use of resources at the operating rooms. The stochastic Earliness/Tardiness (E/T) scheduling problem addresses this by minimizing the total expected deviation of the surgery completion times from the planned completion times. We introduce the concept of E/T-concavity as a property of a probability distribution if the E/T costs are concave as a function of the standard deviation of the completion time, whenever the optimal planned completion times are selected. We use this concept to generate an optimal schedule for the multiple machine variant of the E/T problem. The optimal schedule is not unique and therefore allows us to consider several optimization objectives in addition to the E/T objective. We demonstrate the usefulness of our results in practice by proving E/T-concavity for several probability distributions and by showing that, under the assumption of E/T-concavity, a simple Shortest Variance First (SVF) rule is optimal. We conclude by providing a numerical example of surgery scheduling where we demonstrate the benefits of the SVF rule compared to several commonly used scheduling rules.