×

A two-stage stochastic programming approach for multi-activity tour scheduling. (English) Zbl 1375.90142

Summary: This paper addresses a discontinuous multi-activity tour scheduling problem under demand uncertainty and when employees have identical skills. The problem is formulated as a two-stage stochastic programming model, where first-stage decisions correspond to the assignment of employees to weekly tours, while second-stage decisions are related to the allocation of work activities and breaks to daily shifts. A multi-cut L-shaped method is presented as a solution approach. Computational results on real-based and randomly generated instances show that the use of the stochastic model helps to reduce understaffing and overstaffing costs, when compared with the expected-value problem solutions.

MSC:

90B36 Stochastic scheduling theory in operations research
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alfares, H. K., Survey, categorization, and comparison of recent tour scheduling literature, Annals of Operations Research, 127, 1-4, 145-175 (2004) · Zbl 1087.90023
[2] Aykin, T., Optimal shift scheduling with multiple break windows, Management Science, 42, 4, 591-602 (1996) · Zbl 0880.90065
[3] Bard, J. F.; Morton, D. P.; Wang, Y. M., Workforce planning at USPS mail processing and distribution centers using stochastic optimization, Annals of Operations Research, 155, 1, 51-78 (2007) · Zbl 1145.90032
[4] Bechtold, S. E.; Showalter, M. J., A methodology for labor scheduling in a service operating system, Decision Sciences, 18, 1, 89-107 (1987)
[5] Birge, J. R.; Louveaux, F. V., A multicut algorithm for two-stage stochastic linear programs, European Journal of Operational Research, 34, 3, 384-392 (1988) · Zbl 0647.90066
[6] Boyer, V.; Gendron, B.; Rousseau, L.-M., A branch-and-price algorithm for the multi-activity multi-task shift scheduling problem, Journal of Scheduling, 17, 2, 185-197 (2014) · Zbl 1297.90032
[7] Campbell, G. M., A two-stage stochastic program for scheduling and allocating cross-trained workers, Journal of the Operational Research Society, 62, 6, 1038-1047 (2011)
[8] Côté, M.-C.; Gendron, B.; Quimper, C.-G.; Rousseau, L.-M., Formal languages for integer programming modeling of shift scheduling problems, Constraints, 16, 1, 54-76 (2011) · Zbl 1215.90026
[9] Côté, M.-C.; Gendron, B.; Rousseau, L.-M., Grammar-based integer programming models for multiactivity shift scheduling, Management Science, 57, 1, 151-163 (2011) · Zbl 1214.90077
[10] Côté, M.-C.; Gendron, B.; Rousseau, L.-M., Grammar-based column generation for personalized multi-activity shift scheduling, INFORMS Journal on Computing, 25, 3, 461-474 (2013)
[11] Dahmen, S.; Rekik, M., Solving multi-activity multi-day shift scheduling problems with a hybrid heuristic, Journal of Scheduling, 18, 2, 207-223 (2015) · Zbl 1312.90020
[12] De Bruecker, P.; Van den Bergh, J.; Beliën, J.; Demeulemeester, E., Workforce planning incorporating skills: State of the art, European Journal of Operational Research, 243, 1, 1-16 (2015) · Zbl 1346.90470
[13] Demassey, S.; Pesant, G.; Rousseau, L.-M., A cost-regular based hybrid column generation approach, Constraints, 11, 4, 315-333 (2006) · Zbl 1117.90066
[14] Detienne, B.; Péridy, L.; Pinson, É.; Rivreau, D., Cut generation for an employee timetabling problem, European Journal of Operational Research, 197, 3, 1178-1184 (2009) · Zbl 1176.90413
[15] Easton, F. F.; Mansour, N., A distributed genetic algorithm for deterministic and stochastic labor scheduling problems, European Journal of Operational Research, 118, 3, 505-523 (1999) · Zbl 0933.90028
[16] Easton, F. F.; Rossin, D. F., A stochastic goal program for employee scheduling, Decision Sciences, 27, 3, 541-568 (1996)
[17] Ernst, A.; Jiang, H.; Krishnamoorthy, M.; Owens, B.; Sier, D., An annotated bibliography of personnel scheduling and rostering, Annals of Operations Research, 127, 21-144 (2004) · Zbl 1090.90078
[18] Ernst, A.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, 1, 3-27 (2004) · Zbl 1053.90034
[19] Kim, K.; Mehrotra, S., A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Operations Research, 63, 6, 1431-1451 (2015) · Zbl 1334.90092
[20] Lequy, Q.; Bouchard, M.; Desaulniers, G.; Soumis, F.; Tachefine, B., Assigning multiple activities to work shifts, Journal of Scheduling, 15, 2, 239-251 (2012)
[21] Lewis, P. A.; Shedler, G. S., Simulation of nonhomogeneous poisson processes by thinning, Naval Research Logistics Quarterly, 26, 3, 403-413 (1979) · Zbl 0497.60003
[22] Magnanti, T. L.; Wong, R. T., Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research, 29, 3, 464-484 (1981) · Zbl 0455.90064
[23] McDaniel, D.; Devine, M., A modified Benders’ partitioning algorithm for mixed integer programming, Management Science, 24, 3, 312-319 (1977) · Zbl 0371.90102
[24] Pacqueau, R.; Soumis, F., Shift scheduling under stoczhastic demand, Technical Report G-2014-46 (2014), GERAD
[25] Papadakos, N., Practical enhancements to the Magnanti-Wong method, Operations Research Letters, 36, 4, 444-449 (2008) · Zbl 1155.90432
[26] Parisio, A.; Jones, C. N., A two-stage stochastic programming approach to employee scheduling in retail outlets with uncertain demand, Omega, 53, 97-103 (2015)
[27] Punnakitikashem, P.; Rosenberber, J. M.; Buckley-Behan, D. F., A stochastic programming approach for integrated nurse staffing and assignment, IIE Transactions, 45, 10, 1059-1076 (2013)
[28] Quimper, C.-G.; Rousseau, L.-M., A large neighbourhood search approach to the multi-activity shift scheduling problem, Journal of Heuristics, 16, 3, 373-392 (2010) · Zbl 1187.90141
[29] Quimper, C.-G.; Walsh, T., Decomposing global grammar constraints, Principles and practice of constraint programming, 590-604 (2007), Springer · Zbl 1145.68529
[30] Restrepo, M. I.; Gendron, B.; Rousseau, L.-M., Combining Benders decomposition and column generation for multiactivity tour scheduling, Technical Report 57 (2015), CIRRELT
[31] Restrepo, M. I.; Gendron, B.; Rousseau, L.-M., Branch-and-price for multi-activity tour scheduling, INFORMS Journal on Computing, 28, 2, 1-17 (2016)
[32] Restrepo, M. I.; Lozano, L.; Medaglia, A. L., Constrained network-based column generation for the multi-activity shift scheduling problem, International Journal of Production Economics, 140, 1, 466-472 (2012)
[33] Ritzman, L. P.; Krajewsky, L. J.; Showalter, M. J., The disaggregation of aggregate manpower plans, Management Science, 22, 11, 1204-1214 (1976)
[34] Robbins, T. R.; Harrison, T. P., A stochastic programming model for scheduling call centers with global service level agreements, European Journal of Operational Research, 207, 3, 1608-1619 (2010) · Zbl 1206.90052
[35] Song, H.; Huang, H.-C., A successive convex approximation method for multistage workforce capacity planning problem with turnover, European Journal of Operational Research, 188, 1, 29-48 (2008) · Zbl 1135.90009
[36] Van den Bergh, J.; Beliën, J.; De Bruecker, P.; Demeulemeester, E.; De Boeck, L., Personnel scheduling: A literature review, European Journal of Operational Research, 226, 3, 367-385 (2012) · Zbl 1292.90001
[37] Van Slyke, R. M.; Wets, R., L-shaped linear programs with applications to optimal control and stochastic programming, SIAM Journal on Applied Mathematics, 17, 4, 638-663 (1969) · Zbl 0197.45602
[38] Wolsey, L. A.; Nemhauser, G. L., Integer and combinatorial optimization (1999), John Wiley & Sons · Zbl 0469.90052
[39] Zhu, X.; Sherali, H. D., Two-stage workforce planning under demand fluctuations and uncertainty, Journal of the Operational Research Society, 60, 1, 94-103 (2009) · Zbl 1168.90533
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.