Soutenance Th
Forum 'Annonces' - Sujet créé le 2004-11-09
Thèse Philippe Mauguière
Cifre Volume Software (université de Tours)
Soutenance le 30 novembre 2004
Etudes de problèmes d'ordonnancement disjonctifs avec contraintes de disponibilité des ressources et de préparation.
Composition du jury :
Jean-Charles Billaut (directeur)
Jean-Louis Bouquard (co-directeur)
Jacques Carlier
Stéphane Dauzère-Pérès (rapporteur)
Eric Pinson (rapporteur)
Francis Sourd
Résumé de la thèse :
Ce manuscrit traite de problèmes d'ordonnancement disjonctifs.
Dans le premier chapitre, nous avons réalisé un état de l'art sur le problème central disjonctif ainsi que sur les problèmes apparentés, plus précisément nous abordons les problèmes dans lesquels les opérations sont soumises à une date de début au plus tôt, date de fin souhaitée (date de fin impérative), temps de préparation et durée de latence.
Ces problèmes sont abordés de façon préemptive ou non et avec ou sans contrainte de précédence.
La fonction objectif consiste à minimiser la plus grande date de fin d'exécution d'une opération ou plus généralement une fonction de coût croissante.
En plus de leur intérêt intrinsèque, ces problèmes sont en outre utilisés comme relaxation de problèmes plus complexes.
A ce sujet, nous présentons une série d'expérimentations numériques, classiques pour une partie d'entre elles et originales pour les autres. Les problèmes à une machine sont utilisés pour obtenir des ajustements des fenêtres d'exécution des opérations pour le problème du jobshop.
Le deuxième chapitre traite de problèmes d'ordonnancement disjonctifs à une machine et de type jobshop tenant compte de contraintes de disponibilité de ressources.
Traditionnellement dans la littérature, on trouve deux types de problèmes : les problèmes dits sécables où les opérations peuvent être interrompues pendant leur exécution par une interruption sur la machine, et les problèmes dits non sécables dans lesquels les opérations ne peuvent pas être interrompues.
L'information indiquant le type de problème traité (sécable/non sécable) est rattachée à l'opération.
On peut obtenir les mêmes problèmes en disant qu'une période d'indisponibilité peut être traversée par une opération ou non.
Le principe proposé dans ce chapitre est le suivant : les deux problématiques sont prises en compte simultanément, dans ce cas une opération peut être interrompue ou non et une période d'indisponibilité peut être traversée ou non.
En plus des deux problèmes classiques de la littérature, nous mettons en évidence ici trois nouvelles problématiques et, à la fois pour le problème à une machine avec date de début au plus tôt et durée de latence, et pour le problème du job-shop, nous proposons une méthode de résolution exacte de type procédure par séparation-évaluation pour les résoudre.
Les résultats expérimentaux montrent que ces problèmes sont plus difficiles à résoudre que les originaux du fait que l'on a tendance à générer plus facilement des instances difficiles.
Le troisième chapitre présente de nouvelles relaxations à une machine pour le problème du flow-shop qui est un cas particulier du problème du job-shop.
Traditionnellement, la borne inférieure utilisée pour le problème du flow-shop s'appuie sur un cas particulier à deux machines de ce problème.
Ce problème est principalement abordé dans sa version de permutation.
Dans cette partie, nous nous intéressons à sa version de non-permutation auquel cas les relaxations à une machine considérées dans l'état de l'art s'avèrent être des bornes inférieures parmi les plus performantes.
En outre, l'ensemble des bornes connues pour ce problème consiste en la relaxation des contraintes de capacité de certaines machines.
En plus de la relaxation classique à une machine, nous introduisons ici la notion de date de début au plus tôt associée à la position d'une opération et de date de fin au plus tard également associée à la position d'une opération.
Nous proposons donc une nouvelle borne inférieure élaborée autour de ce problème plus contraint que le précédent et de même complexité que les bornes classiques pour ce problème.
Ce principe étant assez général, nous l'avons étendu avec succès au problème du flow-shop à deux machines avec dates de début au plus tôt et au problème du flow-shop à deux machines avec périodes d'indisponibilité.
Dans le quatrième chapitre, nous abordons également un problème de flow-shop où nous considérons que les opérations sont soumises à une phase de préparation nécessitant l'utilisation d'une ressource supplémentaire en capacité limitée.
Dans un premier temps, après un état de l'art sur ce type de problème, nous montrons un ensemble de résultats de complexité de cas particuliers de cette problématique montrant que le problème à deux machines est difficile à résoudre.
Nous montrons également un ensemble de propriétés du problème lorsque les temps de préparation sont unitaires. Le problème à deux machines dans le cas général hérite de ces propriétés.
Dans un second temps, nous cherchons à résoudre le problème à deux machines de façon exacte et approchée.
Pour ce faire, nous proposons deux modèles de programmation mathématique, une procédure par séparation-évaluation, un ensemble d'algorithmes de liste et une méthode de recherche par faisceaux avec réparation des n\oe uds.
Les résultats expérimentaux montrent que ce problème s'avère très difficile à résoudre malgré sa simplicité apparente.
Nous arrivons tout de même à proposer une méthode ne s'écartant jamais de plus de 5\% de la solution optimale.
Dans le dernier chapitre de ce mémoire, nous présentons les travaux que nous avons effectués pour la réalisation du produit Direct Planning de la société Volume Software, qui a financé cette thèse dans le cadre d'une convention CIFRE.
Les travaux abordés dans les chapitres précédents résultent principalement de l'analyse fonctionnelle de ce produit.
Le problème abordé est un problème de type job-shop soumis à de nombreuses contraintes provenant de l'industrie.
Une problématique originale abordée est le déplacement interactif de tâches dans un planning.
Curieusement, nous n'avons pas trouvé de trace de ce type d'algorithme dans la littérature, nous proposons par conséquent un ensemble d'algorithmes correspondants aux différents modes de fonctionnement du produit.
Direct Planning propose également des fonctionnalités d'ordonnancement automatique, nous décrivons donc les trois méthodes que nous avons mises en oeuvre pour y parvenir s'inspirant d'heuristiques bien connues et plus précisément de la ``shifting bottleneck procedure'' et d'une recherche taboue.
Les propriétés de ces deux méthodes répondent bien aux besoins du produit qui cherche à la fois à proposer des solutions de qualité avec des temps de calcul instantanés, et des solutions de haute qualité avec des temps de calcul plus importants.
Cifre Volume Software (université de Tours)
Soutenance le 30 novembre 2004
Etudes de problèmes d'ordonnancement disjonctifs avec contraintes de disponibilité des ressources et de préparation.
Composition du jury :
Jean-Charles Billaut (directeur)
Jean-Louis Bouquard (co-directeur)
Jacques Carlier
Stéphane Dauzère-Pérès (rapporteur)
Eric Pinson (rapporteur)
Francis Sourd
Résumé de la thèse :
Ce manuscrit traite de problèmes d'ordonnancement disjonctifs.
Dans le premier chapitre, nous avons réalisé un état de l'art sur le problème central disjonctif ainsi que sur les problèmes apparentés, plus précisément nous abordons les problèmes dans lesquels les opérations sont soumises à une date de début au plus tôt, date de fin souhaitée (date de fin impérative), temps de préparation et durée de latence.
Ces problèmes sont abordés de façon préemptive ou non et avec ou sans contrainte de précédence.
La fonction objectif consiste à minimiser la plus grande date de fin d'exécution d'une opération ou plus généralement une fonction de coût croissante.
En plus de leur intérêt intrinsèque, ces problèmes sont en outre utilisés comme relaxation de problèmes plus complexes.
A ce sujet, nous présentons une série d'expérimentations numériques, classiques pour une partie d'entre elles et originales pour les autres. Les problèmes à une machine sont utilisés pour obtenir des ajustements des fenêtres d'exécution des opérations pour le problème du jobshop.
Le deuxième chapitre traite de problèmes d'ordonnancement disjonctifs à une machine et de type jobshop tenant compte de contraintes de disponibilité de ressources.
Traditionnellement dans la littérature, on trouve deux types de problèmes : les problèmes dits sécables où les opérations peuvent être interrompues pendant leur exécution par une interruption sur la machine, et les problèmes dits non sécables dans lesquels les opérations ne peuvent pas être interrompues.
L'information indiquant le type de problème traité (sécable/non sécable) est rattachée à l'opération.
On peut obtenir les mêmes problèmes en disant qu'une période d'indisponibilité peut être traversée par une opération ou non.
Le principe proposé dans ce chapitre est le suivant : les deux problématiques sont prises en compte simultanément, dans ce cas une opération peut être interrompue ou non et une période d'indisponibilité peut être traversée ou non.
En plus des deux problèmes classiques de la littérature, nous mettons en évidence ici trois nouvelles problématiques et, à la fois pour le problème à une machine avec date de début au plus tôt et durée de latence, et pour le problème du job-shop, nous proposons une méthode de résolution exacte de type procédure par séparation-évaluation pour les résoudre.
Les résultats expérimentaux montrent que ces problèmes sont plus difficiles à résoudre que les originaux du fait que l'on a tendance à générer plus facilement des instances difficiles.
Le troisième chapitre présente de nouvelles relaxations à une machine pour le problème du flow-shop qui est un cas particulier du problème du job-shop.
Traditionnellement, la borne inférieure utilisée pour le problème du flow-shop s'appuie sur un cas particulier à deux machines de ce problème.
Ce problème est principalement abordé dans sa version de permutation.
Dans cette partie, nous nous intéressons à sa version de non-permutation auquel cas les relaxations à une machine considérées dans l'état de l'art s'avèrent être des bornes inférieures parmi les plus performantes.
En outre, l'ensemble des bornes connues pour ce problème consiste en la relaxation des contraintes de capacité de certaines machines.
En plus de la relaxation classique à une machine, nous introduisons ici la notion de date de début au plus tôt associée à la position d'une opération et de date de fin au plus tard également associée à la position d'une opération.
Nous proposons donc une nouvelle borne inférieure élaborée autour de ce problème plus contraint que le précédent et de même complexité que les bornes classiques pour ce problème.
Ce principe étant assez général, nous l'avons étendu avec succès au problème du flow-shop à deux machines avec dates de début au plus tôt et au problème du flow-shop à deux machines avec périodes d'indisponibilité.
Dans le quatrième chapitre, nous abordons également un problème de flow-shop où nous considérons que les opérations sont soumises à une phase de préparation nécessitant l'utilisation d'une ressource supplémentaire en capacité limitée.
Dans un premier temps, après un état de l'art sur ce type de problème, nous montrons un ensemble de résultats de complexité de cas particuliers de cette problématique montrant que le problème à deux machines est difficile à résoudre.
Nous montrons également un ensemble de propriétés du problème lorsque les temps de préparation sont unitaires. Le problème à deux machines dans le cas général hérite de ces propriétés.
Dans un second temps, nous cherchons à résoudre le problème à deux machines de façon exacte et approchée.
Pour ce faire, nous proposons deux modèles de programmation mathématique, une procédure par séparation-évaluation, un ensemble d'algorithmes de liste et une méthode de recherche par faisceaux avec réparation des n\oe uds.
Les résultats expérimentaux montrent que ce problème s'avère très difficile à résoudre malgré sa simplicité apparente.
Nous arrivons tout de même à proposer une méthode ne s'écartant jamais de plus de 5\% de la solution optimale.
Dans le dernier chapitre de ce mémoire, nous présentons les travaux que nous avons effectués pour la réalisation du produit Direct Planning de la société Volume Software, qui a financé cette thèse dans le cadre d'une convention CIFRE.
Les travaux abordés dans les chapitres précédents résultent principalement de l'analyse fonctionnelle de ce produit.
Le problème abordé est un problème de type job-shop soumis à de nombreuses contraintes provenant de l'industrie.
Une problématique originale abordée est le déplacement interactif de tâches dans un planning.
Curieusement, nous n'avons pas trouvé de trace de ce type d'algorithme dans la littérature, nous proposons par conséquent un ensemble d'algorithmes correspondants aux différents modes de fonctionnement du produit.
Direct Planning propose également des fonctionnalités d'ordonnancement automatique, nous décrivons donc les trois méthodes que nous avons mises en oeuvre pour y parvenir s'inspirant d'heuristiques bien connues et plus précisément de la ``shifting bottleneck procedure'' et d'une recherche taboue.
Les propriétés de ces deux méthodes répondent bien aux besoins du produit qui cherche à la fois à proposer des solutions de qualité avec des temps de calcul instantanés, et des solutions de haute qualité avec des temps de calcul plus importants.