Scheduling independent processors with different storage capacities

ABSTRACT

The analysis of multiprocessor scheduling strategies has been the focus of substantial research in recent years. Because of the inherent complexity of the general scheduling problem, many researchers have proposed simple mathematical models of computing systems and analyzed the worst-case performance bounds of heuristic scheduling algorithms. This paper presents the analysis of simple scheduling strategies on a model of a computer system with an arbitrary number of identical but independent processors each with a possibly different storage capacity. Most simple strategies are shown to be unattractive as the bound on their worst-case behavior increases without limit. However, two strategies are presented with worst-case bounds asymptotically approaching 2. In addition, if the system has a preemptive-resume feature, a simple optimal strategy exists that will produce minimal-length schedules for any given task set.

REFERENCES

• 1: Hu, T.C., "Parallel Sequencing and Assembly Line Problems," Operations Research, (9,6), 1961, (841-848).
• 2: Fujii, M., Kasami, T., and Ninomiya, N., "Optimal Sequencing of Two Equivalent Processors," SIAM J. Applied Math., (17,3), 1969, (784-789).
• 3: Graham, R.L., "Bounds on Multiprocessing Timing Anomalies," SIAM J. Applied Math., (17,2), March, 1969, (416-429).
• 4: 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]
• 5: Coffman, E.G., Jr., Graham, R.L., "Optimal Scheduling for Two Processor Systems," Acta Informatica, (1), 1972, (200-213).
• 6: Graham, R.L., "Bounds on Multiprocessing Anomalies and Related Packing Algorithms," Proceedings of SJCC, 1972, (205-217).
• 7: J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
• 8: K. L. Krause , V. Y. Shen , H. D. Schwetman, A task-scheduling algorithm for a multiprogramming computer system, Proceedings of the fourth ACM symposium on Operating system principles, p.112-118, January 1973
• 9: Johnson, S.M., "Optimal Two- and Three-Stage Production Schedules with Setup Times Included," Naval Res. Log. Quart. 1, (1), 1954.
• 10: Shen, V.Y. and Chen, Y.E., "A Scheduling Strategy for the Flow-Shop Problem in a System with Two Classes of Processors," Proc. 6th Princeton Conf. on Information Sciences and Systems, March, 1972.
• 11: Buten, R.E. and Shen, V.Y., "Analysis of the Flow-Shop Scheduling Problem in a System with Two Classes of Processors," Proc. 8th Princeton Conf. on Information Sciences and Systems, March, 1974.
• 12: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 13: Karp, R.M., "Reducibility among Combinatorial Problems," TR3, Dept. of Computer Science, Univ. of California at Berkeley, April, 1972. Also in Complexity of Computer Computations, Miller, et.al., editors, Plenum Press, New York, 1972.
• 14: J. D. Ullman, Polynomial complete scheduling problems, Proceedings of the fourth ACM symposium on Operating system principles, p.96-101, January 1973
• 15: M. R. Garey , R. L. Grehem, Bounds on scheduling with limited resources, Proceedings of the fourth ACM symposium on Operating system principles, p.104-111, January 1973
• 16: Joseph, E.C., "Innovations in Heterogeneous and Homogeneous Distributed-Function Architectures," Computer, March, 1974, (17-24).
• 17: IBM, "System/360 Operating System MFT Guide," International Business Machines, GC27-6939-10, March, 1972.
• 18: Dennis George Kafura, Analysis of scheduling algorithms for a model of a multiprocessor computer system., 1974

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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms

Keywords:
Deterministic scheduling models, Minimizing completion time, Scheduling algorithms