IEEE Transactions on Computers · 1975 · 110 citations · 19 references
ComputingComputer EngineeringComputer ScienceAlgorithmsSchedulingTheory Of ComputationCritical Path AnalysisGraph AlgorithmsResource SchedulingSchedule OptimizationScheduling OptimizationTask SchedulingCritical Path SchedulingDag SchedulingDirected Acyclic Graph SchedulingMultiprocessor SchedulingParallel SchedulingScheduling AlgorithmsScheduling In Multiprocessor SystemsTask Graphs
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.
19
Bounds on Multiprocessing Timing Anomalies
Ron Graham · SIAM Journal on Applied Mathematics · 1969 · 2.4K citations
Bounds for Certain Multiprocessing Anomalies
Ronald Graham · Bell System Technical Journal · 1966 · 1.6K citations
Parallel Sequencing and Assembly Line Problems
T. C. Hu · Operations Research · 1961 · 895 citations
Management, Industrial Engineering, Operations Management +10
Optimal scheduling for two-processor systems
E. G. Coffman, Ronald Graham · Acta Informatica · 1972 · 610 citations