Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors

ABSTRACT

The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n.

REFERENCES

• 1: 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]
• 2: BRUNO, J , COFFMAN, E G. JR , AND SETHI, R Algorithm for mmlmizang mean flow time information Processing 74, North-Holland, Amsterdam, pp 504-510
• 3: E. G. Coffman, Jr. , Ravi Sethi, A generalized bound on LPT sequencing, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.306-310, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806205]
• 4: CONWAY, R W., MAXWELL, W L , AND MILLER, L W Theory of Scheduhng, Addison-Wesley Pubhshmg Co , Reading, Mass , 1967
• 5: GONZALEZ, T, IBARRA, O H , AND SAHNI, S Bounds for LPT schedules on uniform processors. Comptr Scl Tech Pep No 75-1, U of Minnesota, Mmneapohs, Minn , 1974
• 6: GRAHAM, R L Bounds on multlprocessmg timing anomalies. SIAM J Apphed Math 17, 2 (March 1969), 416-429
• 7: Ellis Horowitz , Sartaj Sahni, Exact and Approximate Algorithms for Scheduling Nonidentical Processors, Journal of the ACM (JACM), v.23 n.2, p.317-327, April 1976 [doi>10.1145/321941.321951]
• 8: KARP, R M Reducibility among combinatorial problems In Complexity of Computer Computatlons, R E Miller and J W. Thatcher, Eds , Plenum Press, New York, 1972, pp, 85-103
• 9: SAHNI, S Computatlonally related problems SIAM J Comptg 3, 4 (Dec 1974), 262-279

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

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