TY - JOUR

T1 - The minimum shift design problem

T2 - theory and practice

AU - Gaspero, Luca Di

AU - Gärtner, Johannes

AU - Kortsarz, Guy

AU - Musliu, Nysret

AU - Schaerf, Andrea

AU - Slany, Wolfgang

PY - 2003

Y1 - 2003

N2 - We study the minimum shift design problem (MSD) that arose in a commercial shift scheduling software project: Given a collection of shifts and workforce requirements for a certain time interval, we look for a minimum cardinality subset of the shifts together with an optimal assignment of workers to this subset of shifts such that the deviation from the requirements is minimum. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF. We give a logarithmic hardness of approximation lower bound. In the second part of the paper, we present practical heuristics for MSD. First, we describe a local search procedure based on interleaving different neighborhood definitions. Second, we describe a new greedy heuristic that uses a min-cost max-flow (MCMF) subroutine, inspired by the relation between the MSD and MECF problems. The third heuristic consists of a serial combination of the other two. An experimental analysis shows that our new heuristics clearly outperform an existing commercial implementation.

AB - We study the minimum shift design problem (MSD) that arose in a commercial shift scheduling software project: Given a collection of shifts and workforce requirements for a certain time interval, we look for a minimum cardinality subset of the shifts together with an optimal assignment of workers to this subset of shifts such that the deviation from the requirements is minimum. This problem is closely related to the minimum edge-cost flow problem (MECF), a network flow variant that has many applications beyond shift scheduling. We show that MSD reduces to a special case of MECF. We give a logarithmic hardness of approximation lower bound. In the second part of the paper, we present practical heuristics for MSD. First, we describe a local search procedure based on interleaving different neighborhood definitions. Second, we describe a new greedy heuristic that uses a min-cost max-flow (MCMF) subroutine, inspired by the relation between the MSD and MECF problems. The third heuristic consists of a serial combination of the other two. An experimental analysis shows that our new heuristics clearly outperform an existing commercial implementation.

UR - http://www.scopus.com/inward/record.url?scp=0142183780&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0142183780&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0142183780

SN - 0302-9743

VL - 2832

SP - 593

EP - 604

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -