and they developed a PTAS for machine scheduling with bag-constraints on identical machines. They also considered the case of unrelated machines and showed a lower bound for the approximation ratio and giving an 8-approximation for the case where all jobs of each bag can go on the same machines [@bagptas]. The known PTAS uses a dynamic program to schedule large jobs like in an optimal solution. Given this initial distribution they use different techniques, like flow-networks and greedy algorithms to build a schedule of bounded height. Since the problem is strongly NP-hard we cannot expect to find an FPTAS unless $P=NP$. In this paper we will close this gap between known PTAS and non-existing FPTAS and solve one of the main open problems of Das and Wiese by giving the first EPTAS for machine scheduling with bag-constraints.

The main difficulty for giving an EPTAS for this problem is, that the known strategies for EPTAS from other scheduling problems cannot be applied for this problem without further modifications. The common strategy for EPTAS’ for makespan minimization is to find an efficient placement of large jobs, usually with a (mixed) integer linear program (in short (M)ILP) and place small jobs with greedy 