Development and evaluation of an assignment heuristic for allocating cross-trained workers

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. (C) 2002 Elsevier Science B.V. All rights reserved.