Ordonnancement des systemes flexibles de production sous contraintes de disponibilite des ressources, Scheduling flexible production systems under resource availability constraints

Sadia Azem

Description

Sous la direction de Stéphane Dauzere-Peres
Thèse soutenue le 22 juin 2010: Ecole nationale supérieure des mines - Saint-Etienne
La majeure partie des travaux sur les problèmes d’ordonnancement se placent dans le contexte où les ressources sont disponibles en permanence. Ce qui en réalité n’est pas toujours le cas. Nous nous plaçons dans le contexte d’indisponibilités connues ; nous nous intéressons plus particulièrement aux problèmes de type job shop avec des périodes d’indisponibilité flexibles et des tâches pouvant éventuellement être interrompues par les périodes d’indisponibilité. L’intégration de ces contraintes rend les problèmes d’ordonnancement nettement plus difficiles à résoudre. La flexibilité que nous considérons peut être relative à au moins l’un des points suivants : déplacement de la période d’indisponibilité dans une fenêtre de temps, modification de la durée de la période d’indisponibilité, interruption d’une tâche par une période d’indisponibilité, ensuite reprise avec une éventuelle pénalité.Dans cette thèse, nous avons proposé des modèles mathématiques pour le problème. En plus de la résolution des problèmes considérés, le but de ces modélisations est de permettre d’analyser l'impact des différentes contraintes et d'évaluer la qualité des méthodes approchées que nous proposons. Ces dernières permettent de construire très rapidement un ordonnancement en se basant sur des règles de priorité. Les solutions sont aussi utilisées pour notre approche basée sur la génération de colonnes. Cette approche s’adapte bien à différents fonctions objectif et permet d'intégrer relativement facilement plusieurs contraintes. De nombreuses expérimentations ont été menées pour valider les méthodes proposées.
-Ordonnancement
-Flexibilité
-Optimisation
-Contraintes de disponibilité
-Systèmes industriels
-Génie logiciel
-Modélisation mathématique
-Méthodes approchées
-Génération de colonnes
In most of the machine scheduling literature, resources are assumed to be continuously available which is not always true. We deal with the context of unavailability known a priori; we are particularly interested in job-shop scheduling problems with flexible unavailability periods and tasks that can eventually be interrupted by unavailability periods. Integrating these constraints increase the complexity of the scheduling problems. We deal with flexibility that is related to at least one of the following points: moving the unavailability period in a time window, modification of the duration of the unavailability period, interruption of a task by an unavailability period, then resumed with a possible penalty.In this thesis, we propose mathematical models for the problem. In addition to the resolution of the considered problems, the aim of this modeling is to allow for the analysis of the impact of different constraints and evaluation of the quality of the approximate methods and the column generation approach we develop. The approximate methods construct in very short time a schedule based on priority rules. The solutions are also used in our column generation approach. This approach adapts well to various objective functions and allows relatively easily for the integration of several constraints. Many experiments have been performed to validate the designed methods.
-Scheduling
-Flexibility
-Optimization
-Availability constraints
-Industrial system
-Software programming
-Mathematical modeling
-Approximate methods
-Column generation
Source: http://www.theses.fr/2010EMSE0574/document

Sujets

• Ordonnancement
• Flexibilité
• Optimisation
• Génie logiciel
• Génération de colonnes

Informations

• Publié par: Thesee
• Nombre de lectures: 84
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

N° d’ordre : 2010 EMSE 0574

THÈSE
présentée par

Sadia AZEM
pour obtenir le grade de
Docteur de l’École Nationale Supérieure des Mines de Saint-Étienne
Spécialité : Génie Industriel

ORDONNANCEMENT DES SYSTEMES FLEXIBLES DE
PRODUCTION SOUS CONTRAINTES DE DISPONIBILITE DES
RESSOURCES


Soutenue à Gardanne, le 22 juin 2010

Membres du jury


Président : Eric PINSON Professeur, Université Catholique de l'Ouest, Angers
Rapporteurs : Jean-Charles BILLAUT Professeur, Ecole Polytechnique, Tours
Bernard PENZ Professeur, Institut National Polytechnique, Grenoble
Examinateur(s) : Ammar OULAMARA Maitre de Conférences HDR, Ecole des Mines de Nancy
Directeur(s) de thèse : Stéphane DAUZERE-PERES Professeur, Ecole des Mines de Saint-Etienne, Gardanne
Riad AGGOUNE Responsable d'Unité, Centre de Recherche Henri Tudor,
Luxembourg
Spécialités doctorales : Responsables :
SCIENCES ET GENIE DES MATERIAUX J. DRIVER Directeur de recherche – Centre SMS
MECANIQUE ET INGENIERIE A. VAUTRIN Professeur – Centre SMS
GENIE DES PROCEDES G. THOMAS Professeur – Centre SPIN
SCIENCES DE LA TERRE B. GUY Maître de recherche – Centre SPIN
SC ET GENIE DE L’ENVIRONNEMENT J. BOURGOIS Professeur – Centre SITE
MATHEMATIQUES APPLIQUEES E. TOUBOUL Ingénieur – Centre G2I
INFORMATIQUE O. BOISSIER Professeur – Centre G2I
IMAGE, VISION, SIGNAL JC. PINOLI Professeur – Centre CIS
GENIE INDUSTRIEL P. BURLAT Professeur – Centre G2I
MICROELECTRONIQUE Ph. COLLOT Professeur – Centre CMP

Enseignants-chercheurs et chercheurs autorisés à diriger des thèses de doctorat (titulaires d’un doctorat d’État ou d’une HDR)
AVRIL Stéphane MA Mécanique & Ingénierie CIS
BATTON-HUBERT Mireille MA Sciences & Génie de l'Environnement SITE
BENABEN Patrick PR 1 Sciences & Génie des Matériaux CMP
BERNACHE-ASSOLANT Didier PR 0 Génie des Procédés CIS
BIGOT Jean-Pierre MR SPIN
BILAL Essaïd DR Sciences de la Terre
BOISSIER Olivier PR 1 Informatique G2I
BOUCHER Xavier MA Génie Industriel G2I
BOUDAREL Marie-Reine PR 2 iel DF
BOURGOIS Jacques PR 0 Sciences & Génie de l'Environnement SITE
BRODHAG Christian DR &de l'Envirent
BURLAT Patrick PR 2 Génie industriel G2I
COLLOT Philippe PR 1 Microélectronique CMP
COURNIL Michel PR 0 Génie des Procédés SPIN
DAUZERE-PERES Stéphane PR 1 Génie industriel CMP
DARRIEULAT Michel IGM Sciences & Génie des Matériaux SMS
DECHOMETS Roland PR 1 Sciences & Génie de l'Environnement SITE
DESRAYAUD Christophe MA Mécanique & Ingénierie SMS
DELAFOSSE David PR 1 des Matériaux SMS
DOLGUI Alexandre PR 1 Génie Industriel G2I
DRAPIER Sylvain PR 2 nierie SMS
DRIVER Julian DR 0 Sciences & Génie des Matériaux SMS
FEILLET Dominique PR 2 Génie Industriel CMP
FOREST Bernard PR 1 des Matériaux CIS
FORMISYN Pascal PR 1 Sciences & Génie de l'Environnement SITE
FORTUNIER Roland PR 1 Sciences & Génie des Matériaux SMS
FRACZKIEWICZ Anna DR atériaux SMS
GARCIA Daniel MR Génie des Procédés SPIN
GIRARDOT Jean-Jacques MR Informatique G2I
GOEURIOT Dominique MR Sciences & Génie des Matériaux SMS
GRAILLOT Didier DR Sciences & Génie de l'Environnement SITE
GROSSEAU Philippe MR Génie des Procédés SPIN
GRUY Frédéric MR
GUY Bernard MR Sciences de la Terre SPIN
GUYONNET René DR Génie des Procédés
HERRI Jean-Michel PR 2 SPIN
INAL Karim PR 2 Microélectronique CMP
KLÖCKER Helmut DR Sciences & Génie des Matériaux SMS
LAFOREST Valérie CR Sciences & Génie de l'Environnement SITE
LERICHE Rodolphe CR CNRS Mécanique et Ingénierie SMS
LI Jean-Michel EC (CCI MP) Microélectronique CMP
LONDICHE Henry MR Sciences & Génie de l'Environnement SITE
MALLIARAS George Grégory PR 1 Microélectronique CMP
MOLIMARD Jérôme MA Mécanique et Ingénierie SMS
MONTHEILLET Frank DR 1 CNRS Sciences & Génie des Matériaux SMS
PERIER-CAMBY Laurent PR 2 Génie des Procédés SPIN
PIJOLAT Christophe PR 1
PIJOLAT Michèle PR 1 océdés SPIN
PINOLI Jean-Charles PR 0 Image, Vision, Signal CIS
STOLARZ Jacques CR Sciences & Génie des Matériaux SMS
SZAFNICKI Konrad MR Sciences & Génie de l'Environnement SITE
THOMAS Gérard PR 0 Génie des Procédés SPIN
TRIA Assia Microélectronique CMP
VALDIVIESO François MA Sciences & Génie des Matériaux SMS
VAUTRIN Alain PR 0 Mécanique & Ingénierie SMS
VIRICELLE Jean-Paul MR Génie des procédés SPIN
WOLSKI Krzysztof DR des Matériaux SMS
XIE Xiaolan PR 1 Génie industriel CIS

Glossaire : Centres :
PR 0 Professeur classe exceptionnelle SMS Sciences des Matériaux et des Structures
èrePR 1 catégorie Pr 1 SPIN Sciences des Processus Industriels et Naturels
èmePR 2 Professeur 2 catégorie SITE Sciences Information et Technologies pour l’Environnement
MA(MDC) Maître assistant G2I Génie Industriel et Informatique
DR Directeur de recherche CMP Centre de Microélectronique de Provence
Ing. Ingénieur CIS Centre Ingénierie et Santé
MR(DR2) Maître de recherche
CR Chargé de recherche
EC Enseignant-chercheur
IGM Ingénieur général des mines
Dernière mise à jour le : 9 mars 2010 A ceux que j’aime2Remerciements
Jetiens`at´emoignermaprofondegratitude`aSt´ephaneDAUZERE-PERES,Professeur`al’Ecole
Nationale Sup´erieure des Mines de Saint-Etienne, et `a Riad AGGOUNE, Responsable d’Unit´e
au Centre de Recherche Henri Tudor du Luxembourg, sans qui ce travail n’aurait pas vu le
jour, pour m’avoir encadr´ee, pour leur rigueur, leur exp´erience, leurs pr´ecieuses orientations et
leurs conseils avis´es qui m’ont guid´ee tout au long du parcours. Mes remerciements les plus
vifs, empreints d’une grande reconnaissance `a Pascal BOUVRY, Professeur `a l’Universit´e du
Luxembourg, pour m’avoir si bien accueillie au sein de son ´equipe durant la p´eriode pass´ee `a
l’Universit´e. Je les remercie aussi pour leur soutien et les moyens mis `a ma disposition.
JeremercieJean-CharlesBILLAUT,Professeur`al’EcolePolytechniquedeTours,etBernard
PENZ, Professeur `a l’Institut Polytechnique de Grenoble, d’avoir accept´e d’ˆetre rapporteurs de
cette th`ese. Merci `a vous ainsi qu’`a Eric PINSON, Professeur `a l’Universit´e Catholique de
l’Ouest `a Angers, et Ammar OULAMARA, Maitre de Conf´erences HDR de l’Ecole des Mines
de Nancy, pour l’int´erˆet et l’attention que vous avez accord´e `a ce travail et de m’avoir fait
l’honneur de faire partie de mon Jury. Je vous t´emoigne ma gratitude pour ces ´echanges en-
richissants.
Je tiens `a exprimer ma grande gratitude `a Christian ARTIGUES, Charg´e de Recherche
HDR au LAAS CNRS `a Toulouse, de m’avoir propos´e son aide ; et d’avoir suscit´e davantage
mon int´erˆet pour la recherche pendant mon stage de master.
Ma profonde reconnaissance va ´egalement au Gouvernement du Luxembourg, plus partic-
uli`erement au Minist`ere de la Culture, de l’Enseignement Sup´erieur et de la Recherche, et au
Fonds National de la Recherche, pour le financement de cette ´etude sans lequel cette derni`ere
n’aurait pas pu ˆetre men´ee. Je les remercie chaleureusement pour leurs encouragements et leur
3compr´ehension.
Je suis aussi reonnaissante `a l’Ecole Nationale Sup´erieure des Mines de Saint-Etienne et
l’Universit´e du Luxembourg pour les moyens d´eploy´es pour la bonne r´ealisation de ce travail.
Mes remerciements vont `a leurs personnels que j’ai crois´es ou cotoy´es pour leur gentillesse et
leurprofessionnalisme. Jet´emoigne,plusparticuli`erement,mareconnaissanceauxmembresdes
´equipes SFL et ILIAS de m’avoir offert un environnement de travail agr´eable et ´epanouissant
et pour leur soutien.
Je t´emoigne mon ineffable reconnaissance `a mes proches pour leur soutien infaillible et pour
avoir fait de moi la personne heureuse que je suis. Je remercie en particulier ma famille et
encore plus particuli`erement mon p`ere, ma m`ere , mes fr`eres et mes soeurs qui ont ´et´e pr´esents
pour moi depuis toujours.
Pour finir, je remercie toute personne ayant contribu´e de loin ou de pr`es `a l’existence de ce
travail.
Jegarderaitoujoursunvifsouvenirdecettemerveilleuseaventurequim’abeaucoupapport´e
et m’a surtout tant appris sur moi-mˆeme. J’ai essay´e d’en vivre pleinement et d’en appr´ecier
chaque moment mˆeme les plus durs.
4Contents
0.1 Objectif de la th`ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
0.2 Organisation du m