To: GOThA-tout Subject: Seminaires du GOThA -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- GOThA -- GOThA -- GOThA Groupe de recherche en Ordonnancement Theorique et Applique -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- SEMINAIRES DU GOThA ___________________ LIEU : LIP6 Universite Pierre et Marie Curie 4, place Jussieu 75252 Paris Cedex 06 Tel : 01 44 27 35 94 Fax : 01 44 27 62 86 Couloir 55-65 DATE : Vendredi 19 decembre 1997 HEURE : 14h ============================================================================== DEUX exposes a l'ordre du jour - DEUX exposes a l'ordre du jour - DEUX exposes ============================================================================== INTERVENANT : Stephane DAUZERE-PERES (EMN, Nantes) TITRE : Minimisation du nombre de jobs en retard dans le probleme d'ordonnancement a une machine RESUME : Nous nous interesserons au probleme general d'ordonnancement a une machine, avec des dates de debut au plus tot et des dates de fin au plus tard, avec pour objectif la minimisation du nombre de jobs en retard. Nous rappellerons d'abord les resultats les plus connus sur ce probleme. Nous montrerons comment nous avons pu etendre un cas ou la resolution du probleme peut se faire en temps polynomial. Apres avoir presente les formulations classiques en programmation lineaire en nombres entiers pour le probleme d'ordonnancement a une machine, en discutant leurs avantages et leurs inconvenients, nous developperons deux formulations pour la minimisation du nom- bre de jobs en retard. Ces formulations permettent d'obtenir de bonnes bornes inferieures par relaxation lineaire. Nous mon- trerons qu'une formulation domine l'autre. Nous discuterons ensuite l'ajout de coupes a la meilleure formulation, et des resultats numeriques seront presentes. Nous terminerons l'expose en evoquant de nouveaux resultats qui nous permettent d'introduire une nouvelle formulation, necessi- tant moins de variables que les precedentes. ------------------------------------------------------------------------------- INTERVENANT : Marc SEVAUX (EMN, Nantes) TITRE : Modeles et procedures de resolution pour la planification en temps continu RESUME : Dans les problemes classiques de planification de la production, pour un horizon connu et une prevision de demande calculee, le but est de determiner les quantites a produire pour chacun des produits de facon a minimiser le cout de sotckage et de rupture de stock. L'horizon est alors discretise en periodes de meme longueur, et le surplus (positif=stock, negatif=rupture de stock) est calcule a la fin de chaque periode. Dans de nombreux systemes de production (automobile, embouteil- lage, papier, ...), les matieres premieres arrivent de maniere continue et les produits finis sortent eux aussi de maniere con- tinue. Par ailleurs, les demandes sont souvent exprimees sous forme d'un taux de production et n'evoluent pas toujours a inter- valles reguliers. Dans un tel cas, le modele de planification de la production en temps continu semble bien adapte. Au lieu de quantites, des taux de demande et des taux de production sont consideres. L'objectif est de minimiser le cout, non plus en fin de periode, mais sur la totalite de l'horizon, et le niveau de surplus est considere a tout instant. Pour la resolution de ce probleme, on presentera differents modeles mathematiques. Un procedure iterative utilisant un modele lineaire permet de resoudre efficacement le probleme de la plani- fication en temps continu. ------------------------------------------------------------------------------- Pour tout renseignement sur le contenu de ces exposes, contacter directement l'(les) intervenant(s) : dauze@emn.fr sevaux@emn.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