Scheduling jobs on identical machines with agreement graph

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 382-390

Mohamed, Bendraouche , Mourad, Boudhar

We consider the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph and the aim is to minimize the makespan. This problem is NP-hard. We study the complexity of the problem for two machines and arbitrary bipartite agreement graphs, in particular we prove the NP-hardness of the open problem proposed in the literature which is the case of two machines with processing times at most 3. We propose list…