**Friday, 10:30 - 10:55 h, Room: H 3004**

**Lin Chen**

Approximation algorithms for scheduling parallel machines with capacity constraints

**Coauthors: Klaus Jansen, Wenchang Luo, Guochuan Zhang**

**Abstract:**

In this paper, we consider the classical scheduling problem on

parallel machines with capacity constraints. We are given *m*

identical machines, where each machine *k* can process up to *c*_{k}

jobs. The goal is to assign the *n ≤ ∑*_{k=1}^{m}c_{k} independent

jobs on the machines subject to the capacity constraints such that

the makespan is minimized. This problem is a generalization of

*c*-partition, which is strongly NP-hard for *c ≥ 3* and the best

known approximation algorithm of which has a performance ratio of

4/3 due to Babel et al..

We deal with the general problem and improve the previous results by

establishing an efficient polynomial time approximation scheme

(EPTAS) whose running time is at most *2*^{O(1/ε2log3(1/ε))}+poly(1/ε,*log* n)+O(n*log* n). We develop a best-fit schedule for small

jobs, and then handle the assignment of big jobs through a mixed

integer programming (MILP). Such an MILP consists of a huge number

of integer variables which is not even a constant, however, we would

provide a greedy rounding technique to modify it iteratively so that the number of its integer and fractional variables is sharply reduced.

Talk 1 of the invited session Fri.1.H 3004

**"Approximation algorithms for hard problems"** [...]

Cluster 2

**"Combinatorial optimization"** [...]