A branch-and-price approach for large-scale employee tour scheduling problems. (English) Zbl 1145.90036
Summary: We present a new methodology for solving large-scale employee tour scheduling problems. An integer programming model is proposed where tours are decomposed into shifts and start times. This formulation can model complex shift and start time rules for both continuous and discontinuous scheduling problems. A branch-and-price approach is devised to solve this model efficiently. The methodology was tested on the largest tour scheduling problems found in the open literature. In comparison with an alternative implicit model, our approach showed superior computational performance.
MSC:
| 90B70 | Theory of organizations, manpower planning in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Software:
ABACUSReferences:
| [1] | ABACUS (1999). ABACUS 2.3. User’s guide and reference manual. http://www.informatik.uni-koeln.de/abacus/ . |
| [2] | Bard, J. F., Binici, C., & deSilva, A. H. (2003). Staff scheduling at the united states postal service. Computers and Operations Research, 30, 745–771. · Zbl 1026.90038 · doi:10.1016/S0305-0548(02)00048-5 |
| [3] | Bartholdi, J. J. (1981). A guaranteed-accuracy round-off algorithm for cyclic scheduling and set covering. Operations Research, 29, 501–510. · Zbl 0466.90037 · doi:10.1287/opre.29.3.501 |
| [4] | Bechtold, S. E., & Jacobs, L. W. (1990). Implicit modeling of flexible break assignments in optimal shift scheduling. Management Science, 36, 1339–1351. · doi:10.1287/mnsc.36.11.1339 |
| [5] | Bechtold, S. E., Brusco, M. J., & Showalter, M. J. (1991). A comparative evaluation of labor tour scheduling methods. Decision Sciences, 22, 683–699. · doi:10.1111/j.1540-5915.1991.tb00359.x |
| [6] | Bechtold, S. E., & Brusco, M. J. (1994). Working set generation methods for labor tour scheduling. European Journal of Operational Research, 74, 540–551. · Zbl 0925.90218 · doi:10.1016/0377-2217(94)90230-5 |
| [7] | Brusco, M. J., & Jacobs, L. W. (1998). Personnel tour scheduling when starting-time restriction are present. Management Science, 44, 534–547. · Zbl 0989.90058 · doi:10.1287/mnsc.44.4.534 |
| [8] | Brusco, M. J., & Jacobs, L. W. (2000). Optimal models for meal-break and start-time flexibility in continuous tour scheduling. Management Science, 46, 1630–1641. · Zbl 1232.90204 · doi:10.1287/mnsc.46.12.1630.12074 |
| [9] | Burns, R. N., & Carter, M. W. (1985). Work force size and single shift schedules with variable demands. Management Science, 31, 599–607. · doi:10.1287/mnsc.31.5.599 |
| [10] | Cezik, T., Gunluk, O., & Luss, H. (2001). An integer programming model for the weekly tour scheduling problem. Naval Research Logistics, 48, 607–624. · Zbl 1005.90033 · doi:10.1002/nav.1037 |
| [11] | Dantzig, G. B. (1954). A comment on Edie’s traffic delays at toll booths. Operations Research Journal, 3, 339–341. · doi:10.1287/opre.2.3.339 |
| [12] | Isken, M. W. (2004). An implicit tour scheduling model with applications in health care. Annals of Operations Research, 128, 91–110. · Zbl 1056.90068 · doi:10.1023/B:ANOR.0000019100.08333.a7 |
| [13] | Jacobs, L. W., & Brusco, M. J. (1996). Overlapping start-time bands in implicit tour scheduling. Management Science, 42, 1247–1259. · Zbl 0880.90085 · doi:10.1287/mnsc.42.9.1247 |
| [14] | Jarrah, A. I. Z., Bard, J. F., & deSilva, A. H. (1994). Solving large-scale tour scheduling problems. Management Science, 40, 1124–1144. · Zbl 0818.90043 · doi:10.1287/mnsc.40.9.1124 |
| [15] | Mabert, V. A., & Showalter, M. J. (1988). Measuring the impact of part-time workers in service organizations. Journal of Operations Management, 9(2), 209–229. · doi:10.1016/0272-6963(90)90096-V |
| [16] | Mehrotra, A., Murphy, K. E., & Trick, M. A. (2000). Optimal shift scheduling: a branch-and-price approach. Naval Research Logistics, 47, 185–200. · Zbl 0972.90032 · doi:10.1002/(SICI)1520-6750(200004)47:3<185::AID-NAV1>3.0.CO;2-7 |
| [17] | Moondra, S. L. (1976). An LP model for work force scheduling for banks. Journal of Bank Research, 7, 299–301. |
| [18] | Morris, J. G., & Showalter, M. J. (1983). Simple approaches to shift, days-off and tour scheduling problems. Management Science, 29, 942–950. · doi:10.1287/mnsc.29.8.942 |
| [19] | Ni, H. (2003). A branch-and-price approach to employee tour scheduling. D.Sc. thesis, The George Washington University, Washington DC, USA. |
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.
