Article ID: | iaor20023167 |
Country: | Netherlands |
Volume: | 138 |
Issue: | 1 |
Start Page Number: | 9 |
End Page Number: | 20 |
Publication Date: | Apr 2002 |
Journal: | European Journal of Operational Research |
Authors: | Campbell Gerard M., Diaby Moustapha |
Keywords: | programming: assignment |
An assignment heuristic is developed for allocating cross-trained workers to multiple departments at the beginning of a shift. The cross-trained workers may have different levels of qualification in different departments. With non-linear departmental objective functions and binary decision variables, the problem's formulation represents a variant of the generalized assignment problem, whose difficulty is well known. The new assignment heuristic is based on a linear assignment approximation that takes advantage of the special structure of the cross-utilization problem. It is shown that this assignment heuristic is superior to a classical Lagrangian heuristic and a simplistic Greedy approach. Experimental evaluations are facilitated by the development of a technique that provides tight bounds for the problem. Based on a standard measure of performance, assignment heuristic solutions average within 0.09% of upper bounds across a variety of problem characteristics.