File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Performance guarantee for online deadline scheduling in the presence of overload

TitlePerformance guarantee for online deadline scheduling in the presence of overload
Authors
Lam, TWTo, KK
KeywordsMathematics computers
Algorithms
Measurement
Performance
Theory
Verification
Issue Date2001
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 755-764 How to Cite?
AbstractEarliest deadline first (EDF) is a widely-used online algorithm for scheduling jobs with deadlines in real-time systems. Yet, existing results on the performance guarantee of EDF are limited to underloaded systems [6,12,14]. This paper initiates the study of EDF for overloaded systems, attaining similar performance guarantees as in the underloaded setting. Specifically, we show that EDF with a simple form of admission control is optimal for scheduling on both uniprocessor and multiprocessors when moderately faster processors are available (our analysis actually admits a tradeoff between speed and extra processors). This is the first result attaining optimality under overload. Another contribution of this paper is an improved analysis of the competitiveness for weighted deadline scheduling.
Persistent Identifierhttp://hdl.handle.net/10722/45631
ISSN
1071-9040
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorLam, TWen_HK
dc.contributor.authorTo, KKen_HK
dc.date.accessioned2007-10-30T06:30:41Z-
dc.date.available2007-10-30T06:30:41Z-
dc.date.issued2001en_HK
dc.identifier.citationThe 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, DC., 7-9 January 2001. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, p. 755-764en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45631-
dc.description.abstractEarliest deadline first (EDF) is a widely-used online algorithm for scheduling jobs with deadlines in real-time systems. Yet, existing results on the performance guarantee of EDF are limited to underloaded systems [6,12,14]. This paper initiates the study of EDF for overloaded systems, attaining similar performance guarantees as in the underloaded setting. Specifically, we show that EDF with a simple form of admission control is optimal for scheduling on both uniprocessor and multiprocessors when moderately faster processors are available (our analysis actually admits a tradeoff between speed and extra processors). This is the first result attaining optimality under overload. Another contribution of this paper is an improved analysis of the competitiveness for weighted deadline scheduling.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms-
dc.rights© 2001 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms in 2001, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectMathematics computersen_HK
dc.subjectAlgorithms-
dc.subjectMeasurement-
dc.subjectPerformance-
dc.subjectTheory-
dc.subjectVerification-
dc.titlePerformance guarantee for online deadline scheduling in the presence of overloaden_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW: twlam@cs.hku.hk-
dc.identifier.authorityLam, TW=rp00135-
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-64049107305-
dc.identifier.hkuros57741-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-64049107305&selection=ref&src=s&origin=recordpage-
dc.identifier.spage755-
dc.identifier.epage764-
dc.publisher.placeUnited States-
dc.identifier.scopusauthoridLam, TW=7202523165-
dc.identifier.scopusauthoridTo, KK=36785812300-
dc.customcontrol.immutablesml 160105 - merged-
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats