J. Bruno
E. G. Coffman
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.
- 1 Conway, R.W., Maxwell, W.L., and Miller, L.W. Theorv ol" Scheduling. Addison-Wesley, New York, 1900.Google Scholar
- 2 Ford, L.R., and Fulkerson, D.R. Flows in Networks. Princeton U. Press, Princeton, N.J., 1962.Google Scholar
- 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.Google Scholar
- 4 Cook, S.A. The complexity of theorem proving procedures. 3rd ACM Syrup. on Theory of Computing, Shaker Heights, Oh., May 1971, pp. 151-158. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- 7 Ullman, J.D. Polynomial complete scheduling problems TR9. Dept. of Comput. Sci., U. of California at Berkeley, Mar. 1973.Google Scholar
- 8 Graham, R.L. Bounds for certain multiprocessing anomalies. Bell Syst. Tech J. (Nov. 1966), 1563-1581.Google ScholarCross Ref
- 9 Graham, R.L. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math 17, 2 (Mar. 1969), 416-429.Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Scheduling independent tasks to reduce mean finishing time
Recommendations
Scheduling independent tasks to reduce mean finishing-time (extended abstract)
SOSP '73: Proceedings of the fourth ACM symposium on Operating system principlesIn this paper we study the problem of scheduling a set of independent tasks on m ≥ 1 processors to minimize the mean finishing-time (mean time in system). The importance of the mean finishing-time criterion is that its minimization tends to reduce the ...
Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible
Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical ...
Scheduling independent tasks to reduce mean finishing-time (extended abstract)
In this paper we study the problem of scheduling a set of independent tasks on m ≥ 1 processors to minimize the mean finishing-time (mean time in system). The importance of the mean finishing-time criterion is that its minimization tends to reduce the ...
Comments