Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results
| Autor: | Philippe Laborie |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Rate-monotonic scheduling
Earliest deadline first scheduling Linguistics and Language Mathematical optimization Scheduling Computer science Distributed computing Dynamic priority scheduling Round-robin scheduling Language and Linguistics Fair-share scheduling Artificial Intelligence Genetic algorithm scheduling Two-level scheduling Cumulative resources Lottery scheduling Constraint programming Algorithm AI planning |
| Zdroj: | Artificial Intelligence. 143:151-188 |
| ISSN: | 0004-3702 |
| DOI: | 10.1016/s0004-3702(02)00362-4 |
| Popis: | This paper summarizes the main existing approaches to propagate resource constraints in Constraint-Based scheduling and identifies some of their limitations for using them in an integrated planning and scheduling framework. We then describe two new algorithms to propagate resource constraints on discrete resources and reservoirs. Unlike most of the classical work in scheduling, our algorithms focus on the precedence relations between activities rather than on their absolute position in time. They are efficient even when the set of activities is not completely defined and when the time window of activities is large. These features explain why our algorithms are particularly suited for integrated planning and scheduling approaches. All our algorithms are illustrated with examples. Encouraging preliminary results are reported on pure scheduling problems as well as some possible extensions of our framework. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect