Problèmes d'ordonnancement de commandes client

Les entreprises sont soumises à un environnement concurrentiel accru les poussant à être de plus en plus performantes. La satisfaction des délais clients reste aujourd'hui un enjeu majeur qui définit en partie la compétitivité d'une entreprise. Dans ce contexte, l'activité d'ordonnancement jour un rôle crucial dans le respect des délais clients. Dans la plupart des travaux traitant des problèmes d'rdonnancement d'atelier, les critères de performance des ordonnancements sont associés aux tâches individuelles. Ce critère n'est paspertinent lorsqu'il s'agit d'ordonnancer des commandes clients composées de plusieurs tâches. En effet, une commande est à l heure lorsque toutes ses tâches le sont. Nous étudions la complexité de quelques problèmes d'ordonnancement de commande sur une machine. Nous nous sommes ensuite intéressés particulièrement à deux types de problèmes: la minimisation du nombre pondéré de commandes en retard sur une machine avec contrainte de disponibilité des tâches et la minimisation du retard pondéré des commandes dans un atelier du type job shop. Ces deux problèmes sont NP-difficiles. Pour résoudre ces deux problèmes, nous développons des méthodes approchées. Pour le premier, une méthode de relaxation lagrangienne est développée. Pour le second, nous proposons des heuristiques de liste utilisant des règles de priorité basées sur les commandes. Nous développons plusieurs méthodes de recherche locale. Une analyse expérimentale montre qu une recherche taboue probabiliste donne de bons résultats en un temps très faible. Un algorithme génétique hybride permet de trouver les meilleurs résultats pour un certain nombre d instances en un temps raisonnable.The satisfaction of the customer s delays remains today a major issue for the companies. The production scheduling activity figures unquestionably in good place among the parameters that influence the performance of a workshop in terms of respects of the delays. We deal with the scheduling problem in which customers place orders corresponding to a collection of jobs. The jobs in an order can be executed independently and the order is completed once the last component job is completed. The characteristic of this work is to focus on the optimization of criteria related to the orders, rather than on individual jobs. We give complexity results for some single machine order scheduling problems. Then we focus on resolving two NP-Hard problems. We concentrate first on the single machine problem with release dates; we propose a Lagrangian relaxation heuristic to minimize the weighted number of late orders. The second problem considered is the minimisation of the weighted order tardiness in a job shop. We propose several dispatching rules based on the orders characteristics, which succeed better than the classical dispatching based on the jobs characteristics. Several local search methods are developed. Computational results on a wide range of instances show that a taboo probabilistic algorithm performs at giving high quality solutions quickly. For some problems, a hybrid genetic algorithm (coupling a genetic algorithm and an iterated local search) succeeds in obtaining the best solutions in a reasonable time.NANTES-BU Sciences (441092104) / SudocNANTES-BU Technologie (441092105) / SudocNANTES-ENS Mines (441092314) / SudocSudocFranceF