Scheduling jobs on identical machines with agreement constraints.

Abstract

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.