Solution approaches to large shift scheduling problems

Monia Rekik; Jean-François Cordeau; François Soumis

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 2, page 229-258
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Rekik, Monia, Cordeau, Jean-François, and Soumis, François. "Solution approaches to large shift scheduling problems." RAIRO - Operations Research 42.2 (2008): 229-258. <http://eudml.org/doc/250389>.

@article{Rekik2008,
abstract = { 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. },
author = {Rekik, Monia, Cordeau, Jean-François, Soumis, François},
journal = {RAIRO - Operations Research},
keywords = {Shift scheduling; flexibility; fractionable breaks; work stretch restrictions; forward and backward constraints; local branching; heuristic.; shift scheduling; fractionable breaks; local branching; heuristic},
language = {eng},
month = {5},
number = {2},
pages = {229-258},
publisher = {EDP Sciences},
title = {Solution approaches to large shift scheduling problems},
url = {http://eudml.org/doc/250389},
volume = {42},
year = {2008},
}

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
DA - 2008/5//
PB - EDP Sciences
VL - 42
IS - 2
SP - 229
EP - 258
AB - 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.
LA - eng
KW - Shift scheduling; flexibility; fractionable breaks; work stretch restrictions; forward and backward constraints; local branching; heuristic.; shift scheduling; fractionable breaks; local branching; heuristic
UR - http://eudml.org/doc/250389
ER -

References

top
  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.  
  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.  
  4. T. Aykin. A comparative evaluation of modeling approaches to the labor shift scheduling problem. Eur. J. Oper. Res.125 (2000) 381–397.  
  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 Sciences24 (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.  
  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.  
  9. T. Çezik and O. Günlük. Reformulating linear programs with transportation constraints- with applications to workforce scheduling. Naval Research Logistics51 (2004) 275–296.  
  10. E. Danna, E. Rothberg, and C. Le Pape. Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program.102 (2005) 71–90.  
  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.  
  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 Optimization3(4) (2006) 327–340.  
  15. N. Mladenovic and P. Hansen. Variable neighborhood search. Comput. Oper. Res.24 (1997) 1097–1100.  
  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.  
  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.  
  20. G.M. Thompson. A simulated annealing heuristic for shift scheduling using non-continuously available employees. Comput. Oper. Res.32 (1996) 275–288.  
  21. S. Topaloglua and I. Ozkarahan. Implicit optimal tour scheduling with flexible break assignments. Computers & Industrial Engineering44 (2002) 75–89.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.