Bounds on the Number of Processors and Time for Multiprocessor Optimal Schedules
- 1 August 1973
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-22 (8) , 745-751
- https://doi.org/10.1109/tc.1973.5009153
Abstract
Two problems of importance for the scheduling of multiprocessing systems composed of identical units are discussed in this paper. 1) Given a partially ordered set of computations represented by the vertices of an acyclic directed graph with their associated execution times, find the minimum number of processors in order to execute them in a time not exceeding the length of the critical path of this graph. 2) Determine the minimum time to process this set of computations when a fixed number of processors is available. A unified formulation for lower bounds on the minimum number of processors and on time is presented. These lower bounds are sharper than previously known values and provide a general framework that gives insight for deriving simplified expressions. A new upper bound on the minimum number of processors is presented, which is sharper than the known bounds. The computational aspects of these bounds are also discussed.Keywords
This publication has 6 references indexed in Scilit:
- Optimal Scheduling Strategies in a Multiprocessor SystemIEEE Transactions on Computers, 1972
- Legality and Other Properties of Graph Models of ComputationsJournal of the ACM, 1970
- Bounds for Maxium Parallelism in a Bilogic Graph Model of ComputationsIEEE Transactions on Computers, 1969
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961
- Scheduling with Deadlines and Loss FunctionsManagement Science, 1959
- A Decomposition Theorem for Partially Ordered SetsAnnals of Mathematics, 1950