The authors develop methods for optimally scheduling and sequencing customer arrivals to a single-server appointment system. Customers are characterized by probabilistic service times with distinct distributions, and the server works according to a first-come, first-served discipline. A customer may fail to show for an appointment with known probability, but all arriving customers are assumed to be punctual. Costs are incurred at a specified rate per unit time that each customer waits for service, and an additional cost is incurred for every unit of time that the server operates beyond a scheduled closing time. The objective is to minimize the combined costs of customer waiting and server overtime. Possible applications include scheduling surgeons to operating suites, scheduling military aircraft to training ranges, and scheduling service activities for telecommunication technicians.
Get full access to this article
View all access options for this article.
References
1.
Altiok, T.
(1985), “On the Phase-Type Approximations of General Distributions,”IIE Transactions, 17, 110-116.
2.
Bailey, N.T.J.
(1952), “A Study of Queues and Appointment Systems in Hospital Outpatient Departments, with Special Reference to Waiting Times,”Journal of the Royal Statistical Society—Series B, 14, 185-199.
3.
Cox, D. R.
(1955), “A Use of Complex Probabilities in the Theory of Stochastic Processes,”Procedings of the Cambridge Philosophical Society, 51, 313-319.
4.
Fries, B.
, and V. Marathe (1981), “Determination of Optimal Variables-Sized Multiple-Block Appointment Systems,”Operations Research, 29, 324-345.
5.
Fry, J.
(1964), “Appointments in General Practice,”Operational Research Quarterly, 15, 233-237.
6.
Golden, B. L.
, and W. R. Stewart (1985), “Empirical Analysis of Heuristics,” in The Traveling Salesman Problem, E. L. Lawler et al., eds. New York: John Wiley.
7.
Grape, G. R.
(1968), “Convergence and Cost Minimization in Queuing Systems of the Type (D,M,1),”FOA (Försvarets Forskningsanstalt), 2, 1-6.
8.
Gray, W. J.
, and P. P. Wang (1995), “On the Computation of Optimal Arrival Times for a Single-Server System,”Chinese Institute of Industrial Engineering, 14, 245-252.
9.
Ho, C.
, H. Lau, and J. Li (1995), “Introducing Variable-Interval Appointment Scheduling Rules in Service Systems,”International Journal of Operations and Production Management, 15, 58-69.
10.
Jackson, R.R.P.
(1964), “Design of an Appointments System,”Operational Research Quarterly, 15, 219-224.
11.
Jansson, B.
(1966), “Choosing a Good Appointment System—A Study of Queues of the Type D/M/1,”Operations Research, 14, 292-312.
12.
Kendall, D. G.
(1951), “Some Problems in the Theory of Queues,”Journal of the Royal Statistical Society—Series B, 18, 151-185.
13.
Liao, C.
, C. D. Pegden, and M. Rosenshine (1993), “Planning Timely Arrivals to a Stochastic Production or Service System,”IIE Transactions, 25, 63-73.
14.
Lin, S.
, and B. W. Kernighan (1973), “An Effective Heuristic Algorithm for the Traveling Salesman Problem,”Operations Research, 21, 498-516.
15.
Magerlein, J. M.
, and J. B. Martin (1978), “Surgical Demand Scheduling: A Review,”Health Services Research, 13, 418-433.
16.
Mercer, A.
(1960), “A Queueing Problem in Which the Arrival Times of the Customers Are Scheduled,”Journal of the Royal Statistical Society—Series B, 22, 108-113.
17.
Moler, C.
, and C. Van Loan (1978), “Nineteen Dubious Ways to Compute the Exponential of a Matrix,”SIAM Review, 20, 801-837.
18.
Morse, P. M.
(1963), Queues, Inventories, and Maintenance: The Analysis of Operational Systems with Variable Demand and Supply.New York: John Wiley.
19.
Pegden, C. D.
, and M. Rosenshine (1990), “Scheduling Arrivals to Queues,”Computers and Operations Research, 17, 343-348.
20.
Pinedo, M.
(1995), Scheduling: Theory, Algorithms, and Systems. Englewood Cliffs, NJ: Prentice Hall.
21.
Przasnyski, Z. H.
(1986), “Operating Room Scheduling,”AORN Journal, 44, 67-79.
22.
Sabria, F.
, and C. F. Daganzo (1989), “Approximate Extensions for Queueing Systems with Scheduled Arrivals and Established Service Order,”Transportation Science, 23, 159-169.
23.
Simeoni, J. R. (1994), “An Efficient Approach to Solving the Control of Arrivals Problem,” master’s thesis, AFIT/GOR/ENS/94M-14, Air Force Institute of Technology.
24.
Topkis, D. M.
(1978), “Minimizing a Submodular Function on a Lattice,”Operations Research, 26, 305-321.
25.
Vanden Bosch, P. M. (1997), “Scheduling and Sequencing Arrivals for a Stochastic Service System,” doctoral dissertation, AFIT/DS/ENS/97-03, Air Force Institute of Technology.
26.
Vanden Bosch, P. M.
, and D. C. Dietz (2000), “Minimizing Expected Waiting Cost in a Medical Appointment System,”IIE Transactions, 32, 841-848.
27.
Vanden Bosch, P. M.
, D. C. Dietz, and E. A. Pohl (1999), “Choosing the Best Approach to Matrix Exponentiation,”Computers and Operations Research, 26, 871-882.
28.
Vanden Bosch, P. M.
, D. C. Dietz, and J. R. Simeoni (1999), “Scheduling Customer Arrivals for a Stochastic Service System,”Naval Research Logistics, 46, 549-559.
29.
Voorhis, W. R.
(1956), “Waiting-Line Theory as a Management Tool,”Operations Research, 4, 221-228.
30.
Wang, P. P.
(1993), “Static and Dynamic Scheduling of Customer Arrivals to a Single-Server System,”Naval Research Logistics, 40, 345-360.
31.
Wang, P. P.
(1997), “Optimally Scheduling N Customer Arrival Times for a Single-Server System,”Computers and Operations Research, 24, 703-716.
32.
Weiss, E. N.
(1990), “Models for Determining Estimated Start Times in Hospital Operating Rooms,”IIE Transactions, 22, 143-150.
