Appointment scheduling with discrete random durations

ABSTRACT

We consider the problem of determining optimal appointment schedule for a given sequence of jobs (e.g., medical procedures) on a single processor (e.g., operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random processing duration given by a joint discrete probability distribution. Simple conditions on the cost rates imply that the objective function is submodular and L-convex. Then there exists an optimal appointment schedule which is integer and can be found in polynomial time. Our model can handle a given due date for the total processing (e.g., end of day for an operating room) after which overtime is incurred and, no-shows and emergencies.

REFERENCES

• 1: M. A. Begen, R. Levi, and M. Queyranne, A sampling-based approach to appointment scheduling, Working Paper, Sauder School of Business, University of British Columbia, (2008).
• 2: M. A. Begen and M. Queyranne, Minimizing a discrete-convex function for appointment scheduling, Working Paper, Sauder School of Business, University of British Columbia, (2008).
• 3: P. M. V. Bosch, D. C. Dietz, and J. R. Simeoni, Scheduling customer arrivals to a stochastic service system, Naval Research Logistics, 46 (1999), pp. 549--559.
• 4: T. Cayirli and E. Veral, Outpatient scheduling in health care: A review of literature, Production and Operations Management, 12 (2003).
• 5: B. Denton and D. Gupta, A sequential bounding approach for optimal appointment scheduling, IIE Transactions, 35 (2003), pp. 1003--1016.
• 6: S. Fujishige, Submodular Functions and Optimization, Elsevier, 2005.
• 7: Satoru Iwata, Submodular function minimization, Mathematical Programming: Series A and B, v.112 n.1, p.45-64, July 2007 [doi>10.1007/s10107-006-0084-2]
• 8: G. C. Kaandorp and G. Koole, Optimal outpatient appointment scheduling, Health Care Man. Sci., 10 (2007), pp. 217--229.
• 9: S. T. McCormick, Submodular function minimization. a chapter in the handbook on discrete optimization, Elsevier, K. Aardal, G. Nemhauser, and R. Weismantel, eds, (2006).
• 10: K. Murota, Discrete Convex Analysis, SIAM, 2003.
• 11: J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, to appear in Math Programming, (2007).
• 12: Michael L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer Publishing Company, Incorporated, 2008
• 13: L. W. Robinson and R. R. Chen, Scheduling doctors' appointments: optimal and empirically-based heuristic policies, IIE Transactions, 35 (2003), pp. 295--307.
• 14: L. W. Robinson, Y. Gerchak, and D. Gupta, Appointment times which minimize waiting and facility idleness, Working Paper, DeGroote School of Business, McMaster University, (1996).
• 15: F. Sabria and C. F. Daganzo, Approximate expressions for queuing systems with scheduling arrivals and established service order, Transportation Science, 23 (1989), pp. 159--165.
• 16: D. M. Topkis, Minimizing a submodular function on a lattice, Oper. Res., 26 (1978), pp. 305--321.
• 17: P. P. Wang, Static and dynamic scheduling of customer arrivals to a single-server system, Naval Research Logistics, 40 (1993), pp. 345--360.
• 18: P. P. Wang, Sequencing and scheduling n cusotmers for a stochastic server, European Journal of Operations Research, 119 (1999), pp. 729--738.
• 19: E. N. Weiss, Models for determining estimated start times and case orderings in hospital operating rooms, IIE Transactions, 22 (1990), pp. 143--150.
• 20: P. Zipkin, On the structure of lost-sales inventory models, Oper. Res., Published Online, (2008).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization