Algorithmes d'approximation polynomiale pour des problèmes d’ordonnancement sur machines parallèles dans un contexte multi-objectif ou contraint

This thesis addresses the scheduling problems on parallel machines, with and without nonavailability constraints, and the design of approximation methods dedicated to solving this problem in a multi-objective context (load balancing and minimization of the delivery times). These are critical logistical issues for the quality of service and the performance of such systems. These are NP-hard optimization problems. In this context, the carried work of this thesis leads to a contribution to solving and approximating the performance of these systems with parallel resources. Many optimization methods have been developed and tested in this context. These methods include different approaches such as heuristics of guaranteed performance, dynamic programming algorithms, polynomial time approximation scheme (PTAS), and fully polynomial time approximation scheme (FPTAS). In particular, we thoroughly analyzed the basic substructure with two parallel machines. We have studied the scenario, with a constraint of unavailability on a machine, associated with this substructure. We have shown that the problem has a constant polynomial approximation algorithm. Thus, we presented a dynamic programming algorithm and an FPTAS, which has a strongly polynomial running time. Experimental tests have been performed and used to compare the performances of the proposed algorithms on several sets of instances. The second important contribution of this thesis is related to the determination of the Pareto solutions for the same substructure (two parallel machines) but without non-availability constraint. Many methods have been proposed in this section: dynamic programming, PTAS, FPTAS in two versions, with detailed experimental comparisons. The third contribution of the thesis concerns the extension of the multi-objective study to the problem of scheduling jobs on m parallel machines. Different extensions and algorithms have been proposed: a dynamic programming, a PTAS and an FPTAS for fixed value of m. Experimental tests were conducted and allowed to evaluate and compare the performance of these methods.Cette thèse traite du problème d’ordonnancement sur machines parallèles, avec et sans indisponibilités, et de la conception de méthodes d’approximation dédiées à la résolution de ce problème dans un contexte multi-objectif (équilibrage des charges et minimisation de la date de livraison). Ce sont des problèmes cruciaux dans le domaine logistique pour améliorer la qualité de service et la performance de tels systèmes. Il s’agit des problèmes d’optimisation NP-difficiles. Dans cette optique, les travaux de cette thèse constituent une contribution à la résolution exacte et approchée de ces systèmes à ressources parallèles. Plusieurs méthodes d’optimisation ont été développées et testées dans ce cadre. De telles méthodes incorporent différentes approches de résolution ou d’optimisation, comme les heuristiques à garantie de performance, les algorithmes de programmation dynamique, les schémas d’approximation polynomiaux (PTAS) et entièrement polynomiaux (FPTAS)