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 provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.