TY - GEN

T1 - Online makespan minimization with parallel schedules

AU - Albers, Susanne

AU - Hellwig, Matthias

N1 - Funding Information:
Work supported by the German Research Foundation, grant AL 464/7-1.

PY - 2014

Y1 - 2014

N2 - Online makespan minimization is a classical problem in which a sequence of jobs σ = J1, ..., Jn has to be scheduled on m identical parallel machines so as to minimize the maximum completion time of any job. In this paper we investigate the problem in a model where extra power/resources are granted to an algorithm. More specifically, an online algorithm is allowed to build several schedules in parallel while processing σ. At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. As a main result we develop a (4/3 + ε)-competitive algorithm, for any 0 < ε ≤ 1, that uses a constant number of schedules. The constant is equal to 1/ε O(log(1/ε)). We also give a (1 + ε)-competitive algorithm, for any 0 < ε ≤ 1, that builds a polynomial number of (m/ε) O(log(1/ε)/ε) schedules. This value depends on m but is independent of the input σ. The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4/3 must construct Ω(m) schedules. On the technical level, our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of σ to within a factor of 1 + ε and (2) guess the job processing times and their frequencies in σ. In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant.

AB - Online makespan minimization is a classical problem in which a sequence of jobs σ = J1, ..., Jn has to be scheduled on m identical parallel machines so as to minimize the maximum completion time of any job. In this paper we investigate the problem in a model where extra power/resources are granted to an algorithm. More specifically, an online algorithm is allowed to build several schedules in parallel while processing σ. At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. As a main result we develop a (4/3 + ε)-competitive algorithm, for any 0 < ε ≤ 1, that uses a constant number of schedules. The constant is equal to 1/ε O(log(1/ε)). We also give a (1 + ε)-competitive algorithm, for any 0 < ε ≤ 1, that builds a polynomial number of (m/ε) O(log(1/ε)/ε) schedules. This value depends on m but is independent of the input σ. The performance guarantees are nearly best possible. We show that any algorithm that achieves a competitiveness smaller than 4/3 must construct Ω(m) schedules. On the technical level, our algorithms make use of novel guessing schemes that (1) predict the optimum makespan of σ to within a factor of 1 + ε and (2) guess the job processing times and their frequencies in σ. In (2) we have to sparsify the universe of all guesses so as to reduce the number of schedules to a constant.

UR - http://www.scopus.com/inward/record.url?scp=84904169090&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08404-6_2

DO - 10.1007/978-3-319-08404-6_2

M3 - Conference contribution

AN - SCOPUS:84904169090

SN - 9783319084039

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 25

BT - Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings

PB - Springer Verlag

T2 - 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014

Y2 - 2 July 2014 through 4 July 2014

ER -