Алгоритм генерації розкладів занять для закладів вищої освіти



У данiй статi запропонований алгоритм генерацiї розкладiв для ЗВО. Матерiал в статi враховує необхiднiсть перегенерування розкладiв на основi оцiнки з вагових коефiцiєнтiв та пропонує алгоритм табуйованого локального пошуку альтернативних розкладiв для побудови нових розкладiв на основi початкового з метою покращення оцiнки якостi розкладу. Вводиться поняття якостi розкладу i метод оцiнки якостi розкладу виходячи з явних вагових коефiцiєнтiв.

Ключовi слова–алгоритм генерацiї розкладiв, табуйований локальний пошук, NP-повна задача, iндивiдуальний розклад студента, оптимiзацiя згенерованого розкладу, якiсть згенерованого розкладу, свобода розташування заняття у розкладi.

Вступ

Функцiонування закладiв вищої освiти сильно залежить вiд ритму навчання, закладеного в органiзацiйних документах закладiв. Одним з основних документiв, що регулює ритм навчання та вносить яснiсть в принципи функцiонування розкладу для студентiв i викладачiв. Утiм, задача складання розкладiв не є простою, оскiльки для кожного закладу iснує ряд обмежень, якi необхiдно врахувати при побудовi оптимального розкладу. Таких обмежень може бути дуже багато, i це одна з причин, чому задачi складання розкладiв присвоюють NP-повний рiвень складностi. Варiанти вирiшення задачi складання розкладу включають як повний перебiр варiантiв, що базуються на обмеженнях, так i рiзнi оптимiзацiї на основi генетичних алгоритмiв та iнших видiв алгоритмiв, якi допомагають знизити кiлькiсть варiантiв, якi необхiдно перевiрити для побудови оптимального розкладу. Дана стаття пропонує лiнiйний алгоритм генерацiї першого розкладу, який буде задовольняти мiнiмальному рiвню обмежень, а також алгоритм перегенерування розкладу, що буде знаходити бiльш оптимальнi з точки зору обмежень рiшення шляхом використання алгоритму табуйованого локального пошуку.

Алгоритм генерацiї розкладiв занять

Оцiнюючи свободи розташування i-го заняття розкладi проводиться пiдрахунок:

  • кiлькостi аудиторiй $a_{i}$, якi пiдходять для проведення заняття, на пiдставi вимог заняття до обладнання аудиторiї та кiлькостi робочих мiсць;
  • кiлькостi занять на тиждень $p_{i}$, якi проводить викладач цього заняття;
  • кiлькостi занять на тиждень $g_{i}$ для заданого студента (не рекомендується розглядати групу студентiв, оскiльки наразi iснує практика дисциплiн на вибiр).

На підставі цих даних визначається оцінка свободи розташування заняття у розкладі: \[S_{i}=\frac{a_{i}}{g_{i} \cdot p_{i}},\] де $S_{i}$ – оцінка свободи розташування $i$-го заняття у розкладі;

$n$ – кількість занять.

Після оцінювання свободи розташування занять у розкладі проводиться сортування списку занять щодо зростання їх оцінок свободи розташування: \[S_{i}

Алгоритм перегенерування розкладів

Нехай є $n$ критеріїв для оцінки розкладу, кожен з яких може бути числом в діапазоні [0;1]. Тоді на їх основі можна оцінити якість розкладу, застосувавши наступні розрахунки: \[R_{il}=\sum_{j=1}^{m}w_{j}k_{jl},\] де $R_{il}$ -- якість розташування $i$-го заняття на $l$-й позиції у розкладі;

$k_{jl}$ –- значення, отримане за $j$-м критерієм оцінки якості розташування заняття на $l$-й позиції у розкладі;

$w_{j}$ -- ваговий коефіцієнт $j$-го критерію оцінки якості;

$m$ -– кількість критеріїв оцінки якості.

Після оцінки якості всіх можливих варіантів розташування заняття у розкладі вибирається варіант, при якому досягається максимальне значення оцінки \[R_{i}=\max_{l}(R_{il}), l=1..h,\] де $l$ -- можлива позиція $i$-го заняття в розкладі;

$R_{i}$ -- якість розташування $i$-го заняття у розкладі;

$h$-- кількість можливих варіантів розташування заняття у розкладі.

Після розміщення всіх занять у розкладі проводиться оцінка якості складеного розкладу. Для оцінки якості розкладу вирішено використати суму оцінок якості розташування всіх занять у розкладі. З огляду на те, що оцінка якості розташування кожного заняття за критеріями появи та зникнення вікна у розкладах студентів та викладачів залежить від взаємного розташування занять у розкладі – необхідно провести повторну оцінку якості розташування кожного заняття у складеному розкладі. Для оцінки якості складеного розкладу використовується формула: \begin{eqnarray} R=\sum_{i=1}^{n}R_{i}. \end{eqnarray}

На основі отриманих оцінок можна оптимізувати розклад, застосувавши алгоритм табуйованого локального пошуку.

Шляхом застосування незначних змін (як-от перестановка двох сусідніх занять з мінімальною різницею ступеня свободи $S_{i}-S_{j}$) можна отримати набір розкладів, що є «сусідніми рішеннями» для даної задачі. Для кожного з цих розкладів визначається $R$ за (1) і найкращий запам’ятовується. З метою запобігання зациклювання алгоритму на локальних мінімумах, коли усі сусідні рішення схожі і є гіршими за поточне оптимальне, застосовується табуювання – рішення, що були відхилені як неоптимальні запам’ятовуються і не застосовуються в подальших ітераціях.

Алгоритм табуйованого локального пошуку ітеративший, тож знайшовши рішення з кращим $R$, до нього можна застосувати наступну ітерацію пошуку і шукати більш оптимальне рішення серед сусідів поточного.

Висновки

Отже, для подальшої оптимізації розкладу, що генерується лінійним алгоритмом можна застосувати табуйований локальний пошук і отримати оптимізоване за обмеженнями рішення, яке буде більш ефективним з точки зору обмежень.

Такий спосіб перегенерування розкладів можна застосувати після додавання нових обмежень до системи, щоб вихідний розклад змінився не надто сильно (що гарантується локальним пошуком, оскільки зміни, які пропонуються для сусідніх рішень є мінімальними перестановками занять, а не повним пересортуванням розкладу).

Алгоритмічне рішення, що було описано у тексті статі може бути застосовано в системах генерації розкладів, оскільки вирішує основні проблеми, що виникають при розробці цього типу систем, а саме: генерування розкладу і перегенерування розкладу з мінімальними змінами за виникнення додаткових умов, за якими розклад необхідно оптимізувати.

Дане алгоритмічне рішення буде застосовано як один із способів генерування і перегенерування розкладів у системі генерації розкладів занять для ЗВО, де для нього буде додано графічний інтерфейс з можливістю генерувати та перегенерувати розклад, а також опублікувати отриманий розклад і надати студентам можливість отриманий розклад переглянути.

Також, дане алгоритмічне рішення можна застосувати в рамках будь-яких закладів освіти, у тому числі середньої у ручному і автоматичному форматі для побудови розкладів, що будуть використовуватися у якості розкладів занять у відповідному закладі.

Лiтература

[1] Берегових Ю. В. Алгоритм составления расписания занятий / Ю. В. Берегових, Б. А. Васильєв, М. О. Володiн. // Искусственный интеллект. – 2009. – №2. – С. 50–56.

[2] Галузин К. С. Математическая модель оптимального учебного расписания с учетом нечетких предпочтений : автореф. дис. на здобуття наук. ступеня канд. фiз.-мат. наук / Галузин Константин Станиславович – Пермь, 2004. – 18 с.

[3] Fred G. Future Paths for Integer Programming and Links to Artificial Intelligence / Glover Fred. //Computers and Operations Research. – 1986. – №5. – С. 533–549.

[4] Serial and parallel search techniques for the traveling salesman problem / M.Malek, M. Huruswamy, H. Owens, M. Pandya. // Annals of OR: Linkages with Artificial Intelligence. – 1989. – С. 75–101.

Dec 2, 2021