Abstract
This paper analyzes stability in multi-skill workforce assignments of technicians and jobs. In our stability analysis, we extend the notion of blocking pairs as stated in the Marriage model of Gale-Shapley to the multi-skill workforce assignment. It is shown that finding stable assignments is NP-hard. A special case turns out to be solvable in polynomial time. For the general case, we give a characterization of the set of stable assignments by means of linear inequalities involving binary variables. We propose an integer programming (IP) model to construct optimal stable assignments with several objectives. In the computational results, we observe that it is easier to attain stability in instances with easy jobs and we consider a range of instances to show how fast the solution time increases. Open questions and further directions are discussed in the conclusion section.
Keywords: Multi-skill workforce schedules; Stable assignments; Instability; Blocking pair; University admissions problem; Three-dimensional matching problem; Optimal stable assignments
| Original language | English |
|---|---|
| Pages (from-to) | 95-114 |
| Number of pages | 20 |
| Journal | Annals of Operations Research |
| Volume | 213 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2014 |