Stable multi-skill workforce assignments

Autor:	Alexandre Laugier, Cor A. J. Hurkens, Murat Firat
Přispěvatelé:	Stochastic Operations Research, Process Science, Combinatorial Optimization 1
Jazyk:	angličtina
Rok vydání:	2014
Předmět:	Linear inequality Range (mathematics) Mathematical optimization Computer science Theory of computation Stability (learning theory) General Decision Sciences Management Science and Operations Research Time complexity Integer programming Blocking (computing)
Zdroj:	Annals of Operations Research, 213(1), 95-114. Springer
ISSN:	1572-9338 0254-5330
Popis:	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
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6f5cdd25869226445f329cdeb6e8276a https://research.tue.nl/en/publications/43e20269-8fe3-4b47-a4dd-543a0d95edc8 Zobrazit plný text záznamu Plný text ve formátu PDF