Scheduling independent tasks to reduce mean finishing time

ABSTRACT

Sequencing to minimize mean finishing time (or mean time in system) is not only desirable to the user, but it also tends to minimize at each point in time the storage required to hold incomplete tasks. In this paper a deterministic model of independent tasks is introduced and new results are derived which extend and generalize the algorithms known for minimizing mean finishing time. In addition to presenting and analyzing new algorithms it is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution.

REFERENCES

• 1: Conway, R.W., Maxwell, W.L., and Miller, L.W. Theorv ol" Scheduling. Addison-Wesley, New York, 1900.
• 2: Ford, L.R., and Fulkerson, D.R. Flows in Networks. Princeton U. Press, Princeton, N.J., 1962.
• 3: Bruno, J. A scheduling algorithm for minimizing mean flow time. Tech. Rep. #141, Comput. Sci. Dept., Penn State U., University Park, Penna., July 1973.
• 4: 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]
• 5: Karp, R.M. Reducibility between combinatorial problems. In Complexity o/Computer Computations, R.E. Milker and J.W. Thatcher (Eds) Plenum Press, New York 1972, pp. 85-103.
• 6: Sahni, S. Some related problems from network flows, game theory and integer programming. 13th Ann. Syrup. on Switching and Automata Theory, Oct. 1972, pp. 130-139.
• 7: Ullman, J.D. Polynomial complete scheduling problems TR9. Dept. of Comput. Sci., U. of California at Berkeley, Mar. 1973.
• 8: Graham, R.L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech J. (Nov. 1966), 1563-1581.
• 9: Graham, R.L. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math 17, 2 (Mar. 1969), 416-429.
• 10: Coffman, E.G. On a conjecture concerning the comparison of SPT and LPT scheduling. Tech. Rep. #140, Comput. Sci. Dept., Penn State U., University Park, Penna., July 1973.

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:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms

Keywords:
deterministic scheduling models, minimizing mean finishing time, minimizing mean flow time, optimal scheduling algorithms, sequencing algorithms