algorithms [@jeptas1; @jeptas2]. In the presence of bag-constraints the problem arises that not every efficient placement of large jobs allows for a schedule of bounded height, as seen in figure \[abb:diffic\]. The first idea that comes into mind is to incorporate the bag-constraints into the MILP. To do this however we would need a number of integer variables depending on the number of bags. As we can have as many bags as jobs we would need a running time exponential in the size of the instance $|I|$ to solve such an MILP.

[Comparing possible schedules depending on large job placement. In the left schedule the two large jobs were scheduled on different machines, allowing for a schedule of height OPT. Considering the placement of large jobs in the right schedule, we see even though large jobs are packed with height OPT, we are forced to place small jobs like depicted and increase the overall makespan.]{} \[abb:diffic\]

We overcome these problems by relaxing the bag-constraints to some extent. While computing a schedule we will temporarily allow for some conflicts of jobs from the same bag, but in a controlled way, such that we can repair our schedule in polynomial-time and with 