Scheduling jobs on identical machines with agreement graph

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 algorithms with empirical results for the problem in the general case.