Pre-processing techniques for resource allocation in the heterogeneous case

✍ Scribed by Vicente Valls; M. Angeles Perez; M. Sacramento Quintanilla

• Book ID: 104339605
• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 251 KB
• Volume: 107
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00340-8

✦ Synopsis

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 ®nd 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.