A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem

M.M. Glybovets, N.M. Gulayeva, M.M. Pasichnyk

Abstract


This paper describes the development and implementation of a parallel genetic algorithm (GA) to solve scheduling the university class problem. The proposed GA is based on the "farmer-workers" model and uses a number of heuristics, e. g. classroom and time selection during population initialization, adding useful subsolutions into the initial population, using special (new) mutation operator. In the algorithm a specific chromosome coding and fitness function that takes into account a number of restrictions on the resulting schedule are proposed. Problem-specific crossover and mutation operators are developed. Based on a number of computational experiments optimal parameters of GA are proposed for further use.

Full Text:

PDF (Ukrainian)

References


Коффман Э.Г. Теория расписаний и вычислительные машины. М.: Наука, 1984. – 335 с.

Конькова И.С. Генетические алгоритмы в решении задачи составления расписания занятий в вузе // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей XII Междунар. науч-но-техн. конф. – Пенза: ПДЗ, 2012. – С. 26–29.

Busetti F. Simulated annealing overview, 2009. – Available at:

http://www.cs.ubbcluj.ro/~csatol/mestint/pdfs/Busetti_AnnealingIntro.pdf

Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми. – К.: НаУКМА, 2013. – 828 с.

Глибовец H.Н., Медвідь С.А. Генетичиские агоритмы и их использование для решения задачи составления расписания // Кибернетика и системный анализ. – 2003. – № 1. – С. 95–108.

Бутко В.В., Бурбело С.М. та інші. Розробка автоматизованої системи формування розкладу магістратури // Наукові праці ВНТУ. – 2009. – №4. – С. 91–94.

Бидюк П.И., Литвиненко В.И., Токарь А.А. Параллельные генетические алгоритмы // Системні дослідження та інформаційні технології. – 2002. – № 4. – С. 7–16.


Refbacks

  • There are currently no refbacks.