Abstract:
The problem of Scheduling $n$ Independent Jobs on $m$ Unrelated Parallel Machines, when $m$ is fixed, is considered. The standard problem of minimizing the makespan of the schedule (SUM) and the bicriteria problem of scheduling with bounded makespan and cost (SUMC), are addressed, and randomized fully linear time approximation schemes are shown for both problems. The core of the algorithms is an interesting new randomized rounding procedure, the Filtered Randomized Rounding (FRR), that boosts the deviation bounds of the rounded linear packing constraints to any given constant ratio. Finally, the notion of {\it polybottleneck} combinatorial optimization problems is defined and used to build $O(n \log n \log\log n)$ time approximation schemes for two natural optimization versions of SUMC obtained by bounding the one objective and optimizing the other. All algorithms admit simple optimal work parallelization.