Veuillez utiliser cette adresse pour citer ce document : https://di.univ-blida.dz/jspui/handle/123456789/8069
Titre: Scheduling jobs on identical machines with agreement constraints.
Auteur(s): Sidoummou., Benyoucef..
Mots-clés: Scheduling with Agreements.
Identical Parallel Machines.
Makespan.
Heuristics.
Metaheuristics.
Lower Bounds.
Date de publication: 28-oct-2018
Editeur: Université Blida 1
Résumé: In this thesis, we consider the "Scheduling with Agreements” problem. The jobs are subjected to agreement constraints modeled by a graph called "Agreement Graph”. All the jobs are ready at time zero, the preemption is not allowed and the objective is to minimize the makespan. We consider different types of agreement graph: general graphs, bipartite graphs, trees and chains. This problem is NP-hard in the general agreement graph case. However, it can be solved in a reasonable time for a special classes of graphs. Indeed, we introduce an algorithm solving polynomially the problem in the case of chain-type agreement graph. This algorithm is built on the maximum weight stable set to determine a lower bound for the problem. A mathematical formulation is proposed in both general and bipartite graphs. To approach the optimality and obtain an upper bound for the problem, we introduce heuristics based on lists. And, to be closer to the optimal solution, we propose metaheuristics. All these methods are widely experimented using uniformly generated instances. Keywords: Scheduling with Agreements, Identical Parallel Machines, Makespan, Heuristics, Metaheuristics, Lower Bounds.
Description: ill.,Bibliogr.
URI/URL: http://di.univ-blida.dz:8080/jspui/handle/123456789/8069
Collection(s) :Mémoires de Master

Fichier(s) constituant ce document :
Fichier Description TailleFormat 
sidoummou benyoucef.pdf27,95 MBAdobe PDFVoir/Ouvrir


Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.