Abstract.
We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aykin, T.: Optimal shift scheduling with multiple break windows. Management Science 42, 591–602 (1996)
Aykin, T.: A comparative evaluation of modeling approaches to the labor shift scheduling problem. European Journal of Operational Research 125, 381–397 (2000)
Balakrishnan, N., Wong, R.T.: A network model for the rotating workforce scheduling problem. Networks 20, 25–42 (1990)
Barnhart, C., Johnson, E.L., Nemhauser, G.L., Vance, P.H.: Crew scheduling. In R.W. Hall, editor, Handbooks of Transportation Science, pages 493–521, Norwell, MA, 1999. Kluwer Academic Publisher
Bartholdi III, J.J.: A guaranteed-accuracy round-off algorithm for cyclic scheduling and set covering. Operations Research 29, 501–510 (1981)
Bartholdi III, J.J., Orlin, J.B., Ratliff, H.D.: Cyclic scheduling via integer programs with circular ones. Operations Research 28, 1074–1085 (1980)
Beaumont, N.: Scheduling staff using mixed integer programming. European European Journal of Operational Research 98, 473–484 (1997)
Bechtold, S.E., Jacobs, L.W.: The equivalence of general set-covering and implicit integer programming formulations for shift scheduling. Naval Research Logistics 43, 233–250 (1996)
Billionnet, A.: Integer programming to schedule a hierarchical workforce with variable demands. European Journal of Operational Research 114, 105–114 (1999)
Brusco, M.J., Jacobs, L.W.: Personnel tour scheduling when starting-time restrictions are present. Management Science 44, 534–547 (1998)
Brusco, M.J., Jacobs, L.W.: Optimal models for meal-break and start-time flexibility in continuous tour scheduling. Management Science 46, 1630–1641 (2000)
Brusco, M.J., Jacobs, L.W., Bongiorno, R.J., Lynos, D.V., Tang, B.: Improving personnel scheduling at airline stations. Operations Research 43, 741–751 (1995)
Caprara, A., Fischetti, M., Toth, P., Vigo, D., Guida, P.L.: Algorithms for railway crew management. Mathematical Programming 79, 125–141 (1997)
Cook, W.J., Cunningham, W.H., Pulleyblank, W.R., Schrijver, A.: Combinatorial Optimization. John Wiley & Sons, Inc, 1998
Cormen, T.H., Leiserson, C.E., Rivest, R.R.: Introduction to Algorithms. MIT Press, 1990
Ernst, A.T., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: a review of applications, methods and models. European Journal of Operational Research. (to appear)
Gamache, M., Soumis, F., Marquis, G., Desrosiers, J.: A column generation approach for large-scale aircrew rostering problems. Operations Research 47, 247–263 (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco, 1979
Geoffrion, A.M.: Lagrangean relaxation for integer programming. Mathematical Programming Study 2, 82–114 (1974)
Jacobs, L.W., Brusco, M.J.: Overlapping start-time bands in implicit tour scheduling. Management Science 42, 1247–1259 (1996)
Jarrah, A.I.Z., Bard, J.F., deSilva, A.: Solving large-scale tour scheduling problems. Management Science 40, 1124–1144 (1994)
Jaumard, B., Semet, F., Vovor, T.: A generalized linear programming model for nurse scheduling. European Journal of Operational Research 107, 1–18 (1998)
Marcotte, O.: An instance of the cutting stock problem for which the rounding property does not hold. Operations Research Letters 4, 239–243 (1986)
Mehrotra, A., Murphy, K.E., Trick, M.A.: Optimal shift scheduling: a branch-and-price approach. Naval Research Logistics 47, 185–200 (2000)
Thompson, G.M.: Improved implicit optimal modeling of the labor shift scheduling problem. Management Science 41, 595–607 (1995)
Thompson, G.M.: Labor staffing and scheduling models for controlling service levels. Naval Research Logistics 44, 719–740 (1997)
Tien, J.M., Kamiyama, A.: On manpower scheduling algorithms. SIAM Review 24, 275–287 (1982)
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59
Rights and permissions
About this article
Cite this article
Caprara, A., Monaci, M. & Toth, P. Models and algorithms for a staff scheduling problem. Math. Program., Ser. B 98, 445–476 (2003). https://doi.org/10.1007/s10107-003-0413-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-003-0413-7