  Machine scheduling is a fundamental optimization problem in computer science.
The task of scheduling a set of jobs on a given number of machines and
minimizing the makespan is well studied and among other results, we know that
EPTAS's for machine scheduling on identical machines exist. Das and Wiese
initiated the research on a generalization of makespan minimization, that
includes so called bag-constraints. In this variation of machine scheduling the
given set of jobs is partitioned into subsets, so called bags. Given this
partition a schedule is only considered feasible when on any machine there is
at most one job from each bag.
  Das and Wiese showed that this variant of machine scheduling admits a PTAS.
We will improve on this result by giving the first EPTAS for the machine
scheduling problem with bag-constraints. We achieve this result by using new
insights on this problem and restrictions given by the bag-constraints. We show
that, to gain an approximate solution, we can relax the bag-constraints and
ignore some of the restrictions. Our EPTAS uses a new instance transformation
that will allow us to schedule large and small jobs independently of each other
for a majority of bags. We also show that it is sufficient to respect the
bag-constraint only among a constant number of bags, when scheduling large
jobs. With these observations our algorithm will allow for some conflicts when
computing a schedule and we show how to repair the schedule in polynomial-time
by swapping certain jobs around.
