Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40985
Title: Two processor scheduling with real release times and deadlines
Authors: Wu, H. 
Jaffar, J. 
Keywords: Feasible schedule
Release time and deadline
Successor-tree-consistency
Task scheduling
Issue Date: 2002
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40985
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

39
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.