is known for unrelated machines [@unrelated1].

We will only look at identical machines in this paper and we want to consider a variant of machine scheduling that involves conflicts. In this variation some jobs are in conflict with each other and therefore not allowed to be executed on the same machine. An easy and intuitive way to model conflicts is to use a graph, where each job is represented as a node and an edge between nodes indicates a conflict. The problem of minimizing the makespan under these restrictions given an arbitrary conflict-graph is NP-hard. A tight $2$-approximation is known for the case where the conflict graph is polynomial-time colorable [@conflict].

A special case of this problem is given when the conflict graph is a cluster graph, that consists of multiple components such that each component is a clique. In this case we can easily model the given conflicts as sets of jobs and each set contains all nodes of one clique. The problem of scheduling jobs under these type of conflicts is also known as machine scheduling with bag-constraints [@bagptas], whereas the mentioned sets are called bags.

Machine scheduling with bag-constraints
---------------------------------------

In software engineering, especially for parallel and 