Автоматизация построения расписания экзаменов ВУЗа с использованием генетического алгоритма



Автоматизация построения расписания экзаменов ВУЗа с использованием генетического алгоритма

М.Ю. Жукова, В.М. Аль-Габри

Донской государственный технический университет, Ростов-на-Дону

Аннотация:В данной статье рассматривается решение проблемы автоматизированного формирования рационального расписания экзаменов вуза с помощью генетического алгоритма. Предложенный метод учитывает ряд требований необходимых для решения проблемы формирования расписания экзаменов. В данной работе, в процессе формирования начального допустимого расписания экзаменационной сессии, уделяется особое внимание последовательности экзаменов. Для улучшения качества полученного расписания был использован генетический алгоритм, позволяющий минимизировать число нарушений заданных мягких ограничений.

Ключевые слова:генетическийалгоритм, расписание, экзамены, ВУЗ, учебная группа.

Введение:В настоящее время достаточно большое количество слушателей различных курсов и образовательных программ по итогам зачисления в учебные заведения, в процессе обучения, а также на этапе квалификации, имеют необходимость пройти через экзаменационные испытания. Процесс укрупнения вузов, реализуемый в настоящее время в РФ, приводит их к значительному территориальному росту, увеличению контингента обучающихся и профессорско-преподавательского состава. Это, в свою очередь, обуславливает рост общего числа экзаменов сессии и увеличивает сложность решения задачи формирования расписаний. Кроме того, задача осложняется наличием у каждого вуза своих специфических требований, что делает разработку универсального метода практически невозможным [1].

Российская образовательная система, традиционно ориентированная на технологию обучения в академических группах, находится только в начале пути индивидуализации. В связи с этим, актуальность решения задачи разработки расписания экзаменов, в процессе развития российского образования, будет только возрастать [2].

Формально расписание экзаменов это отношение, построенное на прямом произведении множеств объектов: учебная группа, преподаватель, дисциплина [3]. Для решения задачи формирования расписания экзаменов принимается разные методы и технологии, основанные на классических методах и алгоритмах целочисленного программирования, методах раскраски графов. Кроме того, применяются методы: полного перебора, ветвей и границ, а также эвристические методы, в том числе основанные на генетических алгоритмах [4].

Цельданной работы заключается в разработке метода формирования рационального расписания экзаменов в высшем учебном заведении.

Постановка задачи

        (1)

– множество учебных групп, гдеng - название группы,cnt - количество студентов в группе;

(2)

– множество преподавателей;

   (3)

– множество дисциплин;

        (4)

– множество диапазонов дат, для проведения экзаменационной сессии.

Множество временных интервалов для расписания экзаменов можно представить в виде:

   (5)

гдеdate– дата из диапазона (dtstart,dtend)i,tm - временной интервал, принадлежащий дню, когда может быть проведен экзамен (tm=1 - первая половина дня,tm=2 - вторая половина дня экзамена).

Множество учебных аудиторий можно представить в следующем виде:

 (6)

гдеnr - название аудитории,rns - вместимость,tr - тип аудитории;

При формировании расписания экзаменов необходимо учитывать ряд требований, предъявляемых к этому расписанию. Требования можно определить как жесткие и мягкие ограничения. Под жесткими ограничениями будем рассматривать требования, нарушение которых приводит к недопустимости использования построенного расписания. К мягким отнесем рекомендации и пожелания [5]. В таблице 1 рассмотрены ограничения с их весовыми коэффициентами.

Таблица . Требования к расписанию экзаменов

Ограничение

Весовой коэффициент

1. Жесткие ограничения

1.1.

В одной учебной группе не может быть более одного экзамена в один и тот же временной интервал

k11

1.2.

Один преподаватель не может проводить более одного экзамена в один и тот же временной интервал

k12

1.3.

Одна аудитория не может быть использована для проведения более чем одного экзамена в один и тот же временной интервал

k13

1.4.

В одной учебной группе минимальный временной промежуток между экзаменами составляет 2 дня

k14

1.5.

Количество посадочных мест в аудитории должно быть больше или равно количеству студентов в группе

k15

2. Мягкие ограничения

2.1.

Для учебной группы учитывается порядок следования экзаменов, прогнозирующий наилучшую успеваемость [6]

k21

2.2.

В одной учебной группе минимальный временной промежуток между экзаменами не менее 3 дней

k22

2.3.

Количество свободных посадочных мест в аудитории не превышает 20% от ее общей вместимости

k23

2.4.

Один преподаватель проводит не более одного экзамена в один день

k24

Объемы нарушений ограничений определяются по следующим формулам:

    (7)

где  - функция, определяющая нарушение ограничения 1.1,countExamG()- функция, определяющая количество экзаменов в группеgi во временном интервалеdtej.

    (8)

где  - функция, определяющая нарушение ограничения 1.2,countExamT()- функция, определяющая количество экзаменов у преподавателяti во временном интервалеdtej.

    (9)

где  - функция, определяющая нарушение ограничения 1.3,countExamR()- функция, определяющая количество экзаменов в аудиторииri во временном интервалеdtej.

(10)

где  - функция, определяющая нарушение ограничения 1.4.

   (11)

где- функция, определяющая нарушение ограничения 1.5,countst() - функция, определяющая количество студентов в группе,RoomCap() - функция, определяющая количество посадочных мест в аудитории.

    (12)

где  - функция, определяющая нарушение ограничения 2.1,  -  функция получения коэффициента успеваемости группы по заданной последовательности экзаменов (wi).

   (13)

где  - функция, определяющая нарушение ограничения 2.2.

      (14)

где- функция, определяющая нарушение ограничения 2.3,countst() - функция, определяющая количество студентов в группе,RoomCap() - функция, определяющая количество посадочных мест в аудитории,iRecom - рекомендуемый максимальный процент свободных мест в аудитории.

   (15)

где  - функция, определяющая нарушение ограничения 2.4,countExamT()- функция, определяющая количество экзаменов у преподавателяti в день экзаменаej (dateej).

Для определения качества сформированного расписания экзаменов используется целевая функция, представляющая собой количественную оценку нарушений ограничений [7].

                         (16)

гдеkij – весовой коэффициент ограничения,cij – объем нарушенийij -го ограничения,n – число  типов ограничений (в данном случаеn =2),mi -количество ограниченийi-го типа,x - текущее решение.

Алгоритм построения допустимого расписания

При построении допустимого расписания основополагающим фактором является использование заранее известной последовательности экзаменов, прогнозирующей наилучшую успеваемость группы.

aProgress = {(gi, (e1,e2, …,ene,w)j) |giG,j=,wϵ[0, 1]} – массив зависимостей успеваемости группы от порядка следования экзаменов, отсортированные по убываниюw,el – экзамен с порядковым номеромl,w - коэффициент успеваемости группы.

(e1,e2, …,ene)jProgress =getSequence(gi,jProgress) – функция, получающая для группыgi, по порядковому номеруjProgress последовательность экзаменов из массиваaProgress.

minTimeout - минимально количество дней между экзаменами.

normTimeout - рекомендуемое количество дней между экзаменами.

countApptExams- количество расставленных экзаменов в группе.

Qallnappt - очередь из всех нераспределенных экзаменов.

eCount() - функция вычисления количества экзаменов в группе.

maxTOgi-максимально допустимый интервал между экзаменами в период заданного диапазона.

getCountApptExams() -функция получения количества расставленных экзаменов.

addExamToQ() - функция добавления экзамена в очередь.

removeExamFromQ() - функция удаления экзамена из очереди.

isApptExam() -функция проверки расставлен ли экзамен (true -  расставлен,false - не расставлен).

setRDExam() - функция присвоения пространственно-временной характеристика экзамену.

getPossibleDate() - функция получения возможной даты из диапазона дат для проведения экзамена.

getNextDate() - функция получения следующей даты.

Псевдокод алгоритма построения допустимого расписания экзаменов:

1Сортировка групп по диапазонам сессии.

2Цикл по группамgiG

3ВычислитьeCount(gi)

4ВычислитьmaxTOgi с округлением в меньшую сторону

5Если (maxTOgi<minTimeout)

6ТО переход на шаг 2

7ИНАЧЕ

8ЕСЛИgetCountApptExmas(gi) == eCount(gi)

9ТО переход на шаг 2

10ИНАЧЕ

11ПРИСВАИВАЕМjProgress = 1

12ПРИСВАИВАЕМ Qjpgi = getSequence(gi, jProgress)

13ПРИСВАИВАЕМcountApptExmas[gi] = 0

14ЦИКЛ ПОКА не конец очередиQjpgi

15ЕСЛИisApptExam(ej) ==true

16ТО

17removeExamFromQ(ej,Qjpgi)

18countApptExmas[gi]+1

19                                      переход на шаг14

20ИНАЧЕ

21date = getPossibleDate(gi)

22ЕСЛИdate == null

23ТОaddExamToQ(ej,Qallnappt)

24ИНАЧЕ

25ЕСЛИfindConf(dategej) ==false

26ТО

27setRDExam(dategej)

28countApptExmas[gi] +1

29removeExamFromQ(ej,Qjpgi)

30ИНАЧЕ

31date =getNextDate()

32ЕСЛИdate == null

33ТО

34jProgress+1

35                                                                    переходим на шаг 12

36ИНАЧЕ переход на шаг25

37ВСЕ ЕСЛИ

38ВСЕЕСЛИ

39ВСЕ ЕСЛИ

40ВСЕ ЕСЛИ

41ВСЕ ЦИКЛ ПОКА

42ВСЕ ЕСЛИ

43ВСЕ Если

44ВСЕ Цикл

Минимизация целевой функции(16)реализуется с помощью генетического алгоритма, основанного на механизмах естественного отбора и наследования[8].

Будем рассматривать расписание экзаменационной сессии как некоторое однозначное отображениеES из множества экзаменовE во множествоDtm × R(декартово произведение временных интервалов и аудиторий):

ES :EDtm×R.

Табличное представление данного отображения представлено в таблице 2.

Таблица . Табличное представление отображенияES

date

tm

r1

r2

...

...

rnr

d1

1

e1

e2

...

...

el