A comparison of list schedules for parallel processing systems

✍ Scribed by Adam, Thomas L.; Chandy, K. M.; Dickson, J. R.

• Book ID: 120597528
• Publisher: Association for Computing Machinery
• Year: 1974
• Tongue: English
• Weight: 604 KB
• Volume: 17
• Category: Article
• ISSN: 0001-0782
• DOI: 10.1145/361604.361619

✦ Synopsis

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.