Solution approaches to large shift scheduling problems
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 229-258.

This paper considers large shift scheduling problems with different shift start times and lengths, fractionable breaks and work stretch duration restrictions. Two solution approaches are proposed to solve the problems over a multiple-day planning horizon. The first approach is based on a local branching strategy and the second one is based on a temporal decomposition of the problem. Local branching is very efficient in finding good feasible solutions when compared to a classical branch-and-bound procedure. However, the decomposition approach has the advantage of yielding feasible solutions in short computing times, even for difficult instances.

DOI : 10.1051/ro:2008006
Classification : 90C10, 90C11, 90C29
Mots-clés : shift scheduling, flexibility, fractionable breaks, work stretch restrictions, forward and backward constraints, local branching, heuristic 
@article{RO_2008__42_2_229_0,
     author = {Rekik, Monia and Cordeau, Jean-Fran\c{c}ois and Soumis, Fran\c{c}ois},
     title = {Solution approaches to large shift scheduling problems},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {229--258},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {2},
     year = {2008},
     doi = {10.1051/ro:2008006},
     mrnumber = {2431401},
     zbl = {1154.90483},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro:2008006/}
}
TY  - JOUR
AU  - Rekik, Monia
AU  - Cordeau, Jean-François
AU  - Soumis, François
TI  - Solution approaches to large shift scheduling problems
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 229
EP  - 258
VL  - 42
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro:2008006/
DO  - 10.1051/ro:2008006
LA  - en
ID  - RO_2008__42_2_229_0
ER  - 
%0 Journal Article
%A Rekik, Monia
%A Cordeau, Jean-François
%A Soumis, François
%T Solution approaches to large shift scheduling problems
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 229-258
%V 42
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro:2008006/
%R 10.1051/ro:2008006
%G en
%F RO_2008__42_2_229_0
Rekik, Monia; Cordeau, Jean-François; Soumis, François. Solution approaches to large shift scheduling problems. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 2, pp. 229-258. doi : 10.1051/ro:2008006. http://archive.numdam.org/articles/10.1051/ro:2008006/

[1] I. Addou and F. Soumis. Bechtold-Jacobs generalized model for shift scheduling with extraordinary overlap. Technical report, GERAD, HEC Montréal, (2004).

[2] T. Aykin. Optimal shift scheduling with multiple break windows. Manage. Sci. 42 (1996) 591-602. | Zbl

[3] T. Aykin. A composite branch and cut algorithm for optimal shift scheduling with multiple breaks and break windows. J. Oper. Res. Soc. 49 (1998) 603-615. | Zbl

[4] T. Aykin. A comparative evaluation of modeling approaches to the labor shift scheduling problem. Eur. J. Oper. Res. 125 (2000) 381-397. | Zbl

[5] S.E. Bechtold and L.W. Jacobs. Implicit modeling of flexible break assignments in optimal shift scheduling. Manage. Sci. 36 (1990) 1339-1351.

[6] S.E. Bechtold and L.W. Jacobs. Labor utilization effects of labor scheduling flexibility alternatives in a tour scheduling environment. Decision Sciences 24 (1993) 148-166.

[7] M.J. Brusco and L.W. Jacobs. Cost analysis of alternative formulations for personnel scheduling in continuously operating organisations. Eur. J. Oper. Res. 86 (1995) 249-261. | Zbl

[8] M.J. Brusco and L.W. Jacobs. Starting-time decisions in labor tour scheduling: an experimental analysis and case study. Eur. J. Oper. Res. 131 (2001) 459-475. | Zbl

[9] T. Çezik and O. Günlük. Reformulating linear programs with transportation constraints- with applications to workforce scheduling. Naval Research Logistics 51 (2004) 275-296. | MR | Zbl

[10] E. Danna, E. Rothberg, and C. Le Pape. Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102 (2005) 71-90. | MR | Zbl

[11] G.B. Dantzig. A comment on Edie's traffic delays at toll booths. Oper. Res. 2 (1954) 339-341.

[12] M. Fischetti and A. Lodi. Local branching. Math. Program. B 98 (2003) 23-47. | MR | Zbl

[13] W.B. Henderson and W.L. Berry. Heuristic methods for telephone operator shift scheduling: an experimental analysis. Manage. Sci. 22 (1976) 1372-1380.

[14] D.S. Hochbaum and A. Levin. Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discrete Optimization 3(4) (2006) 327-340. | MR | Zbl

[15] N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR | Zbl

[16] S.L. Moondra. An L.P. model for workforce scheduling in banks. J. Bank Res. 6 (1976) 299-301.

[17] M. Rekik, J.-F. Cordeau, and F. Soumis. Using Benders decomposition to implicitly model tour scheduling. Ann. Oper. Res. 128 (2004) 111-133. | MR | Zbl

[18] M. Rekik, J-F. Cordeau, and F. Soumis. Implicit shift scheduling with multiple breaks and work stretch duration restrictions. Technical report, GERAD-2005-15, (2005).

[19] G.M. Thompson. Improved implicit optimal modeling of the labor shift scheduling problem. Manage. Sci. 41 (1995) 595-607. | Zbl

[20] G.M. Thompson. A simulated annealing heuristic for shift scheduling using non-continuously available employees. Comput. Oper. Res. 32 (1996) 275-288. | Zbl

[21] S. Topaloglua and I. Ozkarahan. Implicit optimal tour scheduling with flexible break assignments. Computers & Industrial Engineering 44 (2002) 75-89.

Cité par Sources :