Journée GOThA - Ordonnancement avec contraintes d'énergie et/ou de ressources périssables

Dynamic speed-scaling, which varies the server speed with the number of tasks, has been proposed to balance energy and delay costs in data-centers. The direct numerical computation of these costs under the optimal speed-scaling policy does not give much insight into their behavior. By making an analogy with the Erlang-C model, we propose approximations for the mean energy consumed per task and the mean delay in systems with dynamic speed-scaling. These approximations are related to those by Halfin and Whitt for the Erlang-C system. The applicability of these approximations is illustrated with the help of comparison with the exact optimal routing policy in data-centers.
-> Joint work with A.E. Tugui (ATM, Bucarest), Maaike Verloop (IRIT)

La production de chimiothérapies est un processus où des contraintes non classiques viennent s'ajouter au problème d'ordonnancement. Par exemple, les matières premières (cytotoxiques) ont la particularité d'être très volatiles une fois ouverts, et aussi très onéreuses. Les deadlines d'utilisation sont fonction des décisions d'ordonnancement (elles s'apparentent à un délai maximum d'utilisation). Un critère lié au retard de la production est considéré et un critère relatif à la quantité perdue est introduit. Un modèle simplifié du problème ainsi que le modèle complet seront présentés, avec des méthodes de résolution et les résultats de ces méthodes.

In this talk we consider coordinated production and interstage batch delivery scheduling problems, where a third-party logistics provider (3PP) delivers semi-finished products in batches from one production location to another production location belonging to the same manufacturer. A batch cannot be delivered until all jobs of the batch are completed at the upstream stage. The 3PP is required to deliver each product within T time units since its release at the upstream stage. We consider two transportation modes: regular transportation, for which delivery departure times are fixed at the beginning, and express transportation, for which delivery departure times are flexible. We analyze the complexity of the problems faced by the 3PP when either the manufacturer dominates or the 3PP dominates. In this context, we investigate the complexity of several problems, providing polynomiality and NP-completeness results.
-> Joint work with Mohamed Ali Aloulou, Liangliang Fu (LAMSADE), Mikhail Kovalyov (United Institute of Informatics Problems, Minsk, Belarus)

In the context of the Arrowhead European project, we investigate production flexibility and energy efficiency in a discrete manufacturing plant: the Sarel electrical enclosures, cabinets and accessories production site. We want to evaluate whether it is worth considering energy costs in the scheduling process and, in particular, what kinds of compromises are worth considering between energy and intermediate or final product inventory. Several techniques can be used, separately or in a combination, to solve the scheduling problem, e.g., mixed-integer linear programming, constraint programming, meta-heuristics, etc. In our current version, constraint programming is used to generate an initial schedule, which is then improved using local search and mixed integer programming.
To assess the quality of this combination, we have used 40 benchmark instances from the literature, initially including no energy cost, to which we have added relevant energy consumption data. This enables both the verification of the optimisation algorithm when energy costs are not taken into account (by comparison with results published by others) and the evaluation of its capacity to generate near-optimal schedules in a reasonable computing time.
-> Travaux communs avec Chloé Desdouits, Jean-Louis Bergerand et Claude Le Pape (Schneider)

Cet exposé est dédié à une présentation des lignes de recherche de l'équipe ROC (Recherche Opérationnelle/Optimisation Combinatoire/Contraintes) sur la thématique ordonnancement & énergie.

Un problème important dans les processeurs est la dissipation de chaleur. L'énergie consommée pendant les calculs est transformée en chaleur, et si le processeur surchauffe il va en général s'imobiliser un court instant, le temps que le système de refroidissement fasse son effet. Ces moments inactifs dégradent alors les performances. Mais comme certaines tâches sont plus gourmandes en énergie que d'autres, il y a la possibilité d'influencer la température du processeur par un ordonnancement des tâches. La température (le froid pour être précis), peut être vu comme une ressource nécessaire au calcul, et qui se renouvelle de manière régulière. Cette resource donne lieu alors à de nouveaux problèmes d'ordonnancement, "temperature-aware scheduling" en anglais.
Après une présentation du modèle, un état de l'art sera donné sur les différents algorithmes d'approximation qui ont été proposés dans ce domaine.

Cette présentation sera consacrée au problème d'allocation de machines virtuelles, sous certaines contraintes, dans le domaine du Cloud Computing dans l'optique de minimiser la consommation d'énergie sans impacter la performance du système. Le problème d'allocation de ressources est un problème complexe qui nécessite des heuristiques efficaces pour le résoudre dans un temps acceptable. La modélisation de l'architecture matérielle et logicielle, une proposition de résolution par algorithme génétique et une résolution par programmation linéaire en nombres entiers feront l'objet de cette présentation.
-> Travaux communs avec Georges Da Costa (IRIT), Thierry Monteil, Christian Artigues et Pierre Lopez (LAAS)

We investigate how to share a common resource among multiple classes of customers in presence of impatient users. We aim at obtaining the structure of the optimal resource allocation strategy in such systems. We tackle this problem with two different methods: (1) by scaling the stochastic process and solving the resulting fluid model, and (2) by developing a heuristic using the Multi-Armed Restless Bandits theory. Extensive simulations show that the performances of the obtained solutions are nearly-optimal.
-> Joint work with Maialen Larranaga (LAAS and IRIT) and Maaike Verloop (IRIT)