The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach

Anders Dohn Hansen, Esben Kolind, Jens Clausen

    Research output: Contribution to journalJournal articleResearchpeer-review

    862 Downloads (Pure)

    Abstract

    In this paper, we consider the Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an IP-model for the problem, which is decomposed using Dantzig-Wolfe decomposition. The problem is solved by column generation in a Branch-and-Price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.
    Original languageEnglish
    JournalComputers & Operations Research
    Volume36
    Issue number4
    Pages (from-to)1145-1157
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2009

    Keywords

    • Branch-and-Price
    • Synchronization
    • Manpower allocation
    • Crew scheduling
    • Column generation
    • Vehicle routing with time windows
    • Decomposition
    • Branching rules
    • Integer programming
    • Set covering
    • Simultaneous execution

    Fingerprint

    Dive into the research topics of 'The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach'. Together they form a unique fingerprint.

    Cite this