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 05 Tel : 01 44 27 59 72 Fax : 01 44 27 62 86 Couloir 55-65 DATE : Vendredi 23 mai 1997 HEURE : 14h ============================================================================== DEUX exposes a l'ordre du jour - DEUX exposes a l'ordre du jour - DEUX exposes ============================================================================== INTERVENANT : Pascal RICHARD (E3I, Tours) TITRE : Une semantique operationnelle des programmes lineaires en nombres entiers avec les reseaux de Petri temporises RESUME : Un reseau de Petri temporise sequentiel (STPN) est un RdP dont chaque transition partage une place d'exclusion mutuelle ; aucune autre hypothese n'est faite sur le reste du reseau. Nous montrons que la resolution de tout programme lineaire en nombres entiers (PLE) peut etre interpretee comme la recherche d'un ordonnance- ment optimal pour atteindre un marquage final. La conversion d'un PLE en un STPN repose sur une nouvelle condition suffisante d'accessibilite pour l'equation d'etat. Le cas des programmes lineaires simples peut etre traite de la meme facon, en con- siderant un reseau continu. La dualite dans les programmes lineaires est alors interpretee par la dualite du reseau de Petri correspondant. ------------------------------------------------------------------------------- INTERVENANT : Laurent PERIDY (Universite Catholique de l'Ouest, Angers) TITRE : Le probleme de job-shop : arbitrages et ajustements RESUME : L'objectif de cet expose est de presenter des regles d'eliminations permettant de reduire l'espace des solutions du probleme de job-shop J//Cmax. L'idee de base est de montrer que certaines configurations ne peuvent conduire à un ordonnancement de duree inferieure ou egale à UB (une borne superieure du prob- leme). Nous avons applique ce concept à deux niveaux : au niveau de la machine (operations locales), et au niveau global sur le job-shop complet (operations globales). Dans une premiere par- tie, nous presentons un schema general pour toute une famille d'arbitrages englobant les travaux de Carlier et Pinson. Ce modele est base sur l'etude du positionnement d'un ensemble de tâches par rapport à un autre ensemble de tâches. Sur la base de ces differentes configurations, nous caracterisons des posi- tionnements invariants dans tout ordonnancement de duree inferieure ou egale à UB. L'information supplementaire obtenue par ce modele n'etant pas suffisante pour resoudre certaines instances type LA21, La29, nous avons essaye de re-introduire les interactions entre les machines et ainsi travailler sur le prob- leme complet. L'objectif dans la deuxieme partie est d'imposer une condition et de verifier si celle-ci est valide avec le prob- leme complet en propageant les consequences à l'aide des opera- tions locales. Dans le cas d'une condition non valide, nous en deduisons que sa negation est vraie dans toute solution de duree inferieure ou egale à UB. Les conditions utilisees sont : une tâche doit demarrer apres un instant donne, à un instant fixe ou pendant un intervalle de temps. De plus, nous avons defini la notion d'incompatibilite entre conditions et introduit la notion de graphe d'incompatibilites. Sur ce dernier, la non existence d'un stable de cardinalite n*m nous permet de statuer à l'absence de solution de duree inferieure ou egale à UB pour le probleme. ------------------------------------------------------------------------------- Pour tout renseignement sur le contenu de ces exposes, contacter directement l'(les) intervenant(s) : richardp@univ-tours.fr Laurent.Peridy@ima.uco.fr Pour tout renseignement sur les seminaires du GOThA, consulter l'URL : http://www.laas.fr/~lopez/gotha/Gotha.html ou contacter : lopez@laas.fr