Scheduling Tasks with Nonuniform Deadlines on Two Processors

ABSTRACT

Given a set @@@@ = {T1,T2,···,Tn} of tasks, with each Ti having execution time 1 and a deadline di > 0, and a set of precedence constraints which restrict allowable schedules, the problem of determining whether there exists a schedule using two processors in which each task is completed before its deadline is examined. An efficient algorithm for finding such a schedule, whenever one exists, is given. The algorithm may also be used to find the shortest such schedule. In addition it is shown that the problem of finding a one-processor schedule which minimizes the number of tasks failing to meet their deadlines is NP-complete and, hence, is likely to be computationally intractable.

REFERENCES

• 1: AH0, A.V., GAREY, M.R., AND ULLMAN, J.D. The transitive reduction of a directed graph SIAM J. Comput. 1 (1972), 131-137.
• 2: AHO, A.V., HOPCROFT, J.E., AND ULLMAN, j.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974, Ch. 10.
• 3: ARLAZAROV, V.L., DINXC, E.A., KRONOD, M.A., AND FARADZEV, I.A. On economical construction of the transitive closure of an oriented graph. Dokl. Akad. Nauk SSSR 11 (1970), 1209-1210.
• 4: COFFMAN, E.G., AND GRAHAM, R.L. Optimal scheduling for two-processor systems Acta lnformatica 1 (1972), 2{}0-213.
• 5: FISCHF.R, M J, AND MEYER, A.R. Booleanmatrix multiplication and transitive closure. Twelfth Ann. Symp on Switching and Automata Theory, East Lansing, Mlch, 1971, pp. 129-131.
• 6: FuJII, M., KASAMI, T., AND NINOMIYA, K Optimal sequencing of two equivalent processors. SIAM J. Appl. Math. 17 (1969), 784-789.
• 7: FuJII, M., KASAMI, W., AND NINOMIYA, K Erratum. SIAM J. Appl. Math. ~0 (1971), 141.
• 8: G^REY, M.R., AND JOHNSON, D.S. Complexity results for multiprocessor scheduling under resource constraints SIAM J. Comput. ~ (1975), 397--411.
• 9: GRAhAm, R.L. Bounds on multiprocessing anomalies and related packing algorithms. Proc. AFIPS 1972 SJCC, Vol. 40, AFIPS Press, Montvale, N.J., pp. 205--217.
• 10: KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computat,ons, R.E. Miller and J W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85--104.
• 11: MooRE, M.J. An n job, one-machine sequencing algorithm for minimizing the number of late jobs. Manage. Sci. 15 (1968), 102-109.
• 12: Yoichi Muraoka, Parallelism exposure and exploitation in programs, 1971
• 13: PURDOM, P. A transitive closure algorithm. BIT 10 (1970), 76-94.
• 14: SIDNEY, J.B An extension of Moore's due date algorithm. In Symposium on the Theory of Scheduling and Its Applications, S.M. Elmaghraby, Ed., Springer-Verlag, New York, 1973, pp. 393-398.
• 15: ULLMAN, J.D. NP-complete scheduling problems. J. Comput. Syst. Scis. i0 (1975), 384-393.
• 16: Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Performance, Theory, Verification