EFFICIENCY RESEARCH OF PARALLEL GENETIC ALGORITHMS FOR SOLVING UNIVERSITY TIMETABLE SCHEDULING PROBLEM BASING
ON A GRID SYSTEM
M.D. Godlevskiy, A.A. Ababilov
The
efficiency of parallel genetic algorithms running on Grid system for solving a timetable
scheduling problem is investigated. The mentioned problem belongs to the class
of multicriteria optimization problems and is
NP-complete. Application of genetic algorithms simplifies the support of
numerous requirements to schedule and makes it easy to add new ones. Impact of
genetic operators (selection, crossover etc.) and their parameters for population
quality are reviewed. The efficiency of parallel genetic algorithms of two
types – using the island model and dynamic demes – is investigated. The
influence of processes on speed of the genetic search is considered. The conditions of appropriate use of dynamic demes genetic
algorithm for a timetable scheduling problem are defined.
Key words: NP-complete problem, multicriteria optimization, genetic algorithms, parallel
computing, Grid system, efficiency of algorithms, timetable scheduling.