Personnel scheduling: models and complexity. (English) Zbl 1213.90151

Brucker, Peter; Qu, Rong; Burke, Edmund

Eur. J. Oper. Res. 210, No. 3, 467-473 (2011).

Summary: Due to its complexity, its challenging features, and its practical relevance, personnel scheduling has been heavily investigated in the last few decades. However, there is a relatively low level of study on models and complexity in these important problems. In this paper, we present mathematical models which cover specific aspects in the personnel scheduling literature. Furthermore, we address complexity issues by identifying polynomial solvable and NP-hard special cases.

MSC:

90B70	Theory of organizations, manpower planning in operations research
90B35	Deterministic scheduling theory in operations research

Keywords:

complexity; mathematical model; personnel scheduling

References:

[1]	Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows: theory, algorithms, and applications, (1993), Prentice Hall · Zbl 1201.90001
[2]	Bailey, J., Integrated days off and shift personnel scheduling, Computers & industrial engineering, 9, 4, 395-404, (1985)
[3]	Bailey, J.; Alfares, H.; Lin, W.Y., Optimization and heuristic models to integrate project task and manpower scheduling, Computers & industrial engineering, 29, 1-4, 473-476, (1995)
[4]	Bard, J.F., Selecting the appropriate input data set when configuring a permanent workforce, Computers & industrial engineering, 47, 371-389, (2004)
[5]	J.F. Bard, H.W. Purnomo, Real-time scheduling for nurses in response to demand fluctuations and personnel shortages, in: M. Trick, E. Burke (Eds.), Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, Pittsburgh, 2004, pp. 67-87.
[6]	Bard, J.F.; Binici, C.; deSilva, A.H., Staff scheduling at the united states postal service, Computers and opertions research, 30, 745-771, (2003) · Zbl 1026.90038
[7]	Bilgin, B.; De Causmaecker, P.; Rossie, B.; Vanden Berghe, G., Local search neighbourhoods to deal with a novel nurse rostering model, () · Zbl 1251.90116
[8]	Blochliger, I., Modeling staff scheduling problems. A tutorial, European journal of operational research, 158, 533-542, (2004) · Zbl 1056.90056
[9]	Bodin, L.; Golden, B.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews – the state of the art, Computers and opertions research, 10, 2, 63-211, (1983)
[10]	Brucker, P.; Knust, S., Complex scheduling, (2006), Springer Berlin · Zbl 1154.90002
[11]	Brucker, P., Scheduling algorithms, (2007), Springer Berlin · Zbl 1126.90001
[12]	P. Brucker, R. Qu, E. Burke, G. Post, A decomposition, construction and post-processing approach for a specific nurse rostering problem, in: Proceedings of the 2nd Multidisciplinary Conference on Scheduling: Theory and Applications (MISTA 2005), 18-21 July, 2005, pp. 397-406.
[13]	Burke, E.K.; De Causmaecker, P.; Vanden Berghe, G.; Van Landeghem, H., The state of the art of nurse rostering, Journal of scheduling, 7, 6, 441-499, (2004) · Zbl 1154.90422
[14]	Caprara, A.; Monaci, M.; Toth, P., Models and algorithms for a staff scheduling problem, Mathematical programming, series B, 98, 445-476, (2003) · Zbl 1160.90471
[15]	Dantzig, D., A comment on edie’s traffic delay at toll booths, Operations research, 2, 339-341, (1954)
[16]	Dantzig, M.L.; Fulkerson, D.R., Minimizing the number of tankers to meet a fixed schedule, Naval research logistics, 1, 217-222, (1954)
[17]	P. De Causmaecker, P. Demeester, G. Vanden Berghe, B. Verbeke, Analysis of real-world personnel scheduling problems, in: Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, 18th-20th August 2004, Pittsburgh, PA, USA, 2005, pp. 183-198.
[18]	P. De Causmaecker, G. Vanden Berghe, Towards a reference model for timetabling and rostering, Annals of Operations Research, 2010. doi:10.1007/s10479-010-0721-2 · Zbl 1251.90129
[19]	Dowsland, K.A., Nurse scheduling with tabu search and strategic oscillation, European journal of operational ressearch, 106, 393-407, (1998) · Zbl 0991.90055
[20]	Ernst, A.T.; Jiang, H.; Krishnamoorthy, M.; Owens, B.; Sier, D., An annotated bibliography of personnel scheduling and rostering, Annals of OR, 127, 21-144, (2004) · Zbl 1090.90078
[21]	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, 153, 1, 3-27, (2004) · Zbl 1053.90034
[22]	Ertogral, K.; Bamuqabel, B., Developing staff schedules for a bilingual telecommunication call center with flexible workers, Computers & industrial engineering, 54, 118-127, (2008)
[23]	Franz, L.S.; Baker, H.M.; Leong, G.K.; Rakes, T.R., A mathematical model for scheduling and staffing multiclinic health regions, European journal of operational research, 41, 277-289, (1989)
[24]	Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco · Zbl 0411.68039
[25]	Gutjahr, W.J.; Katzensteiner, S.; Reiter, P.; Stummer, C.; Denk, M., Multi-objective decision analysis for competence-oriented project portfolio selection, European journal of operational research, 205, 3, 670-679, (2010) · Zbl 1188.90127
[26]	S. Haspeslagh, P. De Causmaecker, M. Stolevik, A. Schaerf, First International Nurse Rostering Competition 2010, in: Proceedings of the 8th International Conference for the Practice and Theory of Automated Timetabling, Northern Ireland, 10th-13th August, 2010, pp. 498-501. · Zbl 1301.90036
[27]	Kroon, L.G.; Salomon, M.; Van Wassenhove, L.N., Exact and approximation algorithms for the tactical fixed interval scheduling problem, Operations research, 45, 624-638, (1997) · Zbl 0887.90089
[28]	Lau, H.C., On the complexity of manpower shift scheduling, Computers and operations research, 23, 1, 93-102, (1996) · Zbl 0838.90065
[29]	Merciera, A.; Cordeau, J.-F.; Soumis, F., A computational study of benders decomposition for the integrated aircraft routing and crew scheduling problem, Computers & operations research, 32, 1451-1476, (2005) · Zbl 1122.90355
[30]	Orden, A., The transhipment problem, Management science, 2, 3, 276-285, (1956) · Zbl 0995.90549
[31]	R. Robinson, R. Sorli, Y. Zinder, Personnel scheduling with time windows and preemptive tasks, in: Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, 18th-20th August 2004, Pittsburgh, PA, USA, 2005, pp. 561-566.
[32]	Rodrigues, M.M.; de Souza, C.C.; Moura, A.V., Vehicle and crew scheduling for urban bus lines, European journal of operational research, 170, 3, 844-862, (2006) · Zbl 1091.90024
[33]	Segal, M., The operator scheduling problem: a network flow approach, Operations research, 22, 808-823, (1974) · Zbl 0283.90024
[34]	Tiwari, V.; Patterson, J.H.; Mabert, V.A., Scheduling projects with heterogeneous resources to meet time and quality objectives, European journal of operational research, 193, 780-790, (2009) · Zbl 1175.90195
[35]	Weide, O.; Ryan, D.; Ehrgott, M., An iterative approach to robust and integrated aircraft routing and crew scheduling, Computers & operations research, 37, 833-844, (2010) · Zbl 1177.90190