J. Eruno
E. G. Coffman
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 mean number of unfinished tasks in the system. In the paper we give a reduction of our scheduling problem to a transportation problem and thereby extend the class of known non enumerative scheduling algorithms [1]. Next we show that the inclusion of weights (weighted mean finishing-time) complicates the problem and speculate that there may be no non enumerative algorithm for this case. For the special case of identical processors we study the maximum finishing-time properties of schedules which are optimal with respect to mean finishing-time. Finally we give a scheduling algorithm having desirable properties with respect to both maximum finishing-time and mean finishing-time.
- 1 Conway, R. W., Maxwell, W. L., and Miller, L. W., "Theory of Scheduling," Addison-Wesley.Google Scholar
- 2 Ford, L. R. and Fulkerson, D. R., "Flows in Networks," Princeton University Press, 1962.Google Scholar
- 3 Karp, R. M., "Reducibility between Combinatorial Problems," in R. E. Miller and J. W. Thatcher (eds), Complexity of Computer Computations, Plenum Press, N. Y. (1972), pp. 85-103.Google Scholar
Index Terms
- Scheduling independent tasks to reduce mean finishing-time (extended abstract)
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 ...
Scheduling independent tasks to reduce mean finishing time
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 ...
Minimizing mean flow time for UET tasks
We consider the problem of scheduling a set of n unit-execution-time (UET) tasks, with precedence constraints, on m ≥ 1 parallel and identical processors so as to minimize the mean flow time. For two processors, the Coffman--Graham algorithm gives a ...
Comments