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-pre-emptive 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(n⁴), where n is the number of tasks.

REFERENCES

• 1: M. Garey, B. S. D. S. Johnon, and R. Tarjan. Scheduling unit-time jobs with arbitrary release times and deadlines. SIAM J. Comput., 10(2):256--269, 1981.
• 2: M. R. Garey , D. S. Johnson, Scheduling Tasks with Nonuniform Deadlines on Two Processors, Journal of the ACM (JACM), v.23 n.3, p.461-467, July 1976 [doi>10.1145/321958.321967]
• 3: M. Garey and D. Johnson. Two processor cheduling with start-times and deadlines. SIAM J. Comput., 6(3):416--426, 1977.
• 4: M. Garey, D. Johnon, R. Tarjan, and M. Yannakaki. Scheduling opposing forests. SIAM J. Alg. Disc. Meth., 4(1):72--93, March 1983.
• 5: E. L. Lawler, J. Lentra, A. R. Kan, and D. Schmoy. Sequencing and cheduling: Algorithms and complexity. Handbooks in Operations research and management science, volume 4: Logistic of production and inventory, edited by S. C. Graves, A. H. G. Rinnooy Kan and P. Zipkin, North-Holland, pages 445--522, 1993.
• 6: B. Simon. Multiprocessor cheduling of unit-time jobs with arbitrary release times and deadlines. SIAM J. Comput., 12(2):294--299, 1983.
• 7: Barbara B. Simons , Manfred K. Warmuth, A fast algorithm for multiprocessor scheduling of unit-length jobs, SIAM Journal on Computing, v.18 n.4, p.690-710, Aug. 1989 [doi>10.1137/0218048]
• 8: Hui Wu , Joxan Jaffar , Roland Yap, A Fast Algorithm for Scheduling Instructions with Deadline Constraints on RISC Processors, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.281, October 15-19, 2000
• 9: Hui Wu , Joxan Jaffar , Roland H. C. Yap, Instruction Scheduling with Timing Constraints on a Single RISC Processor with 0/1 Latencies, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.457-469, September 18-21, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS

General Terms:
Algorithms

Keywords:
feasible schedule, release time and deadline, successor-tree-consistency, task scheduling