Adam, Thomas L. and Chandy, K. M. and Dickson, J. R. (1974) A comparison of list schedules for parallel processing systems. Communications of the ACM, 17 (12). pp. 685-690. ISSN 0001-0782. doi:10.1145/361604.361619. https://resolver.caltech.edu/CaltechAUTHORS:20190111-160504256
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190111-160504256
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.
| Item Type: | Article | ||||||
|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||
| 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. | ||||||
| Funders: |
| ||||||
| Subject Keywords: | parallel processing, precedence graphs, scheduling, list scheduling, optimization, dynamic programing | ||||||
| Issue or Number: | 12 | ||||||
| Classification Code: | CR Categories: 4.3, 4.32, 4.34, 4.35, 5.3, 5.32, 5.4, 5.42, 8.1 | ||||||
| DOI: | 10.1145/361604.361619 | ||||||
| Record Number: | CaltechAUTHORS:20190111-160504256 | ||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20190111-160504256 | ||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||
| ID Code: | 92231 | ||||||
| Collection: | CaltechAUTHORS | ||||||
| Deposited By: | Tony Diaz | ||||||
| Deposited On: | 12 Jan 2019 05:47 | ||||||
| Last Modified: | 16 Nov 2021 03:48 |
Repository Staff Only: item control page
