Le concept d'énergie a été introduit afin de raisonner simultanément sur le temps et les ressources. Une énergie correspond au produit d'un temps par une quantité de ressource. On obtient ainsi une grandeur agrégée directement assimilable à une surface et qui peut être exprimée en unités de [ ressource x temps ] (hommes.jour, kilowatts.heure, ...). Ce concept est d'un intérêt capital, essentiellement à deux titres.
Les déductions liées au raisonnement énergétique font appel à des bilans d'utilisation des ressources sur certains intervalles temporels, ce qui entraîne l'identification et le calcul de différentes énergies. Sur un intervalle de temps, l'énergie peut en effet être fournie par une ressource ou consommée par une tâche. Dans ce dernier cas, on distingue sa consommation minimale (ou consommation obligatoire) de sa consommation maximale sur l'intervalle.
Dans son livre page 274, Kenneth Baker, inspiré par Victor Zaloom, introduit un couplage du temps et des ressources pour aborder les problèmes d'ordonnancement de type cumulatif. La différence essentielle avec notre approche est qu'il raisonne à partir des profils d'utilisations de ressource instantanées.
Dès 1989, Pierre Lopez et Jacques Erschler ont étendu la notion de partie obligatoire à celle de consommation obligatoire d'énergie pour développer les bases du raisonnement énergétique pour l'analyse de l'admissibilité des solutions dans les problèmes d'ordonnancement.
Pour Howard Beck, le but est d'identifier la violation de contraintes ou la menace de viol de contraintes. Sa méthode repose sur le concept d'« habograph », tableau où chaque case correspond à une période et contient le rapport entre la demande agrégée et la capacité agrégée en cette case. Plus ce rapport est proche de l'unité, plus une contrainte est menacée sur cette période ; elle est violée lorsqu'il est supérieur à l'unité.
La différence fondamentale avec notre approche est qu'aucune hypothèse n'est faite sur la répartition de l'énergie demandée puisque durée et intensité ne sont pas connues. Dans ce contexte, l'analyse des charges ne peut détecter que des violations et non des actualisations de fenêtres empêchant la violation. D'autre part, le temps est discrétisé en périodes unitaires, comme le fait Baker ; ceci oblige à énumérer tous les intervalles possibles, ce qui, pour des problèmes de taille industrielle, reste illusoire.
La détection d'une incohérence globale entraîne la définition d'un nouveau problème, en relaxant par exemple certains paramètres comme la capacité de la ressource. Dans la suite, on admettra la cohérence globale des problèmes ; on peut alors envisager d'expliciter de nouvelles propositions consistant à détecter des incohérences locales.
Depuis, de nombreux auteurs se sont intéressés, ont repris, amélioré et étendu le raisonnement énergétique pour le traitement de problèmes d'ordonnancement (Philippe Baptiste, Claude Le Pape & Wim Nuijten ; Emmanuel Néron & Jacques Carlier ; Luc Mercier & Pascal Van Hentenryck, ...). Ne détaillons qu'une de ces réalisations au travers d'une utilisation commerciale de la bibliothèque SCHEDULER des produits d'optimisation d'ILOG (primitives comme ilo_consumes).
@inproceedings{bec92,
author = "H. Beck",
title = "Constraint monitoring in {TOSCA}",
booktitle = "Proc. of AAAI Spring Symposium: Practical approaches to planning and scheduling",
year = 1992,
address = "Stanford"
}
@inproceedings{ers89,
author = "J. Erschler, P. Lopez, C. Thuriot",
title = "Scheduling under time and resource constraints",
booktitle = "Proc. of Workshop on Manufacturing Scheduling, 11th IJCAI",
year = 1989,
address = "Detroit, USA"
}
@article{ers91,
author = "J. Erschler and P. Lopez and C. Thuriot",
title = "Raisonnement temporel sous contraintes de ressources et problèmes d'ordonnancement",
journal = "Revue d'Intelligence Artificielle",
year = 1991,
volume = 5,
number = 3,
pages = "7--36"
}
@article{lah82,
author = "A. Lahrichi",
title = "Ordonnancements : les notions de bosse, de partie obligatoire et leurs applications aux problèmes cumulatifs",
journal = "C.R. Acad. Sc. Paris",
year = 1982,
volume = "t.294",
number = "I-16",
pages = "209--211"
}
@phdthesis{lop91,
author = "P. Lopez",
title = "Approche énergétique pour l'ordonnancement de tâches sous contraintes de temps et de ressources",
type = "Thèse de {Doctorat}",
school = UPS,
address = "Toulouse",
year = "1991"
}
@article{lop92,
author = "P. Lopez and J. Erschler and P. Esquirol",
title = "Ordonnancement de tâches sous contraintes : une approche énergétique",
journal = "Automatique, Productique, Informatique Industrielle",
year = 1992,
volume = 26,
pages = "453--481"
}
@inproceedings{lop96a,
author = "P. Lopez and P. Esquirol",
title = "Consistency enforcing in scheduling: A general formulation based on energetic reasoning",
booktitle = "Proc. of the 5$^{th}$ International Workshop on Project Management and Scheduling",
address = "Poznan, Poland",
pages = "155--158",
year = 1996,
}
@misc{mer05,
author = "L. Mercier and P. Van Hentenryck",
title = "Strong polynomiality of resource constraint propagation",
howpublished = "Brown University report",
year = 2005,
}
@article{ner01,
author = "E. Néron and P. Baptiste and J.N.D. Gupta",
title = "Solving Hybrid Flow Shop problem using energetic reasoning and global operations",
journal = "Omega",
year = 2001,
volume = 29,
pages = "501--511"
}
@article{zal71,
author = "V. Zaloom",
title = "On the resource constrained project scheduling problem",
journal = "AIIE Transactions",
year = 1971,
volume = 3,
number = 4,
pages = "302--305"
}