distributed systems, it is not unusual that one wants to enforce different tasks to run on different machines/processors. This can be done to schedule tasks more efficiently on parallel machines but also for system stability and security purposes. To prevent failure and crashes, jobs need to be run separately, so in case that one machine fails, other machines can still continue working.

To model this, one can extend the definition of machine scheduling by partitioning the set of jobs in subsets $B_1,B_2,...,B_b$. We expect that each job $j\in J$ is contained in exactly one of these subsets, that we call *bag*. For the solution we expect again a schedule with minimum makespan, but additionally we only allow that at most one job from each bag is scheduled on a single machine. Further we will call a violation of the bag-constraints, given by two jobs of the same bag on one machine, a *conflict* and say the respective jobs are conflicting each other. In this paper we will consider only identical machines and our goal will be to minimize the given makespan. The resulting problem is known as *machine scheduling with bag-constraints*.

This problem was recently studied by Das and Wiese 