Open Collections

Appointment scheduling with discrete random durations and applications

University of British Columbia

We study scheduling of jobs on a highly utilized resource when the processing durations are stochastic and there are significant underage (resource idle-time) and overage (job waiting and/or resource overtime) costs. Our work is motivated by surgery scheduling and physician appointments. We consider several extensions and applications. In the first manuscript, we determine an optimal appointment schedule (planned start times) for a given sequence of jobs (surgeries) on a single resource (operating room, surgeon). Random processing durations are integers and given by a discrete probability distribution. The objective is to minimize the expected total underage and overage costs. We show that an optimum solution is integer and can be found in polynomial time. In the second manuscript, we consider the appointment scheduling problem under the assumption that the duration probability distributions are not known and only a set of independent samples is available, e.g., historical data. We develop a sampling-based approach and determine bounds on the number of independent samples required to obtain a provably near-optimal solution with high probability. In manuscript three, we focus on determining the number of surgeries for an operating room in an incentive-based environment. We explore the interaction between the hospital and the surgeon in a game theoretic setting, present empirical findings and suggest incentive schemes that the hospital may offer to the surgeon to reduce its idle time and overtime costs. In manuscript four, we consider an application to inventory management in a supply chain context. We introduce advance multi-period quantity commitment with stochastic characteristics (demand or yield) and describe several real-world applications. We show these problems can be solved as special cases of the appointment scheduling problem. In manuscript five, an appendix, we develop an alternate solution approach for the appointment scheduling problem. We find a lower bound value, obtain a subgradient of the objective function, and develop a special-purpose integer rounding algorithm combining discrete convexity and non-smooth convex optimization methods.

Text

2010-04-09

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/23332

Business Administration

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/