Conference Paper: On-line scheduling with tight deadlines

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleOn-line scheduling with tight deadlines
AuthorsKoo, CY3
Lam, TW1
Ngan, TW1
Sadakane, K2
To, KK1
KeywordsCompetitive analysis
Deadline scheduling
On-line algorithms
Issue Date2003
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
CitationTheoretical Computer Science, 2003, v. 295 n. 1-3, p. 251-261 [How to Cite?]
DOI: http://dx.doi.org/10.1016/S0304-3975(02)00407-3
AbstractThis paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor O(1) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(logk) times faster (Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only O(1) times faster. © 2002 Elsevier Science B.V. All rights reserved.
ISSN0304-3975
2011 Impact Factor: 0.665
2011 SCImago Journal Rankings: 0.055
DOIhttp://dx.doi.org/10.1016/S0304-3975(02)00407-3
ISI Accession Number IDWOS:000181124700016
ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorKoo, CY
dc.contributor.authorLam, TW
dc.contributor.authorNgan, TW
dc.contributor.authorSadakane, K
dc.contributor.authorTo, KK
dc.date.accessioned2010-09-06T09:51:02Z
dc.date.available2010-09-06T09:51:02Z
dc.date.issued2003
dc.description.abstractThis paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a uni-processor system. It has been known for long that in such a setting, no on-line algorithm is 1-competitive (i.e., optimal) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be better than k-competitive, where k is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to a constant if the on-line scheduler is equipped with a processor O(1) times faster (J. ACM 47(4) (2000) 617), and further to one when using a processor O(logk) times faster (Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms, 2001, p. 755). This paper presents a new on-line algorithm for scheduling jobs with tight deadlines and shows that it is 1-competitive when using a processor that is only O(1) times faster. © 2002 Elsevier Science B.V. All rights reserved.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationTheoretical Computer Science, 2003, v. 295 n. 1-3, p. 251-261 [How to Cite?]
DOI: http://dx.doi.org/10.1016/S0304-3975(02)00407-3
dc.identifier.doihttp://dx.doi.org/10.1016/S0304-3975(02)00407-3
dc.identifier.epage261
dc.identifier.hkuros80442
dc.identifier.isiWOS:000181124700016
dc.identifier.issn0304-3975
2011 Impact Factor: 0.665
2011 SCImago Journal Rankings: 0.055
dc.identifier.issue1-3
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-0037463530
dc.identifier.spage251
dc.identifier.urihttp://hdl.handle.net/10722/88992
dc.identifier.volume295
dc.languageeng
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
dc.publisher.placeNetherlands
dc.relation.ispartofTheoretical Computer Science
dc.relation.referencesReferences in Scopus
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.
dc.subjectCompetitive analysis
dc.subjectDeadline scheduling
dc.subjectOn-line algorithms
dc.titleOn-line scheduling with tight deadlines
dc.typeConference_Paper
Author Affiliations
  1. The University of Hong Kong
  2. Tohoku University
  3. University of Maryland