Improved 0/1-interchange scheduling |
| |
| Authors: | Michael A Langston |
| |
| Institution: | (1) Computer Science Department, Washington State University, 99164 Pullman, WA, USA |
| |
| Abstract: | Consideration is given to the problem of nonpreemptively scheduling a set ofN independent tasks to a system ofM identical processors, with the objective to minimize the overall finish time. It is proved that the 0/1-INTERCHANGE scheduling heuristic can be modified, without increasing its time complexity fromO(N logM), so that its worst-case performance bound is reduced from 2 to 4/3 times optimal. |
| |
| Keywords: | multiprocessor scheduling approximation algorithms worst-case analysis |
| 本文献已被 SpringerLink 等数据库收录！ |
|
