Pre-processing techniques for resource allocation in the heterogeneous case

The Heterogeneous Resource Allocation Problem (HRAP) deals with the allocation of resources, whose units do not all share the same characteristics, to an established plan of activities. Each activity requires one or more units of each resource which possess particular characteristics, and the objective is to find the minimum number of resource units of each type, necessary to carry out all the activities within the plan, in such a way that two activities whose processing overlaps in time do not have the same resource unit assigned. The HRAP is an NP-Complete problem and it is possible to optimally solve medium-sized HRAP instances in a reasonable time. The objective of this work is to develop preprocessing techniques that enable an HRAP to be transformed into an equivalent HRAP of smaller size, thus increasing the size of HRAPs that can be solved exactly. (C) 1998 Elsevier Science B.V. All rights reserved.