A New Algorithm for Preemptive Scheduling of Trees

ABSTRACT

An algorithm which schedules forests of n tasks on m identical processors in O(n log m) time, offline, is given. The schedules are optimal with respect to finish time and contain at most n - 2 preemptions, a bound which is realized for all n. Also given is a simpler algorithm which runs in O(nm) time on the same problem and can be adapted to give optimal finish time schedules on-line for independent tasks with release times.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: COFFMAN, E.G. J~., ED.Computer and Job-Shop Scheduling Theory. John Wiley and Sons, New York, 1976.
• 3: CONWAY, R.W., MAXWELL, W.L., AND MILLER, L.W.Theory of Scheduling Addison-Wesley, Reading, Mass., 1967.
• 4: DAVWA, G.I., AND LINTON, D.J. A new algorithm for the scheduling of tree structured tasks. Proc. 1976 Conf, inform. Sci. and Syst., Baltimore, Md., 1976, pp. 543-548.
• 5: Teofilo Gonzalez , Sartaj Sahni, Preemptive Scheduling of Uniform Processor Systems, Journal of the ACM (JACM), v.25 n.1, p.92-101, Jan. 1978 [doi>10.1145/322047.322055]
• 6: HORN, W.A Some simple scheduling algorithms. Naval Res. Log. Quart. 21 (1974), 177-185
• 7: Edward C. Horvath , Shui Lam , Ravi Sethi, A Level Algorithm for Preemptive Scheduling, Journal of the ACM (JACM), v.24 n.1, p.32-43, Jan. 1977 [doi>10.1145/321992.321995]
• 8: Hu, T.C Parallel sequencing and assembly line problems. Operations Res. 9, 6 (Nov. 1961), 841-848.
• 9: LAM, S, AND SETHI, R Worst case analysis of two scheduling algorithms. SIAM J. Comptg. 6 (1977), 518- 536
• 10: Jane W. S. Liu , Ai-Tsung Yang, Optimal scheduling of independent tasks on heterogeneous computing systems, Proceedings of the 1974 annual conference, p.38-45, January 1974 [doi>10.1145/800182.810377]
• 11: McNAuGHTON, R.Scheduling with deadhnes and loss functions. Management Sci. 12, 7(1959), 1-10.
• 12: MtmTZ, R'.R., AND COFFMAU, E.G. JR Optimal preemptive scheduling on two-processor systems. IEEE Trans. Comptr. C-18, 11(1969), 1014-1020.
• 13: R. R. Muntz , E. G. Coffman, Jr., Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems, Journal of the ACM (JACM), v.17 n.2, p.324-338, April 1970 [doi>10.1145/321574.321586]
• 14: SAHNI, S. Preemptive schedulmg with due dates. OperaUons Res. 27, 5 (Sept.-Oct. 1979), 925-934.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Measurement, Theory, Verification