Task scheduling is essential for the proper functioning of parallel processor systems. Scheduling of tasks onto networks of parallel processors is an interesting problem that is well-defined and documented in the literature. However, most of the available techniques are based on heuristics that solve certain instances of the scheduling problem very efficiently and in reasonable amounts of time. This paper investigates an alternative paradigm, based on genetic algorithms, to efficiently solve the scheduling problem without the need to apply any restricted assumptions that are problem-specific, such is the case when using heuristics. Genetic algorithms are powerful search techniques based on the principles of evolution and natural selection. The performance of the genetic approach will be compared to the well-known list scheduling heuristics. The conditions under which a genetic algorithm performs best will also be highlighted. This will be accompanied by a number of examples and case studies.

List-based priority schedulers have long been the dominant class of static scheduling algorithms. Such heuristics have been predominantly based on the ''critical path, most immediate successors first'' CP MISF priority. The ability of this type of scheduler to handle increased levels of communication overhead is examined in this paper. Three of the more popular list scheduling heuristics, Hu's LSH and Kruatrachue's ISH and DSH, are subjected to a performance-based comparison, with results demonstrating their inadequacies in communication-intensive cases. WINSCHED, a Microsoft Windows tool developed by the Parallel Computing Research Laboratory, is also briefly presented. WINSCHED uses a number of list-based heuristics to schedule a parallel program represented as an enhanced directed acyclic graph EDAG on an arbitrary number of homogeneous parallel processors. It supports six distinct heuristics with or without consideration of communication costs and has six interconnection topologies built in.