Two processor scheduling with real release times and deadlines

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.