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

Anders Dohn Hansen, Esben Kolind, Jens Clausen

    Research output: Book/ReportReport

    177 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
    PublisherInformatics and Mathematical Modelling, Technical University of Denmark, DTU
    Publication statusPublished - 2007

    Cite this

    Hansen, A. D., Kolind, E., & Clausen, J. (2007). The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report. Informatics and Mathematical Modelling, Technical University of Denmark, DTU.
    Hansen, Anders Dohn ; Kolind, Esben ; Clausen, Jens. / The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report. Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2007.
    @book{74b2ac5a79e74fa5b6d60950d6736f39,
    title = "The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report",
    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.",
    author = "Hansen, {Anders Dohn} and Esben Kolind and Jens Clausen",
    year = "2007",
    language = "English",
    publisher = "Informatics and Mathematical Modelling, Technical University of Denmark, DTU",

    }

    Hansen, AD, Kolind, E & Clausen, J 2007, The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report. Informatics and Mathematical Modelling, Technical University of Denmark, DTU.

    The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report. / Hansen, Anders Dohn; Kolind, Esben; Clausen, Jens.

    Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2007.

    Research output: Book/ReportReport

    TY - RPRT

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

    AU - Hansen, Anders Dohn

    AU - Kolind, Esben

    AU - Clausen, Jens

    PY - 2007

    Y1 - 2007

    N2 - 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.

    AB - 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.

    M3 - Report

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

    PB - Informatics and Mathematical Modelling, Technical University of Denmark, DTU

    ER -

    Hansen AD, Kolind E, Clausen J. The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach - Technical Report. Informatics and Mathematical Modelling, Technical University of Denmark, DTU, 2007.