Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/40985
DC Field | Value | |
---|---|---|
dc.title | Two processor scheduling with real release times and deadlines | |
dc.contributor.author | Wu, H. | |
dc.contributor.author | Jaffar, J. | |
dc.date.accessioned | 2013-07-04T08:16:56Z | |
dc.date.available | 2013-07-04T08:16:56Z | |
dc.date.issued | 2002 | |
dc.identifier.citation | Wu, H.,Jaffar, J. (2002). Two processor scheduling with real release times and deadlines. Annual ACM Symposium on Parallel Algorithms and Architectures : 127-132. ScholarBank@NUS Repository. | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/40985 | |
dc.description.abstract | In a hard real-time system, critical tasks are subject to timing constraints such as release times and deadlines. All timing constraints must be satisfied when tasks are executed. Nevertheless, given a set of tasks, finding a feasible schedule which satisfies all timing constraints is NP-complete even on one processor. In this paper, we study the following special non-preemptive two processor scheduling problem: Given a set of UET (Unit Execution Time) tasks with arbitrary precedence constraints, individual real release times and deadlines, find a feasible schedule on two identical processors whenever one exists. The complexity status of this problem has been open for a long time, we propose the first polynomial algorithm for this problem. Our algorithm is underpinned by the key consistency notion: Successor-tree-consistency. The time complexity of our algorithm is O(n4), where n is the number of tasks. | |
dc.source | Scopus | |
dc.subject | Feasible schedule | |
dc.subject | Release time and deadline | |
dc.subject | Successor-tree-consistency | |
dc.subject | Task scheduling | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.sourcetitle | Annual ACM Symposium on Parallel Algorithms and Architectures | |
dc.description.page | 127-132 | |
dc.description.coden | AASAE | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.