-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
                       GOThA  --  GOThA  --  GOThA
        Groupe de recherche en Ordonnancement Théorique et Appliqué
        -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

                        SEMINAIRES DU GOThA
                        ___________________


LIEU :  LIP6
        8, rue du Capitaine Scott
        75015 Paris
        (voir (*) ci-dessous pour plus de détails)

DATE :  Vendredi 15 octobre 1999

HEURE : 14h


===================================================================
- DEUX exposes à l'ordre du jour - DEUX exposes à l'ordre du jour - 
===================================================================


INTERVENANT :   Francis Sourd
                (LIP6, Paris)
                

TITRE : Nouvelles bornes inférieures pour les problèmes d'atelier
(travail effectué en collaboration de Wim Nuijten, Ilog, Gentilly)
        

RESUME :

La connaissance de bornes  inférieures  de  qualité,  calculables
rapidement,  est  d'une importance capitale pour la résolution de
bon nombre de problèmes d'ateliers, tel le problème du  job-shop.
Nous   proposons   de  nouvelles  idées  simples  qui  permettent
d'améliorer  les  bornes   actuellement   existantes   pour   ces
problèmes.  Au lieu de considérer des sous-ensembles d'opérations
devant être  exécutées  sur  une  même  machine,  cette  approche
considère  des  opérations devant être exécutées sur des machines
différentes pour  déterminer  une  borne  inférieure  à  la  date
d'exécution  d'une  opération  donnée.  Appliquées dans un algor-
ithme de branch-and-bound, ces idées améliorent significativement
le   temps   de   résolution   des  instances  classiques  de  la
littérature.

-------------------------------------------------------------------------------

INTERVENANT :   Philippe Baptiste
                (HEUDIASYC, Compiegne)

TITRE : Jobs identiques et machines à traitement par batch


RESUME :

Nous étudions les  problèmes  d'ordonnancement  dans  lesquels  n
jobs,  de  durées  identiques,  doivent  être ordonnancés sur des
machines à traitement par batches. Tout au long de  cette  étude,
nous  supposerons  que  les  jobs ne sont pas tous disponibles au
même instant et nous nous intéresserons à deux types de  machines
à traitement par batch.

1. Les problèmes à une machine (serial batching problems)  où  la
durée  d'un  batch  est  la somme des durées des jobs qui le com-
posent et où un temps de setup s doit être pris en  compte  entre
deux  batches.
Ces  problèmes  sont  notés 1|r_j|s-batch,r_i,p_i=p|F.

2. Les  problèmes  à  machines  parallèles  où  b  machines  sont
disponibles pour exécuter les jobs. La date de début (respective-
ment de fin) d'un batch est alors la plus petite  date  de  début
(de  fin)  de  ses jobs.
Ces problèmes sont notés 1|p-batch, b<n,r_i, p_i=p|F.

Nous montrerons que sous certaines conditions,  sur  la  fonction
objectif  F,  ces problèmes peuvent être résolus en temps polyno-
mial  par  des  techniques  de  programmation  dynamique.   Notre
approche  est  valide  pour  la  plupart  des critères classiques
(e.g.,   F = m w_i U_i,  F = m w_i C_i,  F = m T_i,  F = C_{max},
F  = T_{max},  F = L_{max}). Nous fermerons  ainsi une dizaine de
problèmes. Certains étaient ouverts même en l'absence de dates de
disponibilités.

-------------------------------------------------------------------------------

Pour tout renseignement sur le contenu de ces exposés, contacter
directement l'(les) intervenant(s) :
                
                

Pour tout renseignement sur les séminaires du GOThA, consulter l'URL :
                http://www.laas.fr/~lopez/gotha/Gotha.html

ou contacter :
                lopez@laas.fr



(*) Comment se rendre au site Scott du LIP6 ?

    1) metro station BIR HAKEIM
    2) RER C station Champs de Mars-Tour Eiffel
    3) metro station LAMOTTE-PIQUET

A partir de 1) et 2) descendre à peu pres sur 300m la rue de la Fédération
et prendre à gauche la rue du Capitaine Scott.
A partir de 3), remonter l'avenue de Suffren sur 800m environ, à gauche la
rue Desaix puis tout de suite à droite la rue du capitaine Scott.

Si vous etes intéressés, il serait souhaitable que je connaisse très
rapidement la liste des participants pour que Philippe Chrétienne la
communique à l'accueil (afin que vous puissiez monter en communiquant
simplement votre nom). Merci.