Parallel Genetic Algorithms to Find Near Optimal Schedules for Tasks on Multiprocessor Architectures

摘要

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