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. / 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.
| Identifer | oai:union.ndltd.org:theses.fr/2010EMSE0574 |
| Date | 22 June 2010 |
| Creators | Azem, Sadia |
| Contributors | Saint-Etienne, EMSE, Dauzère-Pérès, Stéphane |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0024 seconds