File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Algorithms and complexity for periodic real-time scheduling

TitleAlgorithms and complexity for periodic real-time scheduling
Authors
KeywordsAlgorithms and complexity
Feasibility problem
Multiprocessing systems
Polynomial approximation
Profitability
Issue Date2010
PublisherSociety for Industrial and Applied Mathematics.
Citation
The 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, TX., 17-19 January 2010. In Proceedings of the 21st SODA, 2010, p. 1350-1359 How to Cite?
AbstractWe investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial time algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems. The complexity of some of these problems has been open for a long time. We also propose a profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. Copyright © by SIAM.
Persistent Identifierhttp://hdl.handle.net/10722/129587
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorBonifaci, Ven_HK
dc.contributor.authorChan, HLen_HK
dc.contributor.authorMarchettiSpaccamela, Aen_HK
dc.contributor.authorMegow, Nen_HK
dc.date.accessioned2010-12-23T08:39:30Z-
dc.date.available2010-12-23T08:39:30Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, TX., 17-19 January 2010. In Proceedings of the 21st SODA, 2010, p. 1350-1359en_HK
dc.identifier.issn1071-9040-
dc.identifier.urihttp://hdl.handle.net/10722/129587-
dc.description.abstractWe investigate the preemptive scheduling of periodic tasks with hard deadlines. We show that, even in the uniprocessor case, no polynomial time algorithm can test the feasibility of a task system within a constant speedup bound, unless P = NP. This result contrasts with recent results for sporadic task systems. For two special cases, synchronous task systems and systems with a constant number of different task types, we provide the first polynomial time constant-speedup feasibility tests for multiprocessor platforms. Furthermore, we show that the problem of testing feasibility is coNP-hard for synchronous multiprocessor task systems. The complexity of some of these problems has been open for a long time. We also propose a profit maximization variant of the feasibility problem, where every task has a non-negative profit, and the goal is to find a subset of tasks that can be scheduled feasibly with maximum profit. We give the first constant-speed, constant-approximation algorithm for the case of synchronous task systems, together with related hardness results. Copyright © by SIAM.en_HK
dc.languageengen_US
dc.publisherSociety for Industrial and Applied Mathematics.-
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010en_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rightsThe Annual ACM - SIAM Symposium on Discrete Algorithms Proceedings. Copyright © Society for Industrial and Applied Mathematics.-
dc.subjectAlgorithms and complexity-
dc.subjectFeasibility problem-
dc.subjectMultiprocessing systems-
dc.subjectPolynomial approximation-
dc.subjectProfitability-
dc.titleAlgorithms and complexity for periodic real-time schedulingen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_HK
dc.identifier.authorityChan, HL=rp01310en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.scopuseid_2-s2.0-77951677770en_HK
dc.identifier.hkuros177253en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77951677770&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage1350en_HK
dc.identifier.epage1359en_HK
dc.description.otherThe 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, TX., 17-19 January 2010. In Proceedings of the 21st SODA, 2010, p. 1350-1359-
dc.identifier.scopusauthoridBonifaci, V=13906813700en_HK
dc.identifier.scopusauthoridChan, HL=7403402384en_HK
dc.identifier.scopusauthoridMarchettiSpaccamela, A=7004071298en_HK
dc.identifier.scopusauthoridMegow, N=8680826900en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats