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.
author:
- Kilian Grage
- Klaus Jansen
- Kim Manuel Klein
bibliography:
- 'References.bib'
title: 'An EPTAS for machine scheduling with bag-constraints.'
---

Introduction {#S:Introduction}
============

The machine scheduling problem is a classical optimization problem known in computer science. It stems from the simple idea of having multiple jobs that need to be scheduled on a set of machines. Formally we define this problem, also known as *makespan minimization*, as follows: Given a set of jobs $J$ such that each job $j \in J$ has a height or processing time denoted with $p_j$ and $m$ machines. The task is to find a schedule that assigns all jobs to machines and minimizes the makespan, which is the biggest load on any machine. This problem is known to be strongly NP-hard and therefore approximation algorithms are being studied for makespan minimization and different variations of this problem.

Especially polynomial-time approximation schemes (in 