Abstract
The employee tour scheduling problem involves the determination of both work hours of the day and workdays of the week for each employee. This problem has proven difficult to solve optimally due to its large size and pure integer nature. During the last decade, numerous approaches for modeling and solving this problem have been proposed. In this paper, employee tour scheduling literature published since 1990 is reviewed and classified. Solution techniques are classified into ten categories: (1) manual solution, (2) integer programming, (3) implicit modeling, (4) decomposition, (5) goal programming, (6) working set generation, (7) LP-based solution, (8) construction and improvement, (9) metaheuristics, and (10) other methods. The objective is to identify broad classifications, present typical mathematical models, compare the different methods, and identify future research directions.
Similar content being viewed by others
References
Alfares, H.K. (1999). “Aircraft Maintenance Workforce Scheduling: A Case Study.” Journal of Quality in Maintenance Engineering 5(2), 78-88.
Alfares, H.K. (2000). “Four-Week Employee Scheduling Using the (7/3, 7/3, 6/2) Days-off Schedule.” Arabian Journal of Science and Engineering 25(1C), 95-108.
Alfares, H.K. (2001). “Staffing and Workforce Scheduling for a Security Gate.” International Journal of Operations and Quantitative Management 7(4), 281-293.
Alfares, H.K. and J.E. Bailey. (1997). “Integrated Project Task and Manpower Scheduling.” IIE Transactions 29(9), 711-717.
Al-Tabatabai, H. and A.P. Alex. (1997). “Manpower Scheduling Optimization Using Genetic Algorithms.” In Proceedings of the 1997 4th Congress on Computing in Civil Engineering, Philadelphia, PA, USA, 16-18 June, pp. 702-709.
Alvarez-Valdes, R., E. Crespo, and J.M. Tamarit. (1999). “Labour Scheduling at an Airport Refueling Installation.” Journal of the Operational Research Society 50(3), 211-218.
Andrews, B. and H. Parsons. (1993). “Establishing Telephone Agent Staffing Levels through Economic Optimization.” Interfaces 23(2), 14-20.
Ashley, D.W. (1995). “Spreadsheet Optimization System for Library Staff Scheduling.” Computers and Operations Research 22(6), 615-624.
Aykin, T. (2001). “A Comparative Evaluation of Modeling Approaches to the Labor Shift Scheduling Problem.” European Journal of Operational Research 125(2), 381-397.
Bailey, J.E. (1985). “Integrated Days off and Shift Personnel Scheduling.” Computers and Industrial Engineering 9(4), 395-404.
Baker, K.R. (1976). ”Workforce Allocation in Cyclical Scheduling Problems: A Survey.” Operational Research Quarterly 27(1ii), 155-167.
Balakrishnan, N. and R.T. Wong. (1990). “A Network Model for the Rotating Workforce Scheduling Problem.” Networks 20(1), 25-42.
Bartholdi III, J.J. and K.R. Gue. (2000). “Reducing Labor Costs in an LTL Crossdocking Terminal.” Operations Research 48(6), 823-832.
Beaumont, N. (1997). “Scheduling Staff Using Mixed Integer Programming.” European Journal of Operational Research 98(3), 473-484.
Bechtold, S.E. (1988). “Implicit Optimal and Heuristic Labor Staffing in a Multiobjective, Multilocation Environment.” Decision Sciences 19(2), 353-373.
Bechtold, S.E. and M.J. Brusco. (1994a). “A Microcomputer-Based Heuristic for Tour Scheduling of a Mixed Workforce.” Computers and Operations Research 21(9), 1001-1009.
Bechtold, S.E. and M.J. Brusco. (1994b). “Working Set Generation Methods for Labor Tour Scheduling.” European Journal of Operational Research 74(3), 540-551.
Bechtold, S.E. and M.J. Brusco. (1995). “Microcomputer-Based Working Set Generation Methods for Personnel Scheduling.” International Journal of Operations and Production Management 15(10), 63-74.
Bechtold, S.E., M.J. Brusco, and M.J. Showalter. (1991). “A Comparative Evaluation of Labor Tour Scheduling Methods.” Decision Sciences 22(4), 683-699.
Bechtold, S.E. and L.W. Jacobs. (1990). “Implicit Modeling of Flexible Break Assignment in Optimal Shift Scheduling.” Management Science 36(11), 1339-1351.
Bechtold, S.E. and L.W. Jacobs. (1991). “Improvement in Labour Utilization in Shift Scheduling for Services with Implicit Optimal Modeling.”International Journal of Operations and Production Management 11(2),54-70.
Bechtold, S.E. and M.J. Showalter. (1987). “A Methodology for Labor Scheduling in a Service Operating System.” Decision Sciences 18(1), 89-107.
Bedworth, D.D. and J.E. Bailey. (1987). Integrated Production Control Systems: Management, Analysis, Design, 2nd ed. New York: Wiley, pp. 387-420.
Berman, O., R.C. Larson, and E. Pinker. (1997). “Scheduling Workforce and Workflow in a High Volume Factory.” Management Science 43(2), 158-172.
Brusco, M.J. (1998). “Solving Personnel Tour Scheduling Problems Using the Dual All-Integer Cutting Plane.” IIE Transactions 30(9),835-844.
Brusco, M.J. and L.W. Jacobs. (1993a). “A Simulated Annealing Approach to the Cyclic Staff-Scheduling Problem.” Naval Research Logistics 40(1), 69-84.
Brusco, M.J. and L.W. Jacobs. (1993b). “A Simulated Annealing Approach to Flexible Labor Scheduling Problems.”Journal of the Operational Research Society 44(12), 1191-1200.
Brusco, M.J. and L.W. Jacobs. (1993c). “Developing Flexible Personnel Schedules Using a Microcomputer.”Work Study 42(5), 5-8.
Brusco,M.J. and L.W. Jacobs. (1995). “Cost Analysis of Alternative Formulations for Personnel Scheduling in Continuously Operating Organizations.” European Journal of Operational Research 86(2), 249-261.
Brusco, M.J. and L.W. Jacobs. (1998a). “Personnel Tour Scheduling When Starting-Time Restrictions Are Present.” Management Science 44(4), 534-547.
Brusco, M.J. and L.W. Jacobs. (1998b). “Eliminating Redundant Columns in Continuous Tour Scheduling Problems.” European Journal of Operational Research 111(3), 518-525.
Brusco, M.J. and L.W. Jacobs. (2000). “Optimal Models for Meal-Break and Start-Time Flexibility in Continuous Tour Scheduling.” Management Science 46(12), 1630-1641.
Brusco, M.J. and L.W. Jacobs. (2001). “Starting-Time Decisions in Labor Tour Scheduling: An Experimental Analysis and Case Study.” European Journal of Operational Research 131(3), 459-475.
Brusco, M.J., L.W. Jacobs, R.J. Bongiorno, D.V. Lyons, and B. Tang. (1995). “Improving Personnel Scheduling at Airline Stations.” Operations Research 43(5), 741-751.
Brusco, M.J. and T.R. Johns. (1995a). “The Effect of Demand Characteristics on Labour Scheduling Methods.” International Journal of Operations and Production Management 15(1), 74-88.
Brusco, M.J. and T.R. Johns. (1995b). “Improving the Dispersion of Surplus Labor in Personnel Scheduling Solutions.” Computers and Industrial Engineering 28(4), 745-754.
Brusco, M.J. and T.R. Johns. (1996). “A Sequential Integer Programming Method for Discontinuous Labor Tour Scheduling.” European Journal of Operational Research 95(3), 537-548.
Burns, R.N. and M.W. Carter. (1985). “Workforce Size and Single Shift Schedules with Variable Demands.” Management Science 31(5), 599-607.
Burns, R. and R. Narasimhan. (1999). “Multiple Shift Scheduling of Workforce on Four-Day Workweeks.”Journal of the Operational Research Society 50(9), 979-981.
Cai, X. and K.N. Li. (2000). “A Genetic Algorithm for Scheduling Staff of Mixed Skills under Multicriteria.” European Journal of Operational Research 125(2), 359-369.
Cezik, T., O. Gunluk, and H. Luss. (2001). “An Integer Programming Model for the Weekly Tour Scheduling Problem.” Naval Research Logistics 48(7), 607-6
Chan, P. and G. Weil. (2001). “Cyclical Staff Scheduling Using Constraint Logic Programming.” In E. Burke and W. Erben (eds.), Practice and Theory of Automated Timetabling III 3rd International Conference, PATAT 2000, Konstanz, Germany, 16-18 August 2000. Selected Papers. Berlin/Heidelberg: Springer, pp. 159-175.
Chew, K.L. (1991). “Cyclic Schedule for Apron Services.”Journal of the Operational Research Society 42(12), 1061-1069.
Dantzig, G.B. (1954). “A Comment on Edie's Traffic Delays at Toll Booths.” Operations Research 2(3), 339-341.
Easton, F. and N. Mansour. (1993). “A Distributed Genetic Algorithm for Employee Scheduling Problems.” In S. Forest (ed.), Genetic Algorithms: Proceedings of the 5th International Conference.San Mateo, CA: Morgan Kaufmann, pp. 360-367.
Easton, F. and N. Mansour. (1999). “Distributed Genetic Algorithm for Deterministic and Stochastic Labor Scheduling Problems.” European Journal of Operational Research 118(3), 505-523.
Easton, F.F. and D.F. Rossin. (1991a). “Sufficient Working Subsets for the Tour Scheduling Problem.” Management Science 37(11), 1441-1451.
Easton, F.F. and D.F. Rossin. (1991b). “Equivalent Alternative Solutions for the Tour Scheduling Problem.” Decision Sciences 22(5), 985-1001.
Easton, F.F. and D.F. Rossin. (1996). “A Stochastic Goal Program for Employee Scheduling.” Decision Sciences 27(3), 541-568.
Easton, F.F. and D.F. Rossin. (1997). “Overtime Schedules for Full-Time Service Workers.” Omega 25(3), 285-299.
Gartner, J., N. Musliu, and W. Slany. (2001). “Rota: A Research Project on Algorithms for Workforce Scheduling and Shift Design Optimization.” AI Communications 14(2), 83-92.
Glover, F. (1986). “Future Paths for Integer Programming and Links to Artificial Intelligence.” Computers and Operations Research 13(5), 533-549.
Glover, F. and G.A. Kochenberger. (1996). “Critical Event Tabu Search for Multidimensional Knapsack Problems.” In I.H. Osman and J.P. Kelly, (eds.), Meta-Heuristics: Theory and Applications. Norwell, MA: Kluwer Academic, pp. 407-427.
Glover, F.andC. McMillan. (1986). “The Generalized Employee Scheduling Problem: An Integration of MS and AI.” Computers and Operations Research 13(5), 563-573.
Goodale, J. and G. Thompson. (1996). “Heuristics for Assigning Individual Workers to Labor Tour Schedules.” InProceedings of the 1996 27th Annual Meeting of the Decision Science Institute, Atlanta, GA, 24-26 November 1996, Vol. 3, pp. 1614-1616.
Goodale, J. and E. Tunc. (1996). “Labor Scheduling with Learning Effects.” In Proceedings of the 1996 27th Annual Meeting of the Decision Science Institute, Atlanta, GA, 24-26 November 1996, Vol. 1, p. 432.
Goodale, J.C. and E. Tunc. (1998). “Tour Scheduling with Dynamic Service Rates.” International Journal of Service Industry Management 9(3), 226-247.
Gopalakrishnan, M., S. Gopalakrishnan, and D.M.Miller. (1993). “A Decision Support System for Scheduling Personnel in a Newspaper Publishing Environment.” Interfaces 23(4), 104-115.
Hanna, M.E. and L.M. Austin. (1985). “An Advanced Start Algorithm for All-Integer Programming.” Computers and Operations Research 12(3), 301-309.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press.
Hung, R. (1993). “A Three-Day Workweek Multiple-Shift Scheduling Model.” Journal of the Operational Research Society 44(2), 141-146.
Hung, R. (1994a). “A Multiple-ShiftWorkforce Scheduling Model under the 4-Day Workweek withWeekday and Weekend Labour Demands.” Journal of the Operational Research Society 45(9), 1088-1092.
Hung, R. (1994b). “Multiple-ShiftWorkforce Scheduling under the 3-4Workweek with DifferentWeekday and Weekend Labor Requirements.” Management Science 40(2), 280-284.
Hung, R. (1997a). “Shiftwork Scheduling Algorithms with Phase-Delay Feature.” International Journal of Production Research 35(7), 1961-1968.
Hung, R. (1997b). “Scheduling for Continuous Operations: The Baylor Plan.” International Journal of Materials and Product Technology 12(1), 37-42.
Hung, R. and H. Emmons. (1993). “Multiple-ShiftWorkforce Scheduling under the 3-4 CompressedWorkweek with a Hierarchical Workforce.” IIE Transactions 25(5), 82-89.
Isken, M.W. andW.M. Hancock. (1998). “Tactical Scheduling Analysis for Hospital Ancillary Units.” Journal of the Society for Health Systems 5(4), 11-23.
Jacobs, L.W. and S.E. Bechtold. (1993a). “Microcomputer-Based Workforce Scheduling.” International Journal of Service Industry Management 4(1), 36-48.
Jacobs, L.W. and S.E. Bechtold. (1993b). “Labor Utilization Effects of Labor Scheduling Flexibility Alternatives in a Tour Scheduling Environment.” Decision Sciences 24(1), 148-166.
Jacobs, L.W. and M.J. Brusco. (1996). “Overlapping Start-Time Bands in Implicit Tour Scheduling.” Management Science 42(9), 1247-1259.
Jarrah, A.I.Z., J.F. Bard, and A.H. deSilva. (1994). “Solving Large-Scale Tour Scheduling Problems.” Management Science 40(9), 1124-1144.
Keith, E. (1979). “Operator Scheduling.” AIIE Transactions 11(1), 37-41.
Khoong, C.M. (1993). “A Simple but Effective Heuristic for Work-Shift Assignment.” Omega 21(3), 393-395.
Khoong, C.M. and H.C. Lau. (1992). “ROMAN: An Integrated Approach to Manpower Planning and Scheduling.” In O. Balci, R. Sharda, and S.A. Zenios (eds.), Computer Science and Operations Research: New Developments in Their Interfaces. Oxford: Pergamon Press, pp. 383-396.
Kirpatrick, S., C. Gellat, and M. Vecchi. (1983). “Optimization by Simulated Annealing.” Science 220(4598), 671-680.
Knapp, G.M. and M. Mahajan. (1998). “Optimization of Maintenance Organization and Manpower in Process Industries.” Journal of Quality in Maintenance Engineering 4(3), 168-183.
Laporte, G. (1999). “Art and Science of Designing Rotating Schedules.” Journal of the Operational Research Society 50(10), 1011-1017.
Lauer, J., L.W. Jacobs, M.J. Brusco, and S.E. Bechtold. (1994). “An Interactive Optimization-Based Decision Support System for Scheduling Part-Time Computer Lab Attendants.” Omega 22(6), 613-626.
Li, C., E.P. Robinson, and V.A. Mabert. (1991). “An Evaluation of Tour Scheduling Heuristics with Differences in Employee Productivity and Cost.” Decision Sciences 22(4), 700-718.
Lin, C.K.Y. (1999). “Microcomputer-Based Workforce Scheduling for Hospital Porters.” Journal of Management in Medicine 13(4), 251-256.
Lin, C.K.Y., K.F. Lai, and S.L. Hung. (2000). “Development of a Workforce Management System for a Customer Hotline Service.” Computers and Operations Research 27(10), 987-1004.
LINDO Systems, What's Best! Chicago, IL, USA: LINDO Systems.
Loucks, J.S. and F.R. Jacobs. (1991). “Tour Scheduling and Task Assignment of a Heterogeneous Work Force: A Heuristic Approach.” Decision Sciences 22(4), 719-738.
Love, R.R. and J.M. Hoey. (1990). “Management Science Improves Fast-Food Operations.” Interfaces 20(2), 21-29.
Mabert, V. and M. Showalter. (1990). “Measuring the Impact of Part-Time Workers in Service Organizations.” Journal of Operations Management 9(2), 209-229.
Mason, A.J., D.M. Ryan, and D.M. Panton. (1998). “Integrated Simulation, Heuristic, and Optimization Approaches to Staff Scheduling.” Operations Research 46(2), 161-175.
McCampbell, A.S. (1996). “Benefits Achieved through Alternative Work Schedules.” Human Resource Planning 19(3), 30-37.
Melachrinoudis, E. and M. Olafsson. (1992). “A Scheduling System for Supermarket Cashiers.” Computers and Industrial Engineering 23(1-4), 121-124.
Melachrinoudis, E. and M. Olafsson. (1995). “A Microcomputer Cashier Scheduling System for Supermarket Stores.” International Journal of Physical Distribution and Logistics 25(1), 34-50.
Morris, J.G. and M.J. Showalter. (1983). “Simple Approaches to Shift, Days-off, and Tour Scheduling Problems.” Management Science 29(8), 942-950.
Nanda, R and J. Browne. (1992). Introduction to Employee Scheduling. New York: Van Nostrand Reinhold.
Narasimhan, R. (2000). “Algorithm for Multiple Shift Scheduling of Hierarchical Workforce on Four-Day or Three-Day Workweeks.” INFOR 38(1), 14-32.
Panton, D. (1991). “On the Creation of Multiple Shift Continuous Operations Rosters under GeneralWorkforce Conditions.” Asia-Pacific Journal of Operational Research 8(2), 189-210.
Pirlot, M. (1992). “General Local Search Heuristics in Combinatorial Optimization: A Tutorial.” Belgian Journal of Operational Research, Statistics and Computer Science 32(1/2), 7-67.
Shaffer, S. (1991). “A Rule-Based Expert System for Automated Staff Scheduling.” In Proceedings of the 1991 IEEE International Conference on Systems, Man, and Cybernetics, Charlottesville, VA, USA, 10-13 October 1991, pp. 1691-1696.
Showalter, M.J. and V.A. Mabert. (1988). “An Evaluation of Full-/Part-Time Tour Scheduling Methodology.” International Journal of Operations and Production Management 8(7), 54-71.
Tanomaru, J. (1995). “Staff Scheduling by a Genetic Algorithm with Heuristic Operators.” In Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, Vol. 1, Perth, Australia, 29 November-1 December 1995, pp. 456-461.
Taylor, P. and S.A. Huxley. (1989). “A Break from Tradition for the San Francisco Police: Patrol Officer Scheduling Using an Optimization-Based Decision Support Tool.” Interfaces 19(1), 4-24.
Thompson, G.M. (1990). “Shift Scheduling in Services when Employees Have Limited Availability: An LP Approach.” Journal of Operations Management 9(3), 352-370.
Thompson, G.M. (1992). “Improving the Utilization of Front-Line Service Delivery Personnel.” Decision Sciences 23(5), 1072-1098.
Thompson, G.M. (1993). “Representing Employee Requirements in Labour Tour Scheduling.” Omega 21(6), 657-671.
Thompson, G.M. (1995a). “Labor Scheduling Using NPV Estimates of the Marginal Benefit of Additional Labor Capacity.” Journal of Operations Management 13(1), 67-86.
Thompson, G.M. (1995b). “Improved Implicit Optimal Modeling of the Shift Scheduling Problem.” Management Science 41(4), 595-607.
Thompson, G.M. (1996). “Controlling Action Times in Daily Workforce Schedules.” Cornell Hotel and Restaurant Administration Quarterly 37(2), 82-96.
Thompson, G.M. (1997a). “Assigning Telephone Operators to Shifts at New Brunswick Telephone Company.” Interfaces 27(4), 1-11.
Thompson, G.M. (1997b). “Labor Staffing and Scheduling Models for Controlling Service Levels.” Naval Research Logistics 44(8), 719-740.
Thompson, G.M. (1998a). “Labor Scheduling, Part 1: Forecasting Demand.” Cornell Hotel and Restaurant Administration Quarterly 39(5), 22-31.
Thompson, G.M. (1998b). “Labor Scheduling, Part 2: Knowing How Many On-duty Employees to Schedule.” Cornell Hotel and Restaurant Administration Quarterly 39(6), 26-37.
Thompson, G.M. (1999a). “Labor Scheduling, Part 3: Developing a Workforce Schedule.” Cornell Hotel and Restaurant Administration Quarterly 40(1),86-96.
Thompson, G.M. (1999b). “Labor Scheduling, Part 4: Controlling Workforce Schedules in Real Time.” Cornell Hotel and Restaurant Administration Quarterly 40(3), 85-96.
Tien, J.M. and A. Kamiyama. (1982). “On Manpower Scheduling Algorithms.” SIAM Review 24(3), 275-287.
Vakharia, A.J., H.S. Selim, and R.R. Husted. (1992). “Efficient Scheduling of Part-Time Employees.” Omega 20(2), 201-213.
Van Den Berg, Y. and D. Panton. (1994). “Personnel Shift Assignment: Existence Conditions and Network Models.” Networks 24(7), 385-394.
Vaughan, T.S. (1996). “Shift Scheduling with On-call Labor.” In Proceedings of the 1996 27th Annual Meeting of the Decision Science Institute, Atlanta, GA, 24-26 November 1996, Vol. 3, pp. 1611-1613.
Vaughan, T.S. (2000). “On-call Labor Scheduling.” International Journal of Operations and Quantitative Management 6(1), 1-22.
Yura, K. (1994). “Production Scheduling to Satisfy Worker's Preferences for Days off and Overtime under Due-Date Constraints.” International Journal of Production Economics 33(1-3), 265-270.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alfares, H.K. Survey, Categorization, and Comparison of Recent Tour Scheduling Literature. Annals of Operations Research 127, 145–175 (2004). https://doi.org/10.1023/B:ANOR.0000019088.98647.e2
Issue Date:
DOI: https://doi.org/10.1023/B:ANOR.0000019088.98647.e2