Ordonnancement avec dates de livraison et gains cumulatifs
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Le problème étudié dans cette thèse est issu d'une problématique réelle, concernant l'optimisation du processus de numérisation des ouvrages de la Bibliothèque Nationale de France (BNF). La modélisation de ce problème met en évidence un critère d'optimisation nouveau en ordonnancement, tenant compte de gains cumulatifs liés à des dates de livraison communes à toutes les tâches. Dans le but d'identifier les structures des solutions optimales liées à ce nouveau critère et à des dates de disponibilité des tâches, nous nous sommes surtout concentrés sur un problème d'ordonnancement à une machine. Nous avons identifié les classes de complexité de ce problème, et proposé une méthode de résolution exacte de type Branch and Bound pour le problème général, s'appuyant sur des bornes et des règles de dominance dédiées. Nous avons également considéré le problème à deux dates de livraison (NP-difficile au sens faible), pour lequel nous avons proposé un algorithme pseudopolynomial de programmation dynamique et unalgorithme d'approximation polynomial avec une performance de garantie absolue égale à 1. Enfin, dans le but de nous rapprocher de la problématique industrielle, nous nous sommes intéressés à un problème de flowshop de permutation, avec le même critère d'optimisation. Pour ce problème, nous avons proposé plusieurs heuristiques : des algorithmes constructifs, des algorithmes de recherche locale, et une métaheuristique de type GRASP. Tous les algorithmes ont été implémentés, en particulier le Branch and Bound pour le problème à une machine et la recherche locale pour le flowshop permettent d'obtenir de bonnes solutions en tempsraisonnable.
Abstract FR:
Starting from a real world digitization workflow issue, we identified a scheduling problem with a new criterion involving common delivery dates for the jobs. In order to focus on this new criterion and on the jobs' release dates, we mainly worked on a single machine problem. We delimited the complexity classes of the problem, and provided a Branch and Bound algorithm for the general problem, based on dedicated bounds and dominance rules. We also considered the weakly NP-hard problem with two delivery dates, for which we designed a pseudopolynomial dynamic programming algorithm and an approximation algorithm with an absolute performance guarantee of 1. Finally, in order to consider a problem more closely related to the industrial issue, we studied a permutation flowshop problem with the same criterion. For this problem, we proposed several heuristic methods: constructive algorithms, local search, and a GRASP algorithm. All the algorithms were implemented. In particular the Branch and Bound method for the single machine problem and the local search algorithms for the flowshop provide good solutions in a reasonable time.