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

M. Firat, D. Briskorn, A. Laugier

    Research output: Contribution to journalArticleAcademicpeer-review

    15 Citations (Scopus)
    1 Downloads (Pure)

    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.
    Original languageEnglish
    Pages (from-to)676-685
    JournalEuropean Journal of Operational Research
    Volume251
    Issue number2
    DOIs
    Publication statusPublished - 1 Jun 2016

    Keywords

    • Workforce assignment with hierarchical skills
    • Stable assignments
    • Column generation
    • Branch-and-Price

    Fingerprint

    Dive into the research topics of 'A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills'. Together they form a unique fingerprint.

    Cite this