File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On-line scheduling with tight deadlines

TitleOn-line scheduling with tight deadlines
Authors
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
Citation
Theoretical Computer Science, 2003, v. 295 n. 1-3, p. 251-261 How to Cite?
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.
Persistent Identifierhttp://hdl.handle.net/10722/88992
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorKoo, CYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorNgan, TWen_HK
dc.contributor.authorSadakane, Ken_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2010-09-06T09:51:02Z-
dc.date.available2010-09-06T09:51:02Z-
dc.date.issued2003en_HK
dc.identifier.citationTheoretical Computer Science, 2003, v. 295 n. 1-3, p. 251-261en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88992-
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.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectCompetitive analysisen_HK
dc.subjectDeadline schedulingen_HK
dc.subjectOn-line algorithmsen_HK
dc.titleOn-line scheduling with tight deadlinesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=295&spage=251&epage=261&date=2003&atitle=On-line+scheduling+with+tight+deadlinesen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/S0304-3975(02)00407-3en_HK
dc.identifier.scopuseid_2-s2.0-0037463530en_HK
dc.identifier.hkuros80442en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0037463530&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume295en_HK
dc.identifier.issue1-3en_HK
dc.identifier.spage251en_HK
dc.identifier.epage261en_HK
dc.identifier.isiWOS:000181124700016-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridKoo, CY=7006652508en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridNgan, TW=6602433224en_HK
dc.identifier.scopusauthoridSadakane, K=7005716583en_HK
dc.identifier.scopusauthoridTo, KK=36785812300en_HK
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats