A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills

M. Firat, D. Briskorn, A. Laugier

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

7 Citaties (Scopus)
1 Downloads (Pure)

Uittreksel

This paper deals with assigning hierarchically skilled technicians to jobs by considering preferences. We investigate stability definitions in multi-skill workforce assignments stemming from the notion of blocking pairs as stated in the Marriage model of Gale–Shapley. We propose a Branch-and-Price approach to find a stable workforce assignment in which no technician and job pair can be better off by replacing an already assigned technician in current team of the job. As base for our exact algorithm, we give a reformulation of the problem which constructs a stable assignment by selecting teams from a base set. Then, the pricing problem accounts finding a team to a job. We provide details of the algorithm and show its efficiency by means of a computational study. We also show that checking stability becomes NP-hard, if replacing groups of technicians is considered in defining stability.
Originele taal-2Engels
Pagina's (van-tot)676-685
TijdschriftEuropean Journal of Operational Research
Volume251
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 1 jun 2016

Vingerafdruk

Branch-and-price
Assignment
Exact Algorithms
Reformulation
Pricing
NP-complete problem
Skills
Workforce
Costs
Model

Citeer dit

@article{e2ea651566a2450895ad74e3d0c1cd34,
title = "A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills",
abstract = "This paper deals with assigning hierarchically skilled technicians to jobs by considering preferences. We investigate stability definitions in multi-skill workforce assignments stemming from the notion of blocking pairs as stated in the Marriage model of Gale–Shapley. We propose a Branch-and-Price approach to find a stable workforce assignment in which no technician and job pair can be better off by replacing an already assigned technician in current team of the job. As base for our exact algorithm, we give a reformulation of the problem which constructs a stable assignment by selecting teams from a base set. Then, the pricing problem accounts finding a team to a job. We provide details of the algorithm and show its efficiency by means of a computational study. We also show that checking stability becomes NP-hard, if replacing groups of technicians is considered in defining stability.",
keywords = "Workforce assignment with hierarchical skills, Stable assignments, Column generation, Branch-and-Price",
author = "M. Firat and D. Briskorn and A. Laugier",
year = "2016",
month = "6",
day = "1",
doi = "10.1016/j.ejor.2015.11.039",
language = "English",
volume = "251",
pages = "676--685",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills. / Firat, M.; Briskorn, D.; Laugier, A.

In: European Journal of Operational Research, Vol. 251, Nr. 2, 01.06.2016, blz. 676-685.

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

TY - JOUR

T1 - A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills

AU - Firat, M.

AU - Briskorn, D.

AU - Laugier, A.

PY - 2016/6/1

Y1 - 2016/6/1

N2 - This paper deals with assigning hierarchically skilled technicians to jobs by considering preferences. We investigate stability definitions in multi-skill workforce assignments stemming from the notion of blocking pairs as stated in the Marriage model of Gale–Shapley. We propose a Branch-and-Price approach to find a stable workforce assignment in which no technician and job pair can be better off by replacing an already assigned technician in current team of the job. As base for our exact algorithm, we give a reformulation of the problem which constructs a stable assignment by selecting teams from a base set. Then, the pricing problem accounts finding a team to a job. We provide details of the algorithm and show its efficiency by means of a computational study. We also show that checking stability becomes NP-hard, if replacing groups of technicians is considered in defining stability.

AB - This paper deals with assigning hierarchically skilled technicians to jobs by considering preferences. We investigate stability definitions in multi-skill workforce assignments stemming from the notion of blocking pairs as stated in the Marriage model of Gale–Shapley. We propose a Branch-and-Price approach to find a stable workforce assignment in which no technician and job pair can be better off by replacing an already assigned technician in current team of the job. As base for our exact algorithm, we give a reformulation of the problem which constructs a stable assignment by selecting teams from a base set. Then, the pricing problem accounts finding a team to a job. We provide details of the algorithm and show its efficiency by means of a computational study. We also show that checking stability becomes NP-hard, if replacing groups of technicians is considered in defining stability.

KW - Workforce assignment with hierarchical skills

KW - Stable assignments

KW - Column generation

KW - Branch-and-Price

U2 - 10.1016/j.ejor.2015.11.039

DO - 10.1016/j.ejor.2015.11.039

M3 - Article

VL - 251

SP - 676

EP - 685

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -