Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flow- shop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches. Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d'autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées.

Les travaux présentés dans cette thèse abordent la minimisation de coûts de production dans uneindustrie de produits douches et capillaires. Dans cette industrie, le processus de production inclus deuxétapes successives : la fabrication des lots de produit cosmétique et le stockage intermédiaire de ces derniers.Les coûts de production sont essentiellement liés aux opérations de lavage des ressources de fabrication etde stockage intermédiaire. Ces opérations de lavage doivent être effectuées lors de la succession des lots vuleur différentes caractéristiques physiques (couleur, viscosité,...) et chimiques (contenus chimiques,...).Ce problème est décomposé en deux sous-problèmes. Le premier consiste en l'optimisation du stockageintermédiaire. Le site dispose de plusieurs cuves de stockage, de différentes capacités, disposées en parallèle.Le rôle de ces cuves de stockage est de contenir temporairement les lots. Résoudre ce problème équivautà calculer les affectations des lots sur les cuves ainsi que leur date de début de transfert. L'objectif est deminimiser le nombre d'opérations de lavages des cuves de stockage.Le second sous-problème consiste à optimiser la fabrication des lots. Le site comprend plusieurs sallesde fabrication disposées en parallèle. Chaque salle de fabrication est constituée par plusieurs machinesorganisées en Flowshop Hybride. Pour résoudre ce problème, il faut calculer une affectation des lots sur lessalles de fabrication et les ordonnancer sur les machines de celles-ci. L'objectif est de minimiser le nombred'opérations de lavage induites par la succession des lots sur les machines.Nous proposons de résoudre le sous-problème d'optimisation du stockage intermédiaire en premier lieu,pour ensuite résoudre le sous-problème d'optimisation de la fabrication. Nous proposons et expérimentonsplusieurs méthodes heuristiques (gloutons, colonies de fourmis, méthodes arborescentes tronquées, méthodes dédiées) pour la résolution de chaque sous-problème. Les meilleures méthodes de résolution sontdestinées à être intégrées dans un logiciel de planification de la production quotidienne. / The work presented in this thesis addresses the minimization of production costs in an industry ofshowers and hair products. In this industry, the production process consists in two successive steps : themaking of cosmetic products and the intermediate storage of these latter. Production costs are mainlyrelated to cleaning operations of the making and the storage resources. These cleaning operations must beperformed in the sequence of two different batches of cosmetic product because of their different physical(color, viscosity, ...) and chemical (chemical contents,..) characteristics.This problem is decomposed into two sub-problems. The first one is the optimization of intermediatestorage. The shop is made up of parallel storage tanks of various capacities. These storage tanks haveto temporarily store the batches. Solving this problem is equivalent to calculating the assignment of thebatches on the storage tanks and their starting date of transfer. The objective is to minimize the numberof cleaning operations of the storage tanks.The second sub-problem is the optimization of the making process of the batches. The shop gathersseveral making units arranged in parallel. Each making unit consists in multiple mixing machines organizedin hybrid flowshop. To solve this problem, we have to calculate an assignment of the batches on the makingunits and their schedule on the mixing machines. The objective is to minimize the number of cleaningoperations.We propose to solve the sub-problem of optimization of the intermediate storage first, and then solvethe sub-problem of the optimization of the making process. We propose and experiment several heuristics(greedy, ant colonies, truncated tree methods, dedicated methods) for solving each sub-problem. The bestsolution methods are designed to be integrated into a software production planning.

Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flowshop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches.Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d’autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées / This thesis deals with 2-stages hybrid flowshop scheduling problems with batching machines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1\% on 200 task instances. For small instances, we presented 2 exact methods, Branch \& Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates