Polynomial Approximation Algorithms for Parallel Machine Problems in a Multi-objective or Constrained Context

Résumé

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.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 2

Téléchargements : 0