%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 . 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
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.
Pages © WoTUG, or the indicated author. All Rights Reserved.
Comments on these web pages should be addressed to: www at wotug.org