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.