Many real world cyclic scheduling problems involve applications that need to be repeated with different periodicity. For example, multirate control systems present multiple control loops that are organized hierarchically: The higher-level loop responds to the slower system dynamics and typically its period can be a few orders of magnitude longer than the lowest level. Cyclic scheduling problems can be cast into classical RCPSP instances via a technique called unfolding [4,6], which causes graph expansion. In the case of multirate applications, this expansion can be significantly large. In this context, finding a high-quality allocation and schedule could be very challenging. In this paper, we propose a new Multirate Resource Constraint, modeling unary resources, that avoids graph expansion by exploiting the multirate nature of the schedule in its filtering algorithm. In an experimentation on synthetic and real-world instances, we show that our method drastically outperforms approaches based on state-of-the-art unfolding and constraint based scheduling.
Titolo: | The multirate resource constraint | |
Autore/i: | BONFIETTI, ALESSIO; ZANARINI, ALESSANDRO; LOMBARDI, MICHELE; MILANO, MICHELA | |
Autore/i Unibo: | ||
Anno: | 2016 | |
Rivista: | ||
Titolo del libro: | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
Pagina iniziale: | 113 | |
Pagina finale: | 129 | |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-319-44953-1_8 | |
Abstract: | Many real world cyclic scheduling problems involve applications that need to be repeated with different periodicity. For example, multirate control systems present multiple control loops that are organized hierarchically: The higher-level loop responds to the slower system dynamics and typically its period can be a few orders of magnitude longer than the lowest level. Cyclic scheduling problems can be cast into classical RCPSP instances via a technique called unfolding [4,6], which causes graph expansion. In the case of multirate applications, this expansion can be significantly large. In this context, finding a high-quality allocation and schedule could be very challenging. In this paper, we propose a new Multirate Resource Constraint, modeling unary resources, that avoids graph expansion by exploiting the multirate nature of the schedule in its filtering algorithm. In an experimentation on synthetic and real-world instances, we show that our method drastically outperforms approaches based on state-of-the-art unfolding and constraint based scheduling. | |
Data stato definitivo: | 28-nov-2016 | |
Appare nelle tipologie: | 4.01 Contributo in Atti di convegno |