Abstract
The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this paper, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive specialized graph structures that can be searched efficiently. The overall shift scheduling problem can then be solved using a Large Neighbourhood Search. These approaches are able to return near optimal solution on traditional single activity problems and they scale well on large instances containing up to 10 activities.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ahuja, R.K., Ergun, O., Orlin, J.B., Punnen, A.P.: A survey of very large scale neighborhood search techniques. Discrete Appl. Math. 123, 75–102 (2002)
Apt, K.: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)
Aykin, T.: Optimal shift scheduling with multiple break windows. Manag. Sci. 42(4), 591–602 (1996)
Aykin, T.: A composite branch and cut algorithm for optimal shift scheduling with multiple breaks and break windows. J. Oper. Res. Soc. 49(6), 603–615 (1998)
Bechtold, S., Jacobs, L.: Implicit modeling of flexible break assignment in optimal shift scheduling. Manag. Sci. 36(11), 1339–1351 (1990)
Bechtold, S., Jacobs, L.: The equivalence of general set-covering and implicit integer programming formulations for shift scheduling. Nav. Res. Logist. 43(2), 233–249 (1996)
Bonaparte, A., Orlin, J.B.: Using grammars to generate very large scale neighborhoods for the traveling salesman problem and other sequencing problems. In: Integer Programming and Combinatorial Optimization, pp. 437–451 (2005)
Bouchard, M.: Optimisation des pauses dans le problème de fabrication des horaires avec quarts de travail. Memoire de maitrise, Ecole Polytechnique de Montreal (2004)
Brusco, M., Jacobs, L.: A simulated annealing approach to the solution of flexible labor scheduling problems. J. Oper. Res. Soc. 44(12), 1991–1200 (1993)
Cocke, J., Schwartz, J.T.: Programming languages and their compilers: Preliminary notes. Technical Report, Courant Institute of Mathematical Sciences, New York University (1970)
Côté, M.-C., Gendron, B., Rousseau, L.-M.: Modeling the regular constraint with integer programming. In: Fourth International Conference on Integration of AI and OR Techniques in Constraint Programming (CP-AI-OR 07), pp. 29–43 (2007)
Dantzig, G.: A comment on edie’s traffic delay at toll booths. Oper. Res. 2, 339–341 (1954)
Dechter, R.: Constraint Processing. Morgan Kaufmann, San Mateo (2003)
Demassey, S., Pesant, G., Rousseau, L.-M.: A cost-regular based hybrid column generation approach. Constraints 11(4), 315–333 (2006)
Easton, F., Mansour, N.: A distributed genetic algorithm for deterministic and stochastic labor scheduling problems. Eur. J. Oper. Res. 118, 505–523 (1999)
Edie, L.: Traffic delays at toll booths. J. Oper. Res. Soc. Am. 2(2), 107–138 (1954)
Ernst, A., Jiang, H., Krishnamoorthy, M., Owens, B., Sier, D.: An annotated bibliography of personnel scheduling and rostering. Ann. Oper. Res. 127, 21–144 (2004a)
Ernst, A., Jiang, H., Krishnamoorthy, M., Sier, D.: Staff scheduling and rostering: A review of applications, methods and models. Eur. J. Oper. Res. 153, 3–27 (2004b)
Glover, F., McMillan, C.: The general employee scheduling problem: An integration of ms and ai. Comput. Oper. Res. 13(6), 563–573 (1986)
Hopcroft, J., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, Reading (2001)
Kasami, T.: An efficient recognition and syntax-analysis algorithm for context-free languages. Technical Report Scientific Report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA (1965)
Loucks, J.S., Jacobs, F.R.: Our scheduling and task assignment of a heterogeneous wok force: a heuristic approach. Decis. Sci. 22, 719–739 (1991)
Manning, C.D., Schütze, H.: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge (1999)
Mehrotra, A., Murthy, K., Trick, M.: Optimal shift scheduling: A branch-and-price approach. Nav. Res. Logist. 47, 185–200 (2000)
Meyers, C., Orlin, J.B.: Very large-scale neighborhood search techniques in timetabling problems. In: The Practice and Theory of Automated Timetabling VI, pp. 36–52 (2006)
Moondra, S.: An linear programming model for work force scheduling for banks. J. Bank Res. 6, 299–301 (1976)
Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004), pp. 482–495 (2004)
Quimper, C.-G., Walsh, T.: Global grammar constraints. In: Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP 2006), pp. 751–755 (2006)
Quimper, C.-G., Walsh, T.: Decomposing global grammar constraints. In: Principles and Practice of Constraint Programming (CP 2007), pp. 590–604 (2007)
Rekik, M., Cordeau, J.-F., Soumis, F.: Using benders decomposition to implicitly model tour scheduling. Ann. Oper. Res. 118, 111–133 (2004)
Ritzman, L., Krajewski, L.J., Showalter, M.J.: The disaggregation of aggregate manpower plans. Manag. Sci. 22, 1204–1214 (1976)
Rousseau, L.-M., Gendreau, M., Pesant, G.: Using constraint-based operators with variable neighborhood search to solve the vehicle routing problem with time windows. J. Heuristics 8(1), 43–58 (2001)
Sellmann, M.: The theory of grammar constraints. In: Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP 2006), pp. 530–544 (2007)
Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP 1998), pp. 417–431 (1998)
Thompson, G.: Improved implicit optimal modelling of the shift scheduling problem. Manag. Sci. 41(5), 595–607 (1995)
Vatri, E.: Integration de la generation de quart de travail et de l’attribution d’activites. Memoire de maitrise, Ecole Polytechnique de Montreal (2001)
Younger, D.H.: Recognition and parsing of context-free languages in time n 3. Inf. Control 10(2), 189–208 (1967)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Quimper, CG., Rousseau, LM. A large neighbourhood search approach to the multi-activity shift scheduling problem. J Heuristics 16, 373–392 (2010). https://doi.org/10.1007/s10732-009-9106-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-009-9106-6