Institute of Electrical and Electronics Engineers, Computer Architecture News, 3b(18), p. 439-446, 1990
Proceedings of the 4th international conference on Supercomputing - ICS '90
DOI: 10.1145/77726.255186
Full text: Unavailable
The problem of scheduling a set of partially ordered tasks on a nonpreemptive multiprocessor system of identical processors assuming that the execution time of some tasks can vary within a set of known values is studied in an effort to construct a more realistic static schedule. A new heuristic algorithm (CP/MISF/TD) based on task duplication is proposed. The effectiveness of the algorithm is proved by comparing the results obtained for a wide variety of task graphs with the ones obtained by applying the classical list scheduling algorithms which consider fixed time tasks. Keywords: Static scheduling, List scheduling, Heuristic algorithms, Task duplication, Multiprocessor systems.