Please use this identifier to cite or link to this item:
|Title:||Two processor scheduling with real release times and deadlines|
|Authors:||Wu, H. |
Release time and deadline
|Source:||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.|
|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.|
|Source Title:||Annual ACM Symposium on Parallel Algorithms and Architectures|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 9, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.