Genetic List Scheduling Algorithm for Scheduling and Allocation on a Loosely Coupled Heterogeneous Multiprocessor System

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