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


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 ck
jobs. The goal is to assign the n ≤ ∑k=1mck 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 2O(1/ε2log3
+poly(1/ε,log n)+O(nlog 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" [...]


  Payday Loans California. What makes Viagra Strips better than other forms of this medicine is its easiness of usage.