TY - JOUR

T1 - Average stretch without migration

AU - Becchetti, Luca

AU - Leonardi, Stefano

AU - Muthukrishnan, S.

N1 - Funding Information:
$A preliminary version of this paper appeared in the Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’00), pp. 548–557, 2000. *Corresponding author. E-mail addresses: becchett@dis.uniroma1.it (L. Becchetti), leon@dis.uniroma1.it (S. Leonardi), muthu@cs. rutgers.edu (S. Muthukrishnan). 1Partially supported by the IST Programme of the EU under Contract IST-1999-14186 (ALCOM-FT) and IST-2000-14084 (APPOL), and by the MURST Projects ‘‘Algorithms for Large Data Sets: Science and Engineering’’ and ‘‘Resource Allocation in Computer Networks’’.

PY - 2004/2

Y1 - 2004/2

N2 - 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 between the amount of time spent by the job in the system (the response time) and its processing time. For a sequence of jobs, we measure the performance of an algorithm by the average stretch achieved over all 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 Awerbuch et al. (Proceedings of the ACM Symposium on the Theory of Computing (STOC '99), 1999, pp. 198-205) that has (tight) logarithmic competitive ratio for minimizing the average response time. Thus, the algorithm in Awerbuch et al. (Proceedings of the ACM Symposium on the Theory of Computing (STOC '99), 1999. pp. 198-205) 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.

AB - 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 between the amount of time spent by the job in the system (the response time) and its processing time. For a sequence of jobs, we measure the performance of an algorithm by the average stretch achieved over all 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 Awerbuch et al. (Proceedings of the ACM Symposium on the Theory of Computing (STOC '99), 1999, pp. 198-205) that has (tight) logarithmic competitive ratio for minimizing the average response time. Thus, the algorithm in Awerbuch et al. (Proceedings of the ACM Symposium on the Theory of Computing (STOC '99), 1999. pp. 198-205) 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.

KW - Average stretch

KW - Migration

KW - Scheduling

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

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

U2 - 10.1016/j.jcss.2003.06.001

DO - 10.1016/j.jcss.2003.06.001

M3 - Article

AN - SCOPUS:0842278862

SN - 0022-0000

VL - 68

SP - 80

EP - 95

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 1

ER -