Assigning multiple activities to work shifts
Tóm tắt
In some companies such as large retail stores, the employees perform different activities (e.g., cashier or clerk in a specific department) to respond to a customer demand for each activity that varies over the planning horizon and must be fulfilled as soon as possible. For a given time period, this demand translates into an ideal number of employees required for the corresponding activity. During a work shift, an employee can be assigned to several activities that are interruptible at any time and subject to operational constraints (required skills, minimum and maximum assignment durations). Given work shifts already assigned to the employees, the multi-activity assignment problem (MAAP) consists of assigning activities to the shifts such that the activity demands are satisfied as best as possible over the planning horizon. In this paper, we propose three integer programming models for the MAAP and develop various heuristics based on mathematical programming techniques. Computational results obtained on randomly generated MAAP instances show that a heuristic column generation method embedded into a rolling horizon procedure provides the best results in general.
Tài liệu tham khảo
Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs: Prentice-Hall.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.
Bouchard, M. (2004). Optimisation de pauses dans le problème de fabrication d’horaires avec quarts de travail. Mémoire de maîtrise, École Polytechnique, Montréal, Canada.
Côté, M.-C., Gendron, B., & Rousseau, L.-M. (2007). Modeling the regular constraint with integer programming. In Lecture notes in computer science : Vol. 4510. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 29–43). Berlin: Springer.
Dantzig, G. B. (1954). A comment on Edie’s “Traffic delays at toll booths”. Journal of the Operations Research Society of America, 2(3), 339–341.
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8, 101–111.
Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). Column generation. New York: Springer.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., Owens, B., & Sier, D. (2004a). An annotated bibliography of personnel scheduling and rostering. Annals of Operations Research, 127(1), 21–144.
Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004b). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.
Gale, D. (1957). A theorem on flows in networks. Pacific Journal of Mathematics, 7, 1073–1082.
Haase, K., Desaulniers, G., & Desrosiers, J. (2001). Simultaneous vehicle and crew scheduling in urban mass transit systems. Transportation Science, 35(3), 286–303.
Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, 53(6), 1007–1023.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. New York: Wiley.
Omari, Z. (2002). Attribution des activités aux employés travaillant sur des quarts. Mémoire de maîtrise, École Polytechnique, Montréal, Canada.
Rekik, M., Cordeau, J. F., & Soumis, F. (2009). Implicit shift scheduling with multiple breaks and work stretch duration restrictions. Journal of Scheduling, to appear. doi:10.1007/s10951-009-0114-z.
Vatri, E. (2001). Intégration de la génération de quarts de travail et de l’attribution d’activités. Mémoire de maîtrise, École Polytechnique, Montréal, Canada.