Scheduling independent tasks to reduce mean finishing time
- 1 July 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 17 (7), 382-387
- https://doi.org/10.1145/361011.361064
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.Keywords
This publication has 7 references indexed in Scilit:
- Polynomial complete scheduling problemsPublished by Association for Computing Machinery (ACM) ,1973
- Some related problems from network flows, game theory and integer programmingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966
- Flows in NetworksPublished by Walter de Gruyter GmbH ,1963