CRIS Current Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishResource constrained cyclic scheduling problems consist in planning the execution over limited resources of a set of activities, to be indefinitely repeated. In such a context, the iteration period (i.e. the difference between the completion time of consecutive iterations) naturally replaces the makespan as a quality measure; exploiting inter-iteration overlapping is the primary method to obtain high quality schedules. Classical approaches for cyclic scheduling rely on the fact that, by fixing the iteration period, the problem admits an integer linear model. The optimal solution is then usually obtained iteratively, via linear or binary search on the possible iteration period values. In this paper we follow an alternative approach and provide a port of the key Precedence Constraint Posting ideas in a cyclic scheduling context; the value of the iteration period is not a-priori fixed, but results from conflict resolution decisions. A heuristic search method based on Iterative Flattening is used as a practical demonstrator; this was tested over instances from an industrial problem obtaining encouraging results.
| Titolo: | Precedence Constraint Posting for Cyclic Scheduling Problems | |
| Autore/i: | LOMBARDI, MICHELE; BONFIETTI, ALESSIO; MILANO, MICHELA; BENINI, LUCA | |
| Autore/i Unibo: | ||
| Anno: | 2011 | |
| Serie: | ||
| Titolo del libro: | Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 8th International Conference, CPAIOR 2011, Berlin, Germany, May 23-27, 2011. Proceedings, Lecture Notes in Computer Science | |
| Pagina iniziale: | 137 | |
| Pagina finale: | 153 | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-642-21311-3_14 | |
| Abstract: | Resource constrained cyclic scheduling problems consist in planning the execution over limited resources of a set of activities, to be indefinitely repeated. In such a context, the iteration period (i.e. the difference between the completion time of consecutive iterations) naturally replaces the makespan as a quality measure; exploiting inter-iteration overlapping is the primary method to obtain high quality schedules. Classical approaches for cyclic scheduling rely on the fact that, by fixing the iteration period, the problem admits an integer linear model. The optimal solution is then usually obtained iteratively, via linear or binary search on the possible iteration period values. In this paper we follow an alternative approach and provide a port of the key Precedence Constraint Posting ideas in a cyclic scheduling context; the value of the iteration period is not a-priori fixed, but results from conflict resolution decisions. A heuristic search method based on Iterative Flattening is used as a practical demonstrator; this was tested over instances from an industrial problem obtaining encouraging results. | |
| Data prodotto definitivo in UGOV: | 27-giu-2013 | |
| Data stato definitivo: | 29-nov-2016 | |
| Appare nelle tipologie: | 2.01 Capitolo / saggio in libro |
File in questo prodotto:
http://hdl.handle.net/11585/106154
Copyright © 2022