Scheduling to minimize average stretch without migration

Luca Becchetti, Stefano Leonardi

Research output: Contribution to conferencePaper

24 Scopus citations


We study the problem of scheduling parallel machines online, allowing preemptions while disallowing migration of jobs that have been scheduled on one machine to another. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, defined as the ratio of the amount of time the job spends in the system (also known as the response time) to its processing time. For a sequence of jobs, we measure the performance of an algorithm by the average stretch achieved over all the jobs. The scheduling goal is to minimize the average stretch. This problem is of relevance in many applications, e.g., wireless data servers and distributed server systems in wired networks. We prove an O(1) competitive ratio for this problem. The algorithm for which we prove this result is the one proposed in [2] that has (tight) logarithmic competitive ratio for minimizing the average response time. Thus the algorithm in [2] simultaneously performs well for average response time as well as average stretch. We prove the O(1) competitive ratio against an adversary who not only knows the entire input ahead of time, but is also allowed to migrate jobs. Thus our result shows that migration is not necessary to be competitive for minimizing average stretch; in contrast, we prove that preemption is essential, even if randomization is allowed. We also establish a constant-factor lower bound on the competitive ratio of any online algorithm that minimizes average stretch without migration.

Original languageEnglish (US)
Number of pages10
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Scheduling to minimize average stretch without migration'. Together they form a unique fingerprint.

  • Cite this

    Becchetti, L., & Leonardi, S. (2000). Scheduling to minimize average stretch without migration. 548-557. Paper presented at 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .