Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling
Harish Guda, Milind Dawande, Ganesh Janakiraman, Kyung Sung Jung
Production and Operations Management · 2016 · Volume 25 · Issue 7
Abstract
We consider the stochastic, single-machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due-dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker (2014) shows the optimality of the Shortest-Variance-First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption ofdilation orderingof the processing durations. Sinceconvex orderingimplies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.
Keywords
stochastic scheduling, appointment scheduling, smallest-variance-first rule, convex order
Enable JavaScript for citation tools and additional paper interactions.