A decomposition heuristic for resource allocation
Berthe Y. Choueiry, Boi V. Faltings · 1994
. The allocation of resources to a set of tasks with fixed start and end times is known to be NP-complete. We propose an approximation based on identifying pools of interchangeable resources and tasks using a novel decomposition heuristic. The pools are abstractions which provide simple representations for making conflicts explicit. The method is an anytime algorithm that efficiently finds a sub-optimal solution which can then be improved by refining the underlying decomposition. This is more practical than constraint relaxation techniques traditionally used to deal with such problems. 1 Introduction Planning, scheduling and resource allocation are closely related tasks. Because they intervene at different time scales, they are often decoupled. Consider, for instance, the problem of managing flights of an airline company. Purchasing airplanes, hiring personnel, setting flight timetables as well as making large investment decisions are planned for a relatively long period of time and ...