A classification scheme for integrated staff rostering and scheduling problems
Paul, Mareike1 ; Knust, Sigrid1
1 Institute of Computer Science, University of Osnabrück, 49069 Osnabrück, Germany.
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 393-412.

In the last decades job scheduling, staff rostering and staff assignment have received considerable attention, as have combinations of these problems. However, given the wide range of variants of all three basic problems, the number of combinations is immense. In this paper we introduce a new classification scheme for integrated staff rostering and job scheduling problems, extending existing schemes for project and machine scheduling. We provide some elementary reductions and show how problems studied in the literature fit into this new classification scheme. Furthermore, some complexity results are presented.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014052
Classification : 90B35, 68Q25
Mots-clés : Scheduling, rostering, assignment, staff, classification scheme, complexity
Paul, Mareike 1 ; Knust, Sigrid 1

1 Institute of Computer Science, University of Osnabrück, 49069 Osnabrück, Germany. 
@article{RO_2015__49_2_393_0,
     author = {Paul, Mareike and Knust, Sigrid},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {A classification scheme for integrated staff rostering and scheduling problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {393--412},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014052},
     zbl = {1310.90049},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2014052/}
}
TY  - JOUR
AU  - Paul, Mareike
AU  - Knust, Sigrid
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - A classification scheme for integrated staff rostering and scheduling problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 393
EP  - 412
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2014052/
DO  - 10.1051/ro/2014052
LA  - en
ID  - RO_2015__49_2_393_0
ER  - 
%0 Journal Article
%A Paul, Mareike
%A Knust, Sigrid
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T A classification scheme for integrated staff rostering and scheduling problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 393-412
%V 49
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2014052/
%R 10.1051/ro/2014052
%G en
%F RO_2015__49_2_393_0
Paul, Mareike; Knust, Sigrid. A classification scheme for integrated staff rostering and scheduling problems. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 393-412. doi : 10.1051/ro/2014052. http://www.numdam.org/articles/10.1051/ro/2014052/

H. Alfares, J. Bailey and Wen Y. Lin, Optimization and heuristic models to integrate project task and manpower scheduling. Comput. Ind. Eng. 29 (1995) 473–476. | DOI

H.K. Alfares, J.E. Bailey and W.Y. Lin, Integrated project operations and personnel scheduling with multiple labour classes. Prod. Plan. Control 10 (1999) 570–578. | DOI

E.M. Arkin and E.B. Silverberg, Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18 (1987) 1–8. | DOI | Zbl

C. Artigues, M. Gendreau and L.-M. Rousseau, A flexible model and a hybrid exact method for integrated employee timetabling and production scheduling, in Proc. of the 6th International Conference on Practice and Theory of Automated Timetabling (PATAT), Vol. 3867. Springer (2007) 67–84.

C. Artigues, M. Gendreau, L.-M. Rousseau and A. Vergnaud, Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound. Comput. Oper. Res. 36 (2009) 2330–2340. | DOI | Zbl

R.M. Awad and J.W. Chinneck, Proctor assignment at Carleton University. Interfaces 28 (1998) 58–71. | DOI

O. Bellenguez and E. Néron, Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills, in Proc. of the 5th International Conference on Practice and Theory of Automated Timetabling (PATAT), Vol. 3616. Springer (2005) 229–243.

O. Bellenguez-Morineau and E. Néron, A branch-and-bound method for solving multi-skill project scheduling problem. RAIRO–Oper. Res. 41 (2007) 155–170. | DOI | Numdam | Zbl

S. Bertels and T. Fahle, A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Comput. Oper. Res. 33 (2006) 2866–2890. | DOI | Zbl

J. Błażewicz, J.K. Lenstra and A.H.G. Rinnooy Kan, Scheduling subject to resource constraints: classification and complexity. Discrete Appl. Math. 5 (1983) 11–24. | DOI | Zbl

J. Błażewicz, K.H. Ecker, E. Pesch, G. Schmidt and J. Weglarz, Handbook on Scheduling: From Theory to Applications. Springer (2007). | Zbl

N. Boysen, M. Fliedner and A. Scholl, A classification of assembly line balancing problems. Eur. J. Oper. Res. 183 (2007) 674–693. | DOI | Zbl

P. Brucker, A. Drexl, R. Möhring, K. Neumann and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods. Eur. J. Oper. Res. 112 (1999) 3–41. | DOI | Zbl

P. Brucker and S. Knust, Complex Scheduling. Springer, 2nd edition (2012). | MR | Zbl

P. Brucker and S. Knust, Complexity results for scheduling problems. http://www.inf.uos.de/knust/class/.

P. Brucker, R. Qu and E.K. Burke, Personnel scheduling: Models and complexity. Eur. J. Oper. Res. 210 (2011) 467–473. | DOI | MR | Zbl

P. Brucker and R. Qu, Network flow models for intraday personnel scheduling problems. Ann. Oper. Res. 218 (2014) 107–114. | DOI | MR | Zbl

J. Brunner, J. Bard and R. Kolisch, Flexible shift scheduling of physicians. Health Care Manage. Sci. 12 (2009) 285–305. | DOI

J. Brunner, J. Bard and R. Kolisch, Midterm scheduling of physicians with flexible shifts using branch-and-price. IIE Trans. 43 (2010) 84–109. | DOI

E.K. Burke, P. De Causmaecker, G. Vanden Berghe and H. Van Landeghem, The state of the art of nurse rostering. J. Schedul. 7 (2004) 441–499. | DOI | MR | Zbl

P. De Causmaecker and G. Vanden Berghe, A categorisation of nurse rostering problems. J. Schedul. 14 (2011) 3–16. | DOI

M. Desrochers, J.K. Lenstra and M.W.P. Savelsbergh, A classification scheme for vehicle routing and scheduling problems. Eur. J. Oper. Res. 46 (1990) 322–332. | DOI | Zbl

A. Drexl, Scheduling of project networks by job assignment. Manage. Sci. 37 (1991) 1590–1602. | DOI | Zbl

A.T. Ernst, H. Jiang, M. Krishnamoorthy, B. Owens and D. Sier, An annotated bibliography of personnel scheduling and rostering. Ann. Oper. Res. 127 (2004) 21–144. | DOI | MR | Zbl

P.R. Ferreira Jr. and A.L.C. Bazzan, Distributed task scheduling using a swarm intelligence approach. In Proceedings of the 7th Brazilian Meeting on Artificial Intelligence. SBC (2009) 979–988.

M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co. (1990). | Zbl

A.V. Goldberg and R.E. Tarjan, A new approach to the maximum flow problem, in Proc. of the eighteenth annual ACM symposium on Theory of computing, STOC ’86. ACM (1986) 136–146. | MR | Zbl

R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5 (1979) 287–326. | DOI | MR | Zbl

O. Guyon, P. Lemaire, E. Pinson and D. Rivreau, Cut generation for an integrated employee timetabling and production scheduling problem. Eur. J. Oper. Res. 201 (2010) 557–567. | DOI | MR | Zbl

O. Guyon, P. Lemaire, E. Pinson and D. Rivreau, Solving an integrated job-shop problem with human resource constraints. Ann. Oper. Res. 213 (2014) 147–171. | DOI | MR | Zbl

S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (2010) 1–14. | DOI | MR | Zbl

C. Heimerl and R. Kolisch, Scheduling and staffing multiple projects with a multi-skilled workforce. OR Spektrum 32 (2010) 343–368. | DOI | MR | Zbl

J. Herbers, Models and Algorithms for Ground Staff Scheduling on Airports. Ph.D. thesis, Rheinisch-Westfälische Technische Hochschule Aachen (2005).

W. Herroelen, E. Demeulemeester and B. de Reyck, A classification scheme for project scheduling problems, in Project Scheduling – Recent Models, Algorithms and Applications, edited by J. Weglarz. Kluwer Academic Publishers (1998) 1–26.

P. Kilby, The augmented regret heuristic for staff scheduling, in Proceedings of the 16th Australian Society of Operations Research (ASOR 2001), McLaren Vale, South Australia (2001).

A.W.J. Kolen, J.K. Lenstra, C.H. Papadimitriou and F.C.R. Spieksma, Interval scheduling: A survey. Nav. Res. Logist. 54 (2007) 530–543. | DOI | MR | Zbl

G.J. Koop, Multiple shift workforce lower bounds. Manage. Sci. 34 (1988) 1221–1230. | DOI | MR | Zbl

L.G. Kroon, M. Salomon and L.N. Van Wassenhove, Exact and approximation algorithms for the tactical fixed interval scheduling problem. Oper. Res. 45 (1997) 624–638. | DOI | MR | Zbl

H.C. Lau, On the complexity of manpower shift scheduling. Comput. Oper. Res. 23 (1996) 93–102. | DOI | Zbl

J.S. Loucks and F.R. Jacobs, Tour scheduling and task assignment of a heterogeneous work force: A heuristic approach. Dec. Sci. 22 (1991) 719–738. | DOI

S.M. Roberts and L.F. Escudero, Scheduling of plant maintenance personnel. J. Optim. Theor. Appl. 39 (1983) 323–343. | DOI | MR | Zbl

M. Segal, The operator-scheduling problem: A network-flow approach. Oper. Res. 22 (1974) 808–823. | DOI | Zbl

J. Van Den Bergh, J. Belien, P. De Bruecker, E. Demeulemeester and L. De Boeck, Personnel scheduling: A literature review. Eur. J. Oper. Res. 226 (2013) 367–385. | DOI | MR | Zbl

Cité par Sources :