On the Scalability of Constraint Solving for Static/Off-Line Real-Time Scheduling

Abstract : Recent papers have reported on successful application of constraint solving techniques to off-line real-time scheduling problems, with realistic size and complexity. Success allegedly came for two reasons: major recent advances in solvers efficiency and use of optimized, problem-specific constraint representations. Our current objective is to assess further the range of applicability and the scalability of such constraint solving techniques based on a more general and agnostic evaluation campaign. For this, we have considered a large number of synthetic scheduling problems and a few real-life ones, and attempted to solve them using 3 state-of-the-art solvers, namely CPLEX, Yices2, and MiniZinc/G12. Our findings were that, for all problems considered, constraint solving does scale to a certain limit, then diverges rapidly. This limit greatly depends on the specificity of the scheduling problem type. All experimental data (synthetic task systems, SMT/ILP models) are provided so as to allow experimental reproducibility.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179489
Contributeur : Team Kairos <>
Soumis le : mercredi 22 juillet 2015 - 15:52:27
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 11:14:29

Fichier

preprint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01179489, version 1

Collections

Relations

Citation

Raul Gorcitz, Emilien Kofman, Thomas Carle, Dumitru Potop-Butucaru, Robert De Simone. On the Scalability of Constraint Solving for Static/Off-Line Real-Time Scheduling. 2015. 〈hal-01179489〉

Partager

Métriques

Consultations de la notice

328

Téléchargements de fichiers

237