Abstract
This paper addresses the Ground Crew Rostering Problem with Work Patterns, an important manpower planning problem arising in the ground operations of airline companies. We present a cutting stock-based integer programming formulation of the problem and describe a powerful heuristic decomposition approach, which utilizes column generation and variable fixing, to construct efficient rosters for a six-month time horizon. The time horizon is divided into smaller blocks, where overlaps between the blocks ensure continuity. The proposed methodology is able to circumvent one step of the conventional roster construction process by generating rosters directly based on the estimated workload. We demonstrate that this approach has the additional advantage of being able to easily incorporate robustness in the roster. Computational results on real-life instances confirm the efficiency of the approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abbink E, Fischetti M, Kroon L, Timmer G and Vromans M (2005). Reinventing crew scheduling at Netherlands railways. Interfaces 35 (5): 393–401.
Alfares HK (1997). An efficient two-phase algorithm for cyclic days-off scheduling. Comput Opns Res 25 (11): 913–923.
Alfares HK (2002). Optimum workforce scheduling under the (14, 21) days-off timetable. J Appl Math Decis Sci 63 (3): 191–199.
Amor HB and de Carvalho JV (2005). Cutting stock problems. In: Desaulniers G, Desrosiers J and Solomon M (eds). Column Generation. Chapter 5. Springer: New York, pp 131–161.
Anbil R, Gelman E, Patty B and Tanga R (1991). Recent advances in crew-pairing optimization at American Airlines. Interfaces 21 (1): 62–74.
Barnhart C, Cohn AM, Johnson EL, Klabjan D, Nemhauser GL and Vance PH (2003). Airline crew scheduling. In: Hall RW (ed). Handbook of Transportation Science. Kluwer Academic Publishers: Dordrecht.
Brusco MJ, Jacobs LW, Bongiorno RJ, Lyons DV and Tang B (1995). Improving personnel scheduling at airline stations. Ops Res 43 (5): 741–751.
Burke EK, De Causmaecker P, vanden Berghe G and van Landeghem H (2004). The state of the art of nurse rostering. J Scheduling 7: 441–499.
Burke EK, De Causmaecker P, De Maere G, Mulder J, Paelinck M and Vanden Berghe G (2010). A multi-objective approach for robust airline scheduling. Comput Opns Res 37 (5): 822–832.
Butchers ER, Day PR, Goldie AP, Miller S, Meyer JA, Ryan DM, Scott AC and Wallace CA (2001). Optimized crew scheduling at Air New Zealand. Interfaces 31 (1): 30–56.
Cheang B, Li H, Lim A and Rodrigues B (2003). Nurse rostering problems—A bibliographic survey. Eur J Opl Res 151: 447–460.
Chu SCK (2007). Generating, scheduling and rostering of shift crew-duties: Applications at the Hong Kong International Airport. Eur J Opl Res 177: 1764–1778.
Clausen J, Larsen A, Larsen J and Rezanova NJ (2010). Disruption management in the airline industry – Concepts, models and methods. Comput Opns Res 37 (5): 809–821.
Danna E and Pape CL (2005). Branch-and-price heuristics: A case study on the vehicle routing problem with time windows. In: Guy Desaulniers JD and Solomon MM (eds). Column Generation. Chapter 4. Springer: New York, pp 99–129.
Day PR and Ryan DM (1997). Flight attendant rostering for short-haul airline operations. Opns Res 45 (5): 649–661.
Desaulniers G (2010). Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows. Opns Res 58 (1): 179–192.
Desaulniers G, Desrosiers J, Ioachim I, Solomon M, Soumis F and Villeneuve D (1998). A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic T and Laporte G (eds). Fleet Management and Logistics. Chapter 3. Kluwer Academic Publishers: Dordrecht, pp 57–94.
Desaulniers G, Desrosiers J and Solomon MM (2002). Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems. Kluwer: Norwell, pp 309–324.
Desrochers M and Soumis F (1988). A reoptimization algorithm for the shortest path problem with time windows. Eur J Opl Res 35 (2): 242–254.
Desrosiers J and Lübbecke ME (2005). Column generation. In: Desaulniers G, Desrosiers J and Solomon MM (eds). A Primer in Column Generation. Chapter 1. Springer: New York, pp 1–32.
Dohn A, Mason A and Ryan D (2010). A generic solution approach to nurse rostering. Technical Report 5, Department of Management Engineering, Technical University of Denmark.
Dowling D, Krishnamoorthy M, Mackenzie H and Sier D (1997). Staff rostering at a large international airport. Ann Opns Res 72: 125–147.
Ernst A, Jiang H, Krishnamoorthy M and Sier D (2004). Staff scheduling and rostering: A review of applications, methods, and models. Eur J Opns Res 153: 3–27.
Eveborn P and Rönnqvist M (2004). Scheduler—A system for staff planning. Ann Opns Res 128 (1–4): 21–45.
Gendreau M, Ferland J, Gendron B, Hail N, Jaumard B, Lapierre S, Pesant G and Soriano P (2006). Physician scheduling in emergency rooms. In: Burke EK and Rudová H (eds). Practice and Theory of Automated Timetabling VI. 6th International Conference, PATAT. Springer: Verlag.
Irnich S (2008). Resource extension functions: Properties, inversion, and generalization to segments. OR Spect 30 (1): 113–148.
Irnich S and Desaulniers G (2005). Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon M (eds). Column Generation. Chapter 2. Springer: New York, pp 33–66.
Kellogg DL and Walczak S (2007). Nurse scheduling: From academia to implementation or not? Interfaces 37 (4): 355–369.
Mehrotra A, Murphy K and Trick M (2000). Optimal shift scheduling: A branch-and-price approach. Naval Res Logist 47 (3): 185–200.
Ryan D and Foster B (1981). An integer programming approach to scheduling. In: Wren A (ed). Computer Scheduling of Public Transport. Urban Passenger Vehicle and Crew Scheduling. North-Holland, Amsterdam, pp 269–280.
Vohra RV (1987). The cost of consecutivity in the (5, 7) cyclic staffing problem. IIE Trans 29: 942–950.
Wäscher G and Gau T (1996). Heuristics for the integer one-dimensional cutting stock problem: A computational study. OR Spect 18 (3): 131–144.
Weide O, Ryan D and Ehrgott M (2010). An iterative approach to robust and integrated aircraft routing and crew scheduling. Comput Opns Res 37 (5): 833–844.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lusby, R., Dohn, A., Range, T. et al. A column generation-based heuristic for rostering with work patterns. J Oper Res Soc 63, 261–277 (2012). https://doi.org/10.1057/jors.2011.27
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2011.27