Soutenance de thèse de Ahmed Gara-Ali le mardi19 juillet 2016 à 14h dans l' amphithéâtre Gosse - Site Viallet - Grenoble INP
Intitulée : « Ordonnancement de tâches et de périodes d’indisponibilité de durée variable »
Membres du Jury :
Résumé de thèse:
- M. Vincent T'KINDT, Professeur, Ecole Polytechnique de l’Université de Tours, Rapporteur
- M. Farouk YALAOUI, Professeur, Université de Technologie de Troyes, Rapporteur
- M. Julien MONCEL, Maître de conférences, Université Toulouse 1 - IUT Rodez, Examinateur
- M. Bernard PENZ, Professeur, Grenoble INP, Examinateur
- M. Éric SANLAVILLE, Professeur, Université du Havre, Examinateur
- Mme. Marie-Laure ESPINOUSE, Professeur, Université Grenoble Alpes, IUT1 Directrice de thèse
Résumé de thèse:
Dans cette thèse, nous nous intéressons aux problèmes d'ordonnancement simultané de tâches et de périodes d'indisponibilité. Dans un premier temps, nous réalisons une revue de littérature sur la prise en compte des indisponibilités dans les problèmes d'ordonnancement. Ensuite, nous définissons un modèle général qui englobe des modèles existants de la littérature pour des ateliers à une machine et à machines parallèles. Une approche globale de résolution basée sur les problèmes d'affectation linéaire a été développée. Cette approche permet de résoudre le modèle général comme un simple problème d'affectation. Un grand nombre de critères d'optimisation et de modèles de maintenance peuvent être traités en utilisant cette approche, fournissant ainsi l'accès à tous les modèles qui ont souvent été étudiés séparément dans la littérature. Les résultats élaborés avec cette approche ont permis de résoudre des problèmes d'ordonnancement non traités avant et aussi de généraliser et améliorer des résultats antérieurs. Nous proposons, en dernier lieu, une étude d'un problème flow shop à deux machines en présence d'une période d'indisponibilité sur la deuxième machine. Une étude de complexité est menée sur le problème. Ensuite, nous définissons des propriétés d'optimalité. En se basant sur ces propriétés, trois méthodes de résolution exacte sont proposées; une méthode énumérative, un programme linéaire et une méthode basée sur l'approche de séparation et évaluation B&B. Une analyse expérimentale est présentée afin d'évaluer les performances de ces méthodes.
Mots clés: période d'indisponibilité, maintenance, ordonnancement simultané, durée variable
Abstract:
In classical scheduling problems, machines are assumed to be continuously available. However, in a real manufacturing system, machine may become unavailable during the scheduling period due to preventive maintenance. In this dissertation, we are interested in the problems of jointly scheduling jobs and unavailability periods. We start our study by introducing a general framework for scheduling problems and we present a review of the scheduling problems with unavailability periods. Then, we consider a general model for scheduling jobs on single-machine and unrelated parallel-machines with maintenance interventions. A unified approach is presented to solve this model as an assignment problem. A large number of performance criteria and maintenance models can be treated in this way, thus providing access to models that have often been studied separately in the published literature. Finally, we focus on the problem of a two-machine flow-shop makespan scheduling with the deteriorating maintenance period on the second machine. Then, we establish some conditions of the optimal schedule. In order to solve the problem, we proposed different exact methods: enumerative method, mixed-integer programming (MIP) model and a branch & bound algorithm. Numerical experiments are reported for all the proposed methods.
Key words: unavailability constraints, maintenance activities, scheduling, variable duration
Publications :
http://www.sciencedirect.com/science/article/pii/S092552731400067X
http://www.sciencedirect.com/science/article/pii/S0377221715011868
http://www.sciencedirect.com/science/article/pii/S0305048316000360
Mots clés: période d'indisponibilité, maintenance, ordonnancement simultané, durée variable
Abstract:
In classical scheduling problems, machines are assumed to be continuously available. However, in a real manufacturing system, machine may become unavailable during the scheduling period due to preventive maintenance. In this dissertation, we are interested in the problems of jointly scheduling jobs and unavailability periods. We start our study by introducing a general framework for scheduling problems and we present a review of the scheduling problems with unavailability periods. Then, we consider a general model for scheduling jobs on single-machine and unrelated parallel-machines with maintenance interventions. A unified approach is presented to solve this model as an assignment problem. A large number of performance criteria and maintenance models can be treated in this way, thus providing access to models that have often been studied separately in the published literature. Finally, we focus on the problem of a two-machine flow-shop makespan scheduling with the deteriorating maintenance period on the second machine. Then, we establish some conditions of the optimal schedule. In order to solve the problem, we proposed different exact methods: enumerative method, mixed-integer programming (MIP) model and a branch & bound algorithm. Numerical experiments are reported for all the proposed methods.
Key words: unavailability constraints, maintenance activities, scheduling, variable duration
Publications :
http://www.sciencedirect.com/science/article/pii/S092552731400067X
http://www.sciencedirect.com/science/article/pii/S0377221715011868
http://www.sciencedirect.com/science/article/pii/S0305048316000360