The Manpower Allocation Problem with Time Windows and Job-Teaming Constraints

摘要

The Manpower Allocation Problem with Time Windows, Job-Teaming Constraints and a limited number of teams (m-MAPTWTC) is a crew scheduling problem faced in several different contexts in the industry. The number of teams is predetermined and hence the objective is to create a schedule that will maximize utilization by leaving as few tasks uncompleted as possible. The schedule must respect working hours of the teams, transportation time between locations, and skill requirements and time windows of the tasks. Furthermore, some tasks are completed by multiple cooperating teams. Cooperating teams must initiate work simultaneously and hence this must be maintained in the schedule. The problem is solved using column generation and Branch-and-Bound. Optimal solutions are found in 11 of 12 test instances originating from real-life problems. The paper illustrates a way to exploit the close relations between scheduling and vehicle routing problems. The formulation as a routing problem gives a methodological benefit, leading to optimal solutions. A constraint on synchronization is imposed and successfully dealt with in the branching scheme.