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
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

CACM July, 1974

Bruno, J.
Coffman, E. G. Jr.
Sethi, R.

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

4.32 5.39

CA740704 JB January 17, 1978  12:56 PM

2627	5	2627
2627	5	2627
2627	5	2627