Optimal methods for resource allocation and scheduling: a cross-disciplinary survey |
| |
Authors: | Michele Lombardi Michela Milano |
| |
Affiliation: | 1. DEIS, University of Bologna, Viale del Risorgimento 2, 40136, Bologna, Italy
|
| |
Abstract: | Classical scheduling formulations typically assume static resource requirements and focus on deciding when to start the problem
activities, so as to optimize some performance metric. In many practical cases, however, the decision maker has the ability
to choose the resource assignment as well as the starting times: this is a far-from-trivial task, with deep implications on
the quality of the final schedule. Joint resource assignment and scheduling problems are incredibly challenging from a computational
perspective. They have been subject of active research in Constraint Programming (CP) and in Operations Research (OR) for
a few decades, with quite difference techniques. Both the approaches report individual successes, but they overall perform
equally well or (from a different perspective) equally poorly. In particular, despite the well known effectiveness of global
constraints for scheduling, comparable results for joint filtering of assignment and scheduling variables have not yet been
achieved. Recently, hybrid approaches have been applied to this class of problems: most of them work by splitting the overall
problem into an assignment and a scheduling subparts; those are solved in an iterative and interactive fashion with a mix
of CP and OR techniques, often reporting impressive speed-ups compared to pure CP and OR methods. Motivated by the success
of hybrid algorithms on resource assignment and scheduling, we provide a cross-disciplinary survey on such problems, including
CP, OR and hybrid approaches. The main effort is to identify key modeling and solution techniques: they may then be applied
in the construction of new hybrid algorithms, or they may provide ideas for novel filtering methods (possibly based on decomposition,
or on alternative representations of the domain store). In detail, we take a constraint-based perspective and, according to
the equation CP = model + propagation + search, we give an overview of state-of-art models, propagation/bounding techniques
and search strategies. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|