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.
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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro:2008006/
[1] Bechtold-Jacobs generalized model for shift scheduling with extraordinary overlap. Technical report, GERAD, HEC Montréal, (2004).
and .[2] Optimal shift scheduling with multiple break windows. Manage. Sci. 42 (1996) 591-602. | Zbl
.[3] 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] A comparative evaluation of modeling approaches to the labor shift scheduling problem. Eur. J. Oper. Res. 125 (2000) 381-397. | Zbl
.[5] Implicit modeling of flexible break assignments in optimal shift scheduling. Manage. Sci. 36 (1990) 1339-1351.
and .[6] Labor utilization effects of labor scheduling flexibility alternatives in a tour scheduling environment. Decision Sciences 24 (1993) 148-166.
and .[7] Cost analysis of alternative formulations for personnel scheduling in continuously operating organisations. Eur. J. Oper. Res. 86 (1995) 249-261. | Zbl
and .[8] Starting-time decisions in labor tour scheduling: an experimental analysis and case study. Eur. J. Oper. Res. 131 (2001) 459-475. | Zbl
and .[9] Reformulating linear programs with transportation constraints- with applications to workforce scheduling. Naval Research Logistics 51 (2004) 275-296. | MR | Zbl
and .[10] Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102 (2005) 71-90. | MR | Zbl
, , and .[11] A comment on Edie's traffic delays at toll booths. Oper. Res. 2 (1954) 339-341.
.[12] Local branching. Math. Program. B 98 (2003) 23-47. | MR | Zbl
and .[13] Heuristic methods for telephone operator shift scheduling: an experimental analysis. Manage. Sci. 22 (1976) 1372-1380.
and .[14] Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discrete Optimization 3(4) (2006) 327-340. | MR | Zbl
and .[15] Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097-1100. | MR | Zbl
and .[16] An L.P. model for workforce scheduling in banks. J. Bank Res. 6 (1976) 299-301.
.[17] Using Benders decomposition to implicitly model tour scheduling. Ann. Oper. Res. 128 (2004) 111-133. | MR | Zbl
, , and .[18] Implicit shift scheduling with multiple breaks and work stretch duration restrictions. Technical report, GERAD-2005-15, (2005).
, , and .[19] Improved implicit optimal modeling of the labor shift scheduling problem. Manage. Sci. 41 (1995) 595-607. | Zbl
.[20] A simulated annealing heuristic for shift scheduling using non-continuously available employees. Comput. Oper. Res. 32 (1996) 275-288. | Zbl
.[21] Implicit optimal tour scheduling with flexible break assignments. Computers & Industrial Engineering 44 (2002) 75-89.
and .Cité par Sources :