File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973075.109
- Scopus: eid_2-s2.0-77951677770
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Algorithms and complexity for periodic real-time scheduling
Title | Algorithms and complexity for periodic real-time scheduling |
---|---|
Authors | |
Keywords | Algorithms and complexity Feasibility problem Multiprocessing systems Polynomial approximation Profitability |
Issue Date | 2010 |
Publisher | Society 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 Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 1350-1359 How to Cite? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/129587 |
ISSN | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bonifaci, V | en_HK |
dc.contributor.author | Chan, HL | en_HK |
dc.contributor.author | Marchetti-Spaccamela, A | en_HK |
dc.contributor.author | Megow, N | en_HK |
dc.date.accessioned | 2010-12-23T08:39:30Z | - |
dc.date.available | 2010-12-23T08:39:30Z | - |
dc.date.issued | 2010 | en_HK |
dc.identifier.citation | The 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), Austin, TX, 17-19 January 2010. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, p. 1350-1359 | en_HK |
dc.identifier.issn | 1071-9040 | - |
dc.identifier.uri | http://hdl.handle.net/10722/129587 | - |
dc.description.abstract | We 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.language | eng | en_US |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms | en_HK |
dc.rights | © 2010 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms in 2010, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Algorithms and complexity | - |
dc.subject | Feasibility problem | - |
dc.subject | Multiprocessing systems | - |
dc.subject | Polynomial approximation | - |
dc.subject | Profitability | - |
dc.title | Algorithms and complexity for periodic real-time scheduling | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_HK |
dc.identifier.authority | Chan, HL=rp01310 | en_HK |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/1.9781611973075.109 | - |
dc.identifier.scopus | eid_2-s2.0-77951677770 | en_HK |
dc.identifier.hkuros | 177253 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-77951677770&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.spage | 1350 | en_HK |
dc.identifier.epage | 1359 | en_HK |
dc.identifier.scopusauthorid | Bonifaci, V=13906813700 | en_HK |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_HK |
dc.identifier.scopusauthorid | MarchettiSpaccamela, A=7004071298 | en_HK |
dc.identifier.scopusauthorid | Megow, N=8680826900 | en_HK |
dc.identifier.issnl | 1071-9040 | - |