Open shop scheduling problems with conflict graphs

This paper deals with open shops subject to the constraint that some conflicting jobs cannot be processed simultaneously on different machines. In the context of our study, these conflicts are given by an undirected graph, called the conflict graph. We seek a schedule that minimizes the maximum completion time (makespan). We first prove the NP-hardness of different versions of this problem. Then, we present polynomial-time solvable cases, for which we devise simple and efficient algorithms. On the other hand, we present heuristics and lower bounds for the general case. The heuristics are based on the construction of matchings in bipartite graphs as well as on a specific insertion technique combined with beam search. Finally, we test the efficiency of the heuristics and report our computational experiments that display satisfying results.