The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints: A Branch-and-Price Approach |
Anders Dohn, Esben Kolind, Jens Clausen
|
| 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. |
| Keywords | Manpower allocation; Crew scheduling; Vehicle routing with time windows; Synchronization; Simultaneous execution; Branch-and-Price; Branching rules; Column generation; Decomposition; Set covering; Integer programming |
| Type | Journal paper [With referee] |
| Journal | Computers & Operations Research |
| Year | 2009 Vol. 36 No. 4 pp. 1145-1157 |
| Note | doi: 10.1016/j.cor.2007.12.011 |
| Publication link | http://dx.doi.org/10.1016/j.cor.2007.12.011 |
| BibTeX data | [bibtex] |
| IMM Group(s) | Operations Research |