Scheduling in the service industries: An overview

Abstract

Scheduling plays an important role in many different service industries. In this paper we provide an overview of some of the more important scheduling problems that appear in the various service industries. We focus on the formulations of such problems as well as on the techniques used for solving those problems. We consider five areas of scheduling in service industries, namely (i) project scheduling, (ii) workforce scheduling, (iii) timetabling, reservations, and appointments, (iv) transportation scheduling, and (v) scheduling in entertainment. The first two areas are fairly general and have applications in many different service industries. The third, fourth and fifth areas are more related to some very specific service industries, namely the hospitality and health care industries, the transportation industries (of passengers as well as of cargo), and the entertainment industries. In our conclusion section we discuss the similarities and the differences between the problem formulations and solution techniques used in the various different industries and we also discuss the design of the decision support systems that have been developed for scheduling in the service industries.

Keywords

Schedule Problem / Time Slot / Service Industry / Project Schedule / Project Schedule Problem

References

[1] Aggoun A, Vazacopoulos A. Butenko S, Gil-Lafuente J, Pardalos P. Solving Sports Scheduling and Timetabling Problems with Constraint Programming. Economics, Management and Optimization in Sports, 2004, New York: Springer

[2] Ait-Kadia D, Menye J-B, Kane H. Resources assignment model in maintenance activities scheduling. International Journal of Production Research, 2011, 49(22): 6677-6689.

[3] Anagnostopoulos A, Michel L, Van Hentenryck P, Vergados Y. A Simulated Annealing Approach to the Traveling Tournament Problem. Proceedings CPAIOR’003, 2003

[4] Archetti C, Speranza MG, Hertz A. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science, 2006, 40(1): 64-73.

[5] Archetti C, Speranza MG, Savelsbergh MWP. An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Science, 2008, 42(1): 22-31.

[6] Augerat P, Belenguer JM, Benavent E, Corberán A, Naddef D, Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem, 1998, Roma, Italy: Istituto di Analisi dei Sistemi ed Informatica, CNR

[7] Baldacci R, Mingozzi A, Roberti R. Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 2012, 218(1): 1-6.

[8] Bandi C, Bertsimas D. Tractable stochastic analysis in high dimensions via robust optimization. Mathematical Programming, 2012, 134(1): 23-70.

[9] Baptiste Ph, Le Pape CL, Nuijten W. Constraint-Based Scheduling, 2001, Boston: Kluwer Academic Publishers.

[10] Barnhart C, Belobaba P, Odoni A. Applications of Operations Research in the Air Transport Industry. Transportation Science, 2003, 37: 368-391.

[11] Barnhart C, Laporte G. Handbooks in Operations Research and Management Science, 2006, Amsterdam: North-Holland

[12] Barnhart C, Lu F, Shenoi R. Yu G. Integrated Airline Schedule Planning. Operations Research in the Airline Industry, Chapter 13, 1998, Boston: Kluwer Academic Publishers 384-403.

[13] Bartholdi JJ III, Orlin JB, Ratliff HD. Cyclic Scheduling via Integer Programs with Circular Ones. Operations Research, 1980, 28: 1074-1085.

[14] Bartsch T, Drexl A, Kröger S. Scheduling the professional soccer leagues of austria and germany. Computers and Operations Research, 2006, 33: 1907-1937.

[15] Begen MA, Queyranne M. Appointment scheduling with discrete random durations. Mathematics of Operations Research, 2011, 36(2): 240-257.

[16] Belien J, Demeulemeester E. Building cyclic master surgery schedules with leveled resulting bed occupancy. European Journal of Operational Research, 2007, 176: 1185-1204.

[17] Bixby RE, Lee EK. Solving a truck dispatching problem using branch-and-cut. Operations Research, 1998, 46: 355-367.

[18] Blake JT, Carter MW. Surgical process scheduling: a structured review. Journal of the Society for Health Systems, 1997, 5(3): 17-30.

[19] Blake JT, Carter MW. A goal-programming approach to resource allocation in acute-care hospitals. European Journal of Operational Research, 2002, 140: 541-561.

[20] Blake JT, Donald J. Using Integer Programming to Allocate Operating Room Time at Mount Sinai Hospital. Interfaces, 2002, 32(2): 63-73.

[21] Blazewicz J, Cellary W, Slowinski R, Weglarz J. Scheduling under resource constraints — deterministic models, 1986.

[22] Bodin L, Golden B, Assad A, Ball M. Routing and Scheduling of Vehicles and Crews: The State of the Art. Computers and Operations Research, 1983, 10: 63-211.

[23] Bollapragada S, Bussieck M, Mallik S. Scheduling commercial videotapes in broadcast television. Operations Research, 2004, 52: 679-689.

[24] Bollapragada S, Cheng H, Phillips M, Garbiras M, Scholes M, Gibbs T, Humphreville M. NBC’s Optimization Systems Increase Revenues and Productivity. Interfaces, 2002, 32(1): 47-60.

[25] Bollapragada S, Garbiras M. Scheduling commercials on broadcast television. Operations Research, 2004, 52: 337-345.

[26] Bouzina KI, Emmons H. Interval scheduling on identical machines. Journal of Global Optimization, 1996, 9: 379-393.

[27] Brandeau ML, Sainfort F, Pierskalla WP. Operations Research and Health Care — A Handbook of Methods and Applications, 2004.

[28] Brelaz D. New Methods to Color the Vertices of a Graph. Communications of the ACM, 1979, 22: 251-256.

[29] Brown GG, Graves GW, Ronen D. Scheduling ocean transportation of crude oil. Management Science, 1987, 33: 335-346.

[30] Brucker P, Drexl A, Mõhring R, Neumann K, Pesch E. Resource constrained project scheduling: notation, classification, models, and methods. European Journal of Operational Research, 1999, 112: 3-41.

[31] Burgess WJ, Busby RE. Salvendy G. Personnel Scheduling. Handbook of Industrial Engineering chapter 81, 1992, New York: J. Wiley 2155-2169.

[32] Burke E, Carter MW. The Practice and Theory of Automated Timetabling II. Selected Papers from the 2nd International Conference on the Practice and Theory of Automated Timetabling (held August 1997 in Toronto), 1998, Berlin: Springer Verlag

[33] Burke E, De Causmaecker P. The Practice and Theory of Automated Timetabling IV. Selected Papers from the 4th International Conference on the Practice and Theory of Automated Timetabling, Gent, Belgium, August 2002, 2003, Berlin: Springer Verlag

[34] Burke E, De Causmaecker P, Vanden Berghe G, Van Landeghem H. The state of the art of nurse rostering. Journal of Scheduling, 2004, 7: 441-499.

[35] E. Burke, D.G. Elliman, P.H. Ford & R.F. Weare (1996). Exam Timetabling in British Universities: A Survey. The Practice and Theory of Automated Timetabling, E. Burke and P. Ross (eds.), Lecture Notes in Computer Science, Vol. 1153, Springer Verlag, Berlin.

[36] Burke E, Erben W. The Practice and Theory of Automated Timetabling III. Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling (held August 2000 in Konstanz, Germany), 2001, Berlin: Springer Verlag

[37] Burke E, Ross P. The Practice and Theory of Automated Timetabling. Selected Papers from the 1st International Conference on the Practice and Theory of Automated Timetabling, Edinburgh, August 1995, 1996, Berlin: Springer Verlag

[38] Burke E, Rudova H. The Practice and Theory of Automated Timetabling VI. Selected Papers from the 6th International Conference on the Practice and Theory of Automated Timetabling, Brno, Czech Republic, August 2006, 2006

[39] Burke E, Trick M. The Practice and Theory of Automated Timetabling V. Selected Papers from the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburgh, U.S.A. August 2004, 2004, Berlin: Springer Verlag

[40] Burns RN, Carter MW. Work force size and single shift schedules with variable demands. Management Science, 1985, 31: 599-608.

[41] Burns RN, Koop GJ. A modular approach to optimal multiple shift manpower scheduling. Operations Research, 1987, 35: 100-110.

[42] Butenko S, Gil-Lafuente J, Pardalos P. Economics, Management and Optimization In Sports, 2004, Berlin: Springer Verlag.

[43] Campbell AM, Vandenbussche D, Hermann W. Routing for relief efforts. Transportation Science, 2008, 42(2): 127-145.

[44] Caprara A, Fischetti M, Toth P. Modeling and solving the train timetabling problem. Operations Research, 2002, 50: 851-861.

[45] Carey M, Lockwood D. A model, algorithms and strategy for train pathing. Journal of the Operational Research Society, 1995, 46: 988-1005.

[46] Carter MW. A survey of practical applications of examination timetabling algorithms. Operations Research, 1986, 34: 193-202.

[47] Carter MW, Tovey CA. When is the classroom assignment problem hard?. Operations Research, 1992, 40: S28-S39.

[48] Caunhye AM, Nie X, Pokharel S. Optimization models in emergency logistics: a literature review. Socio-Economic Planning Sciences, 2012, 46(1): 4-13.

[49] Cayirli T, Veral E. Outpatient scheduling in health care: a review of literature. Production and Operations Management, 2003, 12(4): 519-549.

[50] Cayirli T, Khiong Yang K, Quek SA. A universal appointment rule in the presence of no-shows and walk-ins. Production and Operations Management, 2012, 21(4): 682-697.

[51] Ceder A, Golany B, Tal O. Creating bus timetables with maximal synchronization. Transportation Research Part A: Policy and Practice, 2001, 35(10): 913-928.

[52] Christiansen M. Decomposition of a combined inventory and time constrained ship routing problem. Transportation Science, 1999, 33: 3-16.

[53] Christiansen M, Fagerholt K, Ronen D. Ship routing and scheduling — status and perspective. Transportation Science, 2004, 38: 1-18.

[54] Christiansen M, Fagerholt K, Nygreen B, Ronen D. Barnhart C, Laporte G. Maritime Transportation. Handbooks in Operations Research and Management Science, Volume 14 — Transportation, 2007, Amsterdam: North-Holland 189-284.

[55] Cordeau J-F, Stojkovic G, Soumis F, Desrosiers J. Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling. Transportation Science, 2001, 35: 375-388.

[56] Cullen FH, Jarvis JJ, Ratliff HD. Set partitioning based heuristics for interactive routing. Networks, 1981, 11: 125-144.

[57] Daduna JR, Branco I, Pinto Paixao JM. Computer Aided Scheduling of Public Transport, 1995, Berlin: Springer Verlag.

[58] Demeulemeester EL, Herroelen WS. Project Scheduling: A Research Handbook, 2002, Boston, MA: Kluwer Academic Publishers

[59] Denton B, Viapiano J, Vogl A. Optimization of surgery sequencing and scheduling decisions under uncertainty. Health Care Management Science, 2007, 10: 13-24.

[60] Desaulniers G, Desrosiers J, Dumas Y, Solomon M M, Soumis F. Daily aircraft routing and scheduling. Management Science, 1997, 43: 841-855.

[61] Desrochers M, Rousseau J-M. Computer Aided Scheduling of Public Transport, 1992, Berlin: Springer Verlag.

[62] de Werra D. Some models of graphs for scheduling sports competitions. Discrete Applied Mathematics, 1988, 21: 47-65.

[63] Elmaghraby SE. On the expected duration of PERT type networks. Management Science, 1967, 13: 299-306.

[64] Emmons H. Workforce scheduling with cyclic requirements and constraints on days off, weekends off, and work stretch. IIE Transactions, 1985, 17: 8-16.

[65] Emmons H, Burns RN. Off-day scheduling with hierarchical worker categories. Operations Research, 1991, 39: 484-495.

[66] Fischetti M, Lodi A, Martello S, Toth P. A polyhedral approach to simplified crew scheduling and vehicle scheduling problems. Management Science, 2001, 47(6): 833-850.

[67] Fisher ML, Rosenwein MB. An interactive optimization system for bulk-cargo ship scheduling. Naval Research Logistics, 1989, 36: 27-42.

[68] Francis PM, Smilowitz KR, Tzur M. The period vehicle routing problem and its extensions. The vehicle routing problem: latest advances and new challenges, 2008, US: Springer 73-102.

[69] Freling R, Wagelmans APM, Paixao JMP. Models and algorithms for single-depot vehicle scheduling. Transportation Science, 2001, 35(2): 165-180.

[70] Fulkerson DR. Expected critical path lengths in PERT type networks. Operations Research, 1962, 10: 808-817.

[71] Garey MR, Johnson DS, Simons BB, Tarjan RE. Scheduling unit-time tasks with arbitrary release times and deadlines. SIAM Journal of Computing, 1981, 10: 256-269.

[72] Gawande M. Workforce Scheduling Problems with Side Constraints, 1996

[73] Goltz HJ, Matzke D. Burke E, Erben W. ConBaTT — Constraint Based TimeTabling. The Practice and Theory of Automated Timetabling III. Selected Papers from the 3rd International Conference on the Practice and Theory of Automated Timetabling, 2001, Berlin: Springer Verlag

[74] Grönkvist M. Using Constraint Propagation to Accelerate Column Generation in Aircraft Scheduling, 2002, Gothenburg, Sweden: Computing Science Department, Chalmers University of Technology

[75] Gupta D, Denton B. Appointment scheduling in health care: challenges and opportunities. IIE Transactions, 2008, 40(9): 800-819.

[76] Gupta D, Wang WY. Patient appointments in ambulatory care. Handbook of Healthcare System Scheduling, 2012, 168: 65-104.

[77] Haase K, Desaulniers G, Desrosiers J. Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 2001, 35(3): 286-303.

[78] K. Hãgele, C.O. Dúnlaing & S. Riis (2001). The complexity of scheduling TV commercials. Electronic Notes in Theoretical Computer Science, Vol. 40.

[79] Hall NG, Liu W-P, Sidney JB. Scheduling in broadcast networks. Networks, 1998, 32: 233-253.

[80] Hall R. Handbook of Healthcare System Scheduling, Vol. 168, 2012, New York: Springer

[81] Hamiez J-P, Hao J-K. Nareyek A. Solving the Sports League Scheduling Problem with Tabu Search. Local Search for Planning and Scheduling, 2001, Berlin: Springer Verlag 24-36.

[82] Hans E, Wullink G, Houdenhoven M v, Kazemier G. Robust surgery loading. European Journal of Operational Research, 2008, 185: 1038-1050.

[83] Hassin R, Mendel S. Scheduling arrivals to queues: a single-server model with no-shows. Management Science, 2008, 54(3): 565-572.

[84] Henz M. Scheduling a major college basketball conference-revisited. Operations Research, 2001, 49: 163-168.

[85] Henz M, Müller T, Thiel S. Global constraints for round robin tournament scheduling. European Journal of Operational Research, 2004, 153: 92-101.

[86] Holguín-Veras J, Jaller M, Wassenhove LNV, Pérez N, Wachtendorf T. On the unique features of post-disaster humanitarian logistics. Journal of Operations Management, 2012, 30(7): 494-506.

[87] Holguín-Veras J, Pérez N, Jaller M, Wassenhove LNV, Aros-Vera F. On the appropriate objective function for postdisaster humanitarian logistics models. Journal of Operations Management, 2013, 31(5): 262-280.

[88] Horen JH. Scheduling of network television programs. Management Science, 1980, 26: 354-370.

[89] Hsu VN, de Matta R, Lee C-Y. Scheduling patients in an ambulatory surgical center. Naval Research Logistics, 2003, 50: 219-238.

[90] Huang M, Smilowitz K, Balcik B. Models for relief routing: equity, efficiency and efficacy. Transportation research part E: logistics and transportation review, 2012, 48(1): 2-18.

[91] Huisman D, Freling R, Wagelmans APM. Multiple depot integrated vehicle and crew scheduling. Transportation Science, 2005, 39(4): 491-502.

[92] Hung R, Emmons H. Multiple-shift workforce scheduling under the 3–4 compressed workweek with a hierarchical workforce. IIE Transactions, 1993, 25: 82-89.

[93] Jia HZ, Ordonez F, Dessouky M. A modeling framework for facility location of medical services for large-scale emergencies. IIE transactions, 2007, 39(1): 41-55.

[94] Jin MZ, Liu K, Bowden RO. A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem. International Journal of Production Economics, 2007, 105(1): 228-242.

[95] Kaandorp GC, Koole G. Optimal outpatient appointment scheduling. Health Care Management Science, 2007, 10(3): 217-229.

[96] Keskinocak P, Tayur S. Scheduling of time-shared jet aircraft. Transportation Science, 1998, 32: 277-294.

[97] Klassen KJ, Yoogalingam R. Improving performance in outpatient appointment services with a simulation optimization approach. Production and Operations Management, 2009, 18(4): 447-458.

[98] Kolish R. Project Scheduling under Resource Constraints, 1995, Heidelberg: Physica-Verlag (Springer Verlag)

[99] LaGanga LR, Lawrence SR. Appointment overbooking in health care clinics to improve patient service and clinic performance. Production and Operations Management, 2012, 21(5): 874-888.

[100] Laporte G, Desroches S. Examination timetabling by computer. Computers and Operations Research, 1984, 11: 351-360.

[101] Lee CG, Epelman MA, White CC III, Bozer YA. A shortest path approach to the multiple-vehicle routing problem with split pick-ups. Transportation research part B: Methodological, 2006, 40(4): 265-284.

[102] Lee C-Y, Lei L. Multiple-project scheduling with controllable project duration and hard resource constraint: Some solvable cases. Annals of Operations Research, 2001, 102(1–4): 287-307.

[103] Marsten RE, Shepardson F. Exact solution of crew scheduling problems using the set partitioning model: recent successful applications. Networks, 1981, 11: 165-177.

[104] Martel CU. Dempster MA, Lenstra JK, Rinnooy Kan AHG. Scheduling Uniform Machines with Release Times, Deadlines and Due times. Deterministic and Stochastic Scheduling, 1982, Dordrecht: Reidel 89-99.

[105] Martel CU. Preemptive scheduling with release times, deadlines and due times. Journal of the Association of Computing Machinery, 1982, 29: 812-829.

[106] Martin C, Jones D, Keskinocak P. Optimizing on-demand aircraft schedules for fractional aircraft operators. Interfaces, 2003, 33(5): 22-35.

[107] Mesquita M, Paixao J. Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations. Computer-aided transit scheduling, 1999 221-243.

[108] Millhiser WP, Veral E. Designing appointment system templates with operational performance targets, 2014, New York, NY: Zicklin School of Business, Baruch College CUNY

[109] Miyashiro R, Matsui T. Round-Robin Tournaments with a Small Number of Breaks, 2003, Tokyo, Japan: Graduate School of Information Science and Technology, the University of Tokyo

[110] Moder JG, Philips CR. Project Management with CPM and PERT, 1970, New York: Van Nostrand Reinhold

[111] Mulvey JM. A classroom/time assignment model. European Journal of Operational Research, 1982, 9: 64-70.

[112] Nanda R, Browne J. Introduction to Employee Scheduling, 1992, NY: Van Nostrand Reinhold

[113] Nemhauser GL, Trick M. Scheduling a major college basketball conference. Operations Research, 1998, 46: 1-8.

[114] Neumann K, Schwindt C, Zimmermann J. Project Scheduling with Time Windows and Scarce Resources, 2001, Berlin: Springer Verlag.

[115] Patterson JH. A comparison of exact approaches for solving the multiple constrained resources rroject scheduling problem. Management Science, 1984, 30: 854-867.

[116] Perakis AN, Bremer WM. An operational tanker scheduling optimization system: background, current practice and model formulation. Maritime Policy and Management, 1992, 19: 177-187.

[117] PERT Program Evaluation Research Task. Phase I Summary Report, Special Projects Office, Bureau of Ordnance, 1958, Washington, D.C: Department of the Navy

[118] Peteghem VV, Vanhoucke M. An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, 2014, 235(1): 62-72.

[119] Posner ME. Minimizing weighted completion times with deadlines. Operations Research, 1985, 33: 562-574.

[120] Reddy SK, Aronson JE, Stam A. SPOT: scheduling programs optimally for television. Management Science, 1998, 44: 83-102.

[121] Regin JC. Sports Scheduling and Constraint Programming, 1999

[122] Ribeiro CC, Soumis F. A column generation approach to the multiple-depot vehicle scheduling problem. Operations Research, 1994, 42(1): 41-52.

[123] Robinson LW, Chen RR. A comparison of traditional and open-access policies for appointment scheduling. Manufacturing & Service Operations Management, 2010, 12(2): 330-346.

[124] Rousseau LM, Gendreau M, Pesant G. A general approach to the physician rostering problems. Annals of Operations Research, 2002, 115: 193-205.

[125] Sasieni M. A note on PERT times. Management Science, 1986, 30: 1652-1653.

[126] Schaerf A. Scheduling sport tournaments using constraint logic programming. Constraints, 1999, 4: 43-65.

[127] Schönberger J, Mattfeld DC, Kopfer H. Memetic algorithm timetabling for non-commercial sport leagues. European Journal of Operational Research, 2004, 153: 102-116.

[128] Schreuder JAM. Combinatorial aspects of construction of competition dutch professional football leagues. Discrete Applied Mathematics, 1992, 35: 301-312.

[129] Stojkovic G, Soumis F, Desrosiers J, Solomon M. An Optimization Model for a Real-Time Flight Scheduling Problem. Transportation Research Part A: Policy and Practice, 2002, 36: 779-788.

[130] Stojkovic M, Soumis F, Desrosiers J. The operational airline crew scheduling problem. Transportation Science, 1998, 32: 232-245.

[131] Talbot FB. Resource constrained project scheduling with time-resource trade-offs: the nonpreemptive case. Management Science, 1982, 28: 1197-1210.

[132] Tien JM, Kamiyama A. On manpower scheduling algorithms. SIAM Review, 1982, 24: 275-287.

[133] Trick M. Burke EK, Erben W. A Schedule-and-Break Approach to Sports Scheduling. Practice and Theory of Automated Timetabling III. Selected Papers of Third International Conference PATAT 2000 (Konstanz, Germany), 2001, Berlin: Springer Verlag 242-253.

[134] Velasquez R, Melo RT, Kuefer K-H. Kalcsics J, Nickel S. Tactical Operating Theatre Scheduling: Efficient Appointment Assignment. Operations Research Proceedings 2007. Proceedings of the GOR 2007 Conference (Saarbruecken), 2008 303-310.

[135] Voss S, Daduna JR. Computer Aided Scheduling of Public Transport, 2001, Berlin: Springer Verlag.

[136] Walker MR, Sayer JS. Project Planning and Scheduling, 1959, Wilmington, Del: E.I. du Pont de Nemours & Co., Inc.

[137] Weglarz J, Jozefowska J, Mika M, Waligóra G. Project scheduling with finite or infinite number of activity processing modesA survey. European Journal of Operational Research, 2011, 208(3): 177-205.

[138] Wiest JD, Levy FK. A Management Guide to PERT/CPM, 1977

[139] Wilson NHM. Computer Aided Scheduling of Public Transport, 1999, Berlin: Springer Verlag

[140] Wong C S, Chan F T S, Chung S H. A joint production scheduling approach considering multiple resources and preventive maintenance tasks. International Journal of Production Research, 2013, 51(3): 883-896.

[141] Wren A, Daduna JR. Computer Aided Scheduling of Public Transport, 1988, Berlin: Springer Verlag.

[142] Yu G. Operations Research in the Airline Industry, 1998, Boston: Kluwer Academic Publishers

[143] Zacharias C, Pinedo M. Appointment scheduling with no-shows and overbooking. Production and Operations Management, 2014, 23(5): 788-801.

[144] Zacharias C, Pinedo M. Managing customer arrivals in service systems with multiple servers, 2014, New York University, New York, NY: Working Paper, Stern School of Business