A two-stage heuristic for multi-activity and task assignment to work shifts

The multi-activity assignment problem consists of assigning interruptible activities to given work shifts so as to match as much as possible for each activity a demand curve in function of time. In this paper we consider an extension to this problem, called the multi-activity and task assignment problem, that additionally considers the assignment of uninterruptible pieces of work, called tasks. These possess properties such as worker qualifications, time windows for completion, fixed lengths and precedence relationships. We propose a mixed-integer programming formulation and a two-stage method to solve this problem. The first stage consists of an approximation mixed-integer programming model to assign tasks approximately taking into account the activities and the second involves a column generation heuristic for assigning activities and reassigning tasks at the same time. We suggest four different strategies for reassigning tasks. We conducted extensive computational tests on randomly generated instances in order to validate our method and to compare the various strategies. One strategy proved universally best when compared to the other three policies. (C) 2012 Elsevier Ltd. All rights reserved.