Full textReport2011UrhG

Scheduling on Uniform Processors Revisited

We study the problem of scheduling jobs on uniform processors with the objective to minimize the makespan. In scheduling theory this problem is known as Q||Cmax. We present an EPTAS for scheduling on uniform machines avoiding the use of an MILP or ILP solver. Instead of solving (M)ILPs we solve the LP-relaxation and use structural information about the ``closest'' ILP solution. For a given LP-solution x we consider the distance to the closest ILP solution y in the infinity norm, i.e. ∥x−y∥∞. We call this distance max-gap(Aδ), where Aδ is the constraint matrix of the considered (I)LP. For identical machines and δ=Θ(ϵ) the matrix Aδ has integral entries in {0,…,(1+δ)/δ} and O(1/δlog(1/δ)) rows representing job sizes and 2O(1/δlog2(1/δ)) columns representing configurations of jobs, so that the column sums are bounded by (1+δ)/δ. The running-time of our algorithm is 2O(1/ϵlog(1/ϵ)log(C(Aδ))+O(nlogn) where C(Aδ) denotes an upper bound for max-gap(Aδ). Furthermore, we can generalize the algorithm for uniform machines and obtain a running-time of 2O(1/ϵlog(1/ϵ)log(C(A˜δ))+poly(n), where A˜δ is the constraint matrix for a sub-problem considered in this case. In both cases we show that C(Aδ),C(A˜δ)≤2O(1/ϵlog2(1/ϵ)). Consequently, our algorithm has running-time at most 2O(1/ϵ2log3(1/ϵ))+O(nlogn) for identical machines and 2O(1/ϵ2log3(1/ϵ))+poly(n) for uniform machines, the same as the current best algorithm. But, to our best knowledge, no instance is known to take on the value 2O(1/ϵlog2(1/ϵ)) for max-gap(Aδ) or max-gap(A˜δ). If C(A˜δ),C(Aδ)≤poly(1/ϵ), the running-time of the algorithm would be 2O(1/ϵlog2(1/ϵ))+poly(n) and thus improve the running-time of the current best algorithm.

Logo BII



Citation style:
Could not load citation form.


Use and reproduction:No Creative Commons License - The german copyright act (UrhG) appliesPlease note that individual components of the publication may be subject to other licensing or copyright conditions.