File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: On-line scheduling with tight deadlines
  • 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
2013 Impact Factor: 0.516
2013 SCImago Journal Rankings: 0.932
 
DOIhttp://dx.doi.org/10.1016/S0304-3975(02)00407-3
 
ISI Accession Number IDWOS:000181124700016
 
ReferencesReferences in Scopus
 
DC FieldValue
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
2013 Impact Factor: 0.516
2013 SCImago Journal Rankings: 0.932
 
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
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Koo, CY</contributor.author>
<contributor.author>Lam, TW</contributor.author>
<contributor.author>Ngan, TW</contributor.author>
<contributor.author>Sadakane, K</contributor.author>
<contributor.author>To, KK</contributor.author>
<date.accessioned>2010-09-06T09:51:02Z</date.accessioned>
<date.available>2010-09-06T09:51:02Z</date.available>
<date.issued>2003</date.issued>
<identifier.citation>Theoretical Computer Science, 2003, v. 295 n. 1-3, p. 251-261</identifier.citation>
<identifier.issn>0304-3975</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/88992</identifier.uri>
<description.abstract>This 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. &#169; 2002 Elsevier Science B.V. All rights reserved.</description.abstract>
<language>eng</language>
<publisher>Elsevier BV. The Journal&apos;s web site is located at http://www.elsevier.com/locate/tcs</publisher>
<relation.ispartof>Theoretical Computer Science</relation.ispartof>
<rights>Theoretical Computer Science. Copyright &#169; Elsevier BV.</rights>
<subject>Competitive analysis</subject>
<subject>Deadline scheduling</subject>
<subject>On-line algorithms</subject>
<title>On-line scheduling with tight deadlines</title>
<type>Conference_Paper</type>
<identifier.openurl>http://library.hku.hk:4550/resserv?sid=HKU:IR&amp;issn=0304-3975&amp;volume=295&amp;spage=251&amp;epage=261&amp;date=2003&amp;atitle=On-line+scheduling+with+tight+deadlines</identifier.openurl>
<description.nature>link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1016/S0304-3975(02)00407-3</identifier.doi>
<identifier.scopus>eid_2-s2.0-0037463530</identifier.scopus>
<identifier.hkuros>80442</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-0037463530&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>295</identifier.volume>
<identifier.issue>1-3</identifier.issue>
<identifier.spage>251</identifier.spage>
<identifier.epage>261</identifier.epage>
<identifier.isi>WOS:000181124700016</identifier.isi>
<publisher.place>Netherlands</publisher.place>
</item>
Author Affiliations
  1. The University of Hong Kong
  2. Tohoku University
  3. University of Maryland