Supervision : Claire HANEN

Cyclic RCPSP study

The constant evolution of high performance processors architectures, to hold the challenging requirements of embedded applications, gives an increasing importance to a more efficient programming, mainly in compilation level, in these systems. Our study is particularly motivated by the optimization of scheduling when compiling instructions in VLIW processors (Very Large Instruction Word), and its resolution by using the RCPSP (Resource Constrained Project Scheduling Problem) cyclic. In such model, there is usually a small number of independent functional units that can execute multiple task simultaneously if the data dependencies are met and if necessary resources are available. Today, theoretical studies in the field of cyclic scheduling aims to characterize the scheduling algorithms (worst-case analysis, optimality result, etc.) for real applications in embedded systems as well as in mass production systems. In this thesis, we worked on identifying suitable models, able to take into account the new characteristics of these systems (the nature of dependencies, the heterogeneity of resources, etc..). Several approximation algorithms with performance guarantees have been proposed, and an experimental study to analyze their performance in practice has been established.

2008-2013 Publications

• 2013
  • M. Ayala, A. Benabid, Ch. Artigues, C. Hanen : “The resource-constrained modulo scheduling problem: an experimental study”, Computational Optimization and Applications, vol. 54 (3), pp. 645-673, (Springer Verlag) (2013)
• 2012
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for bounded timed weighted event graphs”, IEEE Transactions on Automatic Control, vol. 57 (5), pp. 1222-1232, (Institute of Electrical and Electronics Engineers) (2012)
  • Ch. Artigues, M. Ayala, A. Benabid, C. Hanen : “Bornes inférieures et supérieures pour l’ordonnancement modulo sous contraintes de ressources”, ROADEF 2012, Angers, France (2012)
  • Ch. Artigues, M. Ayala, A. Benabid, C. Hanen : “Lower and upper bounds for the resource-constrained modulo scheduling problem”, Project management and Scheduling conference, Louvain, Belgium, pp. 82-85 (2012)
• 2011
  • A. Benabid : “Étude du problème RCPSP cyclique”, thesis, phd defence 02/07/2011, supervision Hanen, Claire (2011)
  • A. Benabid, C. Hanen : “Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays”, Journal of Scheduling, vol. 14 (5), pp. 511-522, (Springer Verlag) (2011)
• 2010
  • A. Benabid, C. Hanen : “Performance of Garey Johnson algorithm for pipelined type tasks systems”, International Transactions in Operational Research, vol. 17 (6), pp. 797-808, (Wiley) (2010)
  • A. Benabid, C. Hanen : “Decomposed software pipelining for VLIW with precedence delays and resource constraints”, EURO conference, Lisbon, Portugal (2010)
  • A. Benabid, C. Hanen : “Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors.”, Electronic Notes in Discrete Mathematics, vol. 36 (1), pp. 791-798, (Elsevier) (2010)
  • A. Benabid, C. Hanen : “Performance of Zinder-Roper algorithm for unitary RCPSP with constant precedence latencies”, 11^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2010), Toulouse, France (2010)
• 2009
  • A. Benabid, C. Hanen : “Decomposed software pipelining for cyclic unitary RCPSP with precedence delays”, Multidisciplinary International Conference on Scheduling: Theory and Applications, Dublin, Ireland (2009)
  • A. Benabid, C. Hanen : “Worst case analysis on modulo scheduling for specialized processors systems”, 10^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2009), Nancy, France, pp. 1-12 (2009)
• 2008
  • A. Benabid, C. Hanen : “Performance of the Garey-Johnson algorithm for pipelined task systems”, ALIO/EURO conference on combinatorial optimization, Buenos Aires, Argentina (2008)
  • A. Benabid, C. Hanen, O. Marchetti, A. Munier‑Kordon : “Periodic schedules for Unitary Timed Weighted Event Graphs”, 9^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2008), Clermont-Ferrand, France, pp. 17-31 (2008)