SCHEDULING MULTIPLE DIVISIBLE LOADS.
- Resource Type
- Article
- Authors
- Drozdowski, M.; Lawenda, M.; Guinand, F.
- Source
- International Journal of High Performance Computing Applications. Spring2006, Vol. 20 Issue 1, p19-1. 1p. 8 Graphs.
- Subject
- *SCHEDULING
*COMPUTATIONAL complexity
*COMPUTER networks
*ARRAY processors
*COMPUTER systems
*PROGRESS reports
*HEURISTIC
*POLYNOMIALS
*COMMUNICATION
- Language
- ISSN
- 1094-3420
The article discusses the scheduling of multiple divisible loads on a star network of processors. It is demonstrated that this problem is computationally hard for unrelated processors, and for uniform processors with simultaneous completion requirement. Special cases solvable in polynomial times are identified. Limits on the performance of heuristics for the problem have been recognized. The complexity of scheduling on uniform processors without simultaneous completion, and scheduling on identical processors remains unidentified.