Paper Details

%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.

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.