%T Parallel Genetic Algorithms to Find Near Optimal Schedules for Tasks on Multiprocessor Architectures
%A  M. Moore
%E  Alan G. Chalmers,  Majid Mirmehdi,  Henk Muller
%B Communicating Process Architectures 2001
%X Parallel genetic schedulers (PGS) are applied to a
   combinatorial optimisation problem, the scheduling of
   multiple, independent, non\-identical tasks. The tasks are
   functionally partitioned and must be distributed over a
   multicomputer or multiprocessor system. As each task
   completes execution, a result message must be communicated.
   Communication occurs over a shared bus. This problem is
   known to be NP\-complete [1]. The PGS execute on a shared
   memory multiprocessor system and on a simulated SIMD torus.
   Schedules produced by the PGS are compared to each other, to
   those found by an exponential\-time optimal branch and bound
   algorithm, and to those found by a linear\-time
   opportunistic algorithm. The PGS produce extremely accurate
   schedules very quickly. When the PGS are executed with
   increasing numbers of processors, near linear speedups are
   obtained with no decrease in the quality of the resulting
   schedules.