Paper Info
Title
Scheduling jobs on identical and uniform processors revisited
Abstract
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||C max . 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(n log n) 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(Ãδ)) + poly(n), where Ãδ is the constraint matrix for a sub-problem considered in this case. In both cases we show that C(Aδ), C(Ãδ) ≤ 2O(1/ε2 log2(1/ε)). Consequently, our algorithm has running-time at most 2O(1/ε3 log3(1/ε)) + O(n log n) for identical machines and 2O(1/ε2 log3(1/ε)) + poly(n) for uniform machines, the same as in [11]. 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(Ãδ). If C(Ãδ), C(Aδ) ≤ poly(1/ε), the running-time of the algorithm would be 2O(1/ε log2(1/ε)) + poly(n) and thus improve the result in [11].
Year
DOI
Venue
2011
10.1007/978-3-642-29116-6_10
WAOA
Keywords
Field
DocType
ilp solver,distance max,scheduling job,closest ilp solution y,c max,uniform machine,uniform processor,constraint matrix,n log n,ilp solution,identical machine
Discrete mathematics,Combinatorics,Uniform norm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Upper and lower bounds,Matrix (mathematics),Time complexity,Bin packing problem,Mathematics,Bounded function
Conference
Citations 
PageRank 
References 
9
0.61
13
Authors
2
Name
Order
Citations
PageRank
Klaus Jansen1343.21
Christina Robenek2232.58