The power of reordering for online minimum makespan scheduling

Article English OPEN
Englert, Matthias; Özmen, Deniz; Westermann, Matthias;
  • Publisher: Society for Industrial and Applied Mathematics
  • Related identifiers: doi: 10.1137/130919738
  • Subject: QA76

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 a... View more
  • References (11)
    11 references, page 1 of 2

    [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)).

  • Metrics
Share - Bookmark