Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system
M. Grajcar · 1999
Our problem consists of a partially ordered set of tasks communi-cating over a shared bus which are to be mapped to a heterogeneous multiprocessor system. The goal is to minimize the makespan, while satisfying constrains implied by data dependencies and ex-clusive resource usage. We present a new efficient heuristic approach based on list scheduling and genetic algorithms, which finds the optimum in few seconds on average even for large examples (up to 96 tasks) taken from [3]. The superiority of our algorithm compared to some other algorithms is demonstrated.