The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints | Anders Dohn, Esben Kolind, Jens Clausen
| | Abstract | The Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC) is the problem of assigning $m$ teams to a number of tasks, where both teams and tasks may be restricted by time windows outside which operation is not possible. Tasks may require several individual teams to cooperate. Due to the limited number of teams, some tasks may have to be left unassigned. The objective is to maximize the number of assigned tasks.
The problem arises in various crew scheduling contexts where cooperation between teams/workers, possibly with different skills, is required to solve tasks. This study focuses on the scheduling of ground handling tasks in some of Europe's major airports. Between arrival and the subsequent departure of an aircraft, numerous jobs
including baggage handling and cleaning must be performed. Typically, specialized handling companies take on the jobs and assign crews of workers with different skills. Any daily work plan must comply with the time windows of tasks, the working hours of the staff, the skill requirements of tasks, and union regulations. It may be necessary to have several teams cooperating on one task in order to complete it within the time window. Furthermore, all
teams involved must initiate work on the task simultaneously (synchronized cooperation), as only one of the team leaders is appointed as responsible supervisor.
The problem is solved using column generation in a Branch-and-Price framework. Synchronization of cooperating teams
is enforced by branching on time windows. The problem is closely related to the Vehicle Routing Problem with Time Windows (VRPTW) which has been studied extensively in the literature. The most promising recent results for exact solution of VRPTW problems use column generation.
The test data sets originate from real-life situations faced by ground handling companies in two of Europe's major airports. A total of 12 test instances are available. Optimal solutions are found for 11 of the 12 test instances. Not surprisingly, a significant decrease in the required computational time is observed, when the constraint on synchronization is relaxed. Hence, we conclude that the synchronization constraint does add some complexity to the problem. However, we also show that it is still possible to get optimal solution for realistic problems when synchronized cooperation is compulsory. Synchronization between teams in an exact optimization context has not previously been treated in the literature. We have successfully integrated the extra requirements into the solution procedure and the results are promising. | | Type | Conference paper [Abstract] | | Conference | Nordic Optimization Symposium | | Year | 2007 | | Electronic version(s) | [pdf] | | BibTeX data | [bibtex] | | IMM Group(s) | Operations Research |
|