Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published December 1974 | public
Journal Article

A comparison of list schedules for parallel processing systems

Abstract

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.

Additional Information

© 1974 Association for Computing Machinery, Inc. Received April 1973; revised February 1974. This work was supported by NSF Grant GJ-35109. The authors would like to thank Professor Edward G. Coffman for his suggestions.

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023