A Preliminary Evaluation of the Critical Path Method for Scheduling Tasks on Multiprocessor Systems
- 1 December 1975
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-24 (12) , 1235-1238
- https://doi.org/10.1109/t-c.1975.224171
Abstract
The problem of scheduling tasks on a system of independent identical processors is discussed and the performance of a suboptimal method is evaluated. The computation is modeled by an acyclic directed graph G(T,<), where node set T represents the set of tasks to be completed and edge set < defines the precedence between tasks. The objective is to minimize the finishing time of the computation graph. Known theoretical results are reviewed and a general branch-and-bound algorithm for finding optimal solutions is presented. The schedules produced by a simple critical path priority method are shown to be near optimal for randomly generated computation graphs.Keywords
This publication has 20 references indexed in Scilit:
- Exact, Approximate, and Guaranteed Accuracy Algorithms for the Flow-Shop Problem n / 2 / F / F¯Journal of the ACM, 1975
- An Almost-Optimal Algorithm for the Assembly Line Scheduling ProblemIEEE Transactions on Computers, 1974
- Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation ProblemsJournal of the ACM, 1974
- Optimal Scheduling Strategies in a Multiprocessor SystemIEEE Transactions on Computers, 1972
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor SystemsJournal of the ACM, 1970
- Priority Assignment in a Network of ComputersIEEE Transactions on Computers, 1969
- Optimal Preemptive Scheduling on Two-Processor SystemsIEEE Transactions on Computers, 1969
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Production and Stabilization of Real-Time Task SchedulesJournal of the ACM, 1967
- Parallel Sequencing and Assembly Line ProblemsOperations Research, 1961