Stable multi-skill workforce assignments

M. Firat, C.A.J. Hurkens, A. Laugier

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)
5 Downloads (Pure)


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 languageEnglish
Pages (from-to)95-114
Number of pages20
JournalAnnals of Operations Research
Issue number1
Publication statusPublished - 2014


Dive into the research topics of 'Stable multi-skill workforce assignments'. Together they form a unique fingerprint.

Cite this