A Preliminary Evaluation of the Critical Path Method for Scheduling Tasks on Multiprocessor Systems

Author

Kohler, Walter H.

Author_Institution

Department of Electrical and Computer Engineering, University of Massachusetts

Issue

12

fYear

1975

Firstpage

1235

Lastpage

1238

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

Acyclic directed graph model, branch-and-bound algorithm, critical path priority method, multiprocessor scheduling.; Algorithm design and analysis; Computational modeling; Finishing; Multiprocessing systems; Optimal scheduling; Polynomials; Processor scheduling; Scheduling algorithm; Tree graphs; Acyclic directed graph model, branch-and-bound algorithm, critical path priority method, multiprocessor scheduling.;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/T-C.1975.224171

Filename

1672764