To: GOThA-tout Subject: Seminaires du GOThA -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- GOThA -- GOThA -- GOThA Groupe de recherche en Ordonnancement Theorique et Applique -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- SEMINAIRES DU GOThA ___________________ LIEU : Institut Blaise Pascal 4, place Jussieu 75252 Paris Cedex 06 Tel : 01 44 27 59 72 Fax : 01 44 27 62 86 Couloir 55-65, salle 105 DATE : Vendredi 7 mars 1997 HEURE : 14h ============================================================================== DEUX exposes a l'ordre du jour - DEUX exposes a l'ordre du jour - DEUX exposes ============================================================================== INTERVENANT : Christelle GUERET (Ecole des Mines de Nantes) TITRE : Une nouvelle borne inferieure pour l'Open-Shop RESUME : Le probleme d'Open-Shop est constitue de N jobs, chacun consti- tue de M taches a executer sur M machines. Les taches d'un job peuvent etre executees dans n'importe quel ordre, mais seulement une a la fois. Une machine ne peut executer plus d'une tache en meme temps. Ce probleme manque d'une bonne borne inferieure. La seule publiee jusqu'a maintenant est la borne inferieure triviale egale au maximum des charges des machines et des durees des jobs. Nous proposons une meilleure borne inferieure pour ce probleme obtenue en resolvant un probleme d'Open-Shop relaxe, Pk. Ce probleme Pk est construit a partir du probleme d'Open-Shop initial en relaxant toutes les contraintes de non-simultaneite des taches des jobs, sauf pour un job Jk. Ce nouveau probleme bien que NP-difficile peut etre resolu tres rapidement par une recherche arborescente se basant sur la resolution de problemes d'empilement. Cette nouvelle borne a ete testee sur des problemes difficiles (a grands gaps) generes aleatoirement. Elle est meilleure que la borne inferieure triviale dans plus de 90%. ------------------------------------------------------------------------------- INTERVENANT : Philippe BAPTISTE (BOUYGUES, St-Quentin-en-Yvelines) TITRE : Contraintes de ressources pour les problemes cumulatifs RESUME : Le probleme cumulatif est une extension du probleme a m machines dans lequel chaque tache utilise une quantite donnee de la res- source. Le but de cet expose est de presenter : (1) Des conditions necessaires d'existence d'une solution a une instance du probleme cumulatif. (2) Des regles permettant d'ajuster les dates de debut au plus tot et les dates de fin au plus tard des taches d'une instance d'un probleme cumulatif. Les resultats presentes sont bases sur deux relaxations ; une relaxation "totalement elastique" du probleme cumulatif (qui se ramene a l'etude du probleme preemptif a une machine) et une relaxation "partiellement elastique", plus fine que la precedente, qui peut etre vue comme une variante "entiere" de la relaxation pseudo-preemptive pour le probleme a m-machines proposee par J. Carlier et E. Pinson. Dans les deux cas, des algorithmes bases sur les regles d'ajustement introduites precedemment sont proposes. Ils etendent de fait les algorithmes d'ajustement pour le cas disjonctif utilises avec succes sur le probleme du Job-Shop. Des resultats experimentaux sur le "Resource Constrained Project Scheduling Problem" (RCPSP) montrent que, pour un certain type d'instance au moins, cette approche semble prometteuse. ------------------------------------------------------------------------------- Pour tout renseignement sur le contenu de ces exposes, contacter directement les intervenants : gueret@emn.fr baptiste@utc.fr Pour tout renseignement sur les seminaires du GOThA, consulter l'URL : http://www.laas.fr/~lopez/gotha/seminaires.html ou contacter : lopez@laas.fr