some extensions to respect bag-constraints. Given a solution of the transformed instance we can easily construct a solution of the original one in polynomial-time, yielding us an EPTAS.

There exists an EPTAS for the machine scheduling with bag-constraints on identical machines.

In the following we will first introduce some preprocessing steps, classification of bag groups and the aforementioned instance modification as well as its correctness (section 2). Knowing that we can work with a modified instance of easier structure we then formalize the MILP and show how we can repair a given MILP solution in case the solution does not allow for a feasible distribution of jobs (section 3). We finalize our presentation of the EPTAS by showing how small jobs can be scheduled such that the height of the schedule does not increase arbitrarily in the end (section 5). Due to space limitations we moved proofs into the appendix.

Preliminaries {#S:Prel}
=============

In the following we will assume that we are given an instance $I$ of the machine scheduling with bag-constraints problem with a set of jobs $J$ that is separated in a partition of bags $B_1 ,..., B_b$ and a number of machines $m$. Furthermore an approximation ratio 