A deterministic heuristic algorithm for optimal multiprocessor scheduling. (c1995)

Abstract

The general problem of multiprocessor scheduling can be stated as scheduling a set of computational tasks onto a multiprocessor system so that a set of performance criteria will be optimized. This scheduling problem is known to be NP-hard. The aim of tbis study is to reexamine the optimal scheduling strategies used in a mUltiprocessor system and to develop a quasi-deterministic metbod which will always yield a balanced load. The approximate optimal time needed to execute the partitioned computational jobs will be determined. This problem will be solved within tbe bounds of an approximated time complexity. Simulation results comparing tbe proposed algorithm with the simulated annealing algorithm using random task graphs, two different cost functions and various types of connection topologies will be presented.