A Benders decomposition-based Matheuristic for the Cardinality Constrained Shift Design Problem

Richard Martin Lusby, Troels Martin Range () and Jesper Larsen
Additional contact information
Richard Martin Lusby: Department of Management Engineering, Postal: Technical University of Denmark
Troels Martin Range: Department of Business and Economics, Postal: University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark
Jesper Larsen: Department of Management Engineering, Postal: Technical University of Denmark

No 9/2015, Discussion Papers on Economics from University of Southern Denmark, Department of Economics

Abstract: The Shift Design Problem is an important optimization problem which arises when scheduling personnel in industries that require continuous operation. Based on the forecast, required staffing levels for a set of time periods, a set of shift types that best covers the demand must be determined. A shift type is a consecutive sequence of time periods that adheres to legal and union rules and can be assigned to an employee on any day. In this paper we introduce the Cardinality Constrained Shift Design Problem; a variant of the Shift Design Problem in which the number of permitted shift types is bounded by an upper limit. We present an Integer Programming model for this problem and show that its structure lends itself very naturally to Benders decomposition. Due to convergence issues with a conventional implementation, we propose a matheuristic based on Benders decomposition for solving the problem. Furthermore, we argue that an important step in this approach is finding dual alternative optimal solutions to the Benders subproblems and describe an approach to obtain a diverse set of these. Numerical tests show that the described methodology significantly outperforms a commercial Mixed Integer Programming solver on instances with 1241 different shift types and remains competitive for larger cases with 2145 shift types. On all classes of problems the heuristic is able to quickly find good solutions.

Keywords: Scheduling; shift design; integer programming; benders decomposition (search for similar items in EconPapers)
JEL-codes: C61 (search for similar items in EconPapers)
Pages: 23 pages
Date: 2015-04-20
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.sdu.dk/-/media/files/om_sdu/institutte ... _2015/dpbe9_2015.pdf Full text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:sdueko:2015_009

Access Statistics for this paper

More papers in Discussion Papers on Economics from University of Southern Denmark, Department of Economics Department of Economics, University of Southern Denmark, Campusvej 55, DK-5230 Odense M, Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Astrid Holm Nielsen ().