publication . Conference object . Article . 2014

The Power of Reordering for Online Minimum Makespan Scheduling

Matthias Englert; Deniz Özmen; Matthias Westermann;
Open Access
  • Published: 27 May 2014
  • Publisher: IEEE
  • Country: United Kingdom
In the classic minimum makespan scheduling problem, we are given an input sequence of jobs with processing times. A scheduling algorithm has to assign the jobs to m parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we do not require that each arriving job has to be assigned immediately to one of the machines. A reordering buffer with limited storage capacity can be used to reorder the input sequence in a restricted fashion so as to schedule the jobs with a smaller makespan. This is a natural extension of lookah...
free text keywords: General Computer Science, General Mathematics, QA76, Parallel computing, Minimisation (psychology), Competitive analysis, Upper and lower bounds, Online algorithm, Algorithm design, Schedule, Computer science, Scheduling (computing), Job shop scheduling, Johnson's rule, Preemption
Related Organizations

[AAF+97] James Aspnes, Yossi Azar, Amos Fiat, Serge A. Plotkin, and Orli Waarts. Online routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM, 44(3):486{504, 1997.

Susanne Albers and Matthias Hellwig. On the value of job migration in online makespan minimization. In Proceedings of the 20th European Symposium on Algorithms (ESA), pages 84{95, 2012.

Susanne Albers. A competitive analysis of the list update problem with lookahead. Theoretical Computer Science, 197(1{2):95{109, 1998.

Susanne Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2):459{473, 1999.

Susanne Albers. New results on web caching with request reordering. In Proceedings of the 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 84{92, 2004.

[ATUW01] Houman Alborzi, Eric Torng, Patchrawat Uthaisombut, and Stephen Wagner. The k-client problem. Journal of Algorithms, 41(2):115{173, 2001.

Piotr Berman, Moses Charikar, and Marek Karpinski. On-line load balancing for related machines. Journal of Algorithms, 35(1):108{121, 2000.

Shai Ben-David and Allan Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11(1):73{91, 1994.

[BFKV95] Yair Bartal, Amos Fiat, Howard J. Karlo , and Rakesh Vohra. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences, 51(3):359{366, 1995.

1 x1 )e 1 x1 )e Lemma 11. rm is non-decreasing in m and limm!1 rm = W 1( 1=e2)=(1 + W 1( 1=e2)).

1P)rPoofm. D1 ue to the de nition, rm is the smallest positive solution to dm(1 x1 )e mx + (x i=dm(1 x1 )e 1i = 1. Fact 9 and Fact 10 combined imply that rm is non-decreasing in m. As m tends to in nity, dm(1 x1 )e mx + (x 1) Pm 1 i=dm(1 x1 )e 1i converges pointwise to 1) ln 1

Any information missing or wrong?Report an Issue