Вгору
Русский   English
ДонНТУ   Портал магістрів

Реферат

Зміст

Вступ

Однією з найважливіших проблем якісної організації навчального процесу у вищому навчальному закладі є завдання формування якісного навчального розкладу. Це завдання є основною в діяльності диспетчерської служби ВНЗ. Якісно складений розклад повинен забезпечити рівномірне завантаження студентських груп і професорсько-викладацького складу, воно впливає на комфортність навчання студентів, творчу віддачу викладачів і ефективність використання ресурсів аудиторного фонду і лабораторій [1].

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

Зокрема необхідно враховувати, чинні санітарно-епідеміологічні правила і норми (СанПіН), розподіл студентських груп на підгрупи, наявність викладачів-сумісників і багато іншого. При складанні розкладу диспетчеру необхідно враховувати вимоги щодо організації навчального процесу, вказівки адміністрації з розподілу аудиторного фонду (і інших ресурсів, необхідних для реалізації навчального процесу), а також особисті побажання викладачів і студентських груп до складання розкладу. Крім цього, специфіка конкретного ВНЗ відбивається в завданню складання розкладу у вигляді специфічних цілей і обмежень. В результаті всього вищевикладеного, завдання складання розкладу стає дуже складним завданням для вирішення вручну. В даний час при актуальності питання якості освітніх послуг і вимог економії ресурсів на практиці затребуване не тільки складання деякого чорнового варіанту розкладу, а й отримання оптимального (для заданих критеріїв при обліку обмежень) або близького до оптимального розкладу. І якщо складання розкладу вручну є важкою і витратним за часом завданням, то вирішення задачі оптимізації навчального розкладу вручну на практиці майже не проводиться [2].

2. Актуальність

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

  1. якість навчання;
  2. економічна ефективність навчання;
  3. комфортність навчання студентів та роботи професорсько-викладацького складу;
  4. проведення навчального процесу без збоїв, і уникнення необхідності коригування розкладу після початку навчального семестру [3].

Автоматизація процедури складання навчальних занять дозволяє:

  1. врахувати всі вимоги, що пред'являються до розкладу;
  2. визначити критерії для оцінки ефективності та оптимізації розкладу;
  3. зменшити часові витрати на складання розкладу, що особливо важливо при необхідності швидко отримати розклад після зміни зовнішніх умов;
  4. дозволить врахувати побажання викладачів, щодо часу проведення занять і забезпечить можливість роботи за сумісництвом.

Завдання теорії розкладів мають не тільки важливе теоретичне значення, бо відноситься до класу NP-повних задач, але і набули широкого практичного поширення. Для знаходження оптимального рішення такого класу задач необхідно провести повний перебір всіх можливих варіантів, що не завжди можливо зробити на увазі обмеженості ресурсів. Побудова оптимального плану розподілу занять може зайняти занадто багато часу і ресурсів, при використанні точних методів рішення, в даному випадку – повний перебір варіантів, що при збільшенні розмірності задачі призводить до логарифмічного зростання витрачених ресурсів для знаходження рішення. Виникає необхідність в методах, що характеризуються поєднанням поліноміальної залежності часу розрахунку від розмірності задачі і точністю близькою до оптимальної [4].

До такого класу методів відносяться еволюційно-генетичні алгоритми , які є на сьогоднішній момент найбільш гнучкими і ефективними з усіх відомих наближених алгоритмів [1].

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

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

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

2. Цілі і завдання роботи

Основною метою роботи є складання алгоритму здатного генерувати ефективне розклад занять в умовах ДонНТУ.

Для досягнення поставленої мети необхідно вирішити такі завдання:

  1. визначити інтелектуальний метод, для складання коректного розкладу;
  2. модифікувати алгоритм для підвищення його ефективності;
  3. перевірити ефективності отриманого алгоритму;
  4. вивчити вплив різних параметрів алгоритму на швидкість і результат рішення задачі;
  5. визначити ефективні значення параметрів для вирішення завдання;
  6. спроектувати базу даних для уніфікації алгоритму.

3. Наукова новизна і практична цінність

Пропонується створення модифікованого генетичного алгоритму (структури і проблемно орієнтованих операторів), адаптованого для вирішення спеціалізованого завдання отримання близьких до оптимальних розкладів занять у вищому навчальному закладі.

Складання цільової функції, з можливістю враховувати як вимоги, так і переваги пред'являються до розкладу.

4. Огляд існуючих підсистем

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

Основними системами, що дозволяють автоматично складати розклад є такі програмні продукти:

  1. Програма 1С: Автоматизоване складання розкладів. Університет;
  2. Програма Ректор-ВНЗ;
  3. Програма Галактика.

Порівняння функціональних можливостей обраних підсистем наведені в таблиці 1.1 [6,7,8,9].

Таблиця 1.1 – Порівняння функціональних можливостей підсистем

Функція 1С Ректор–ВНЗ Галактика
режими складання розкладу ручний, автоматичний, змішаний ручний, автоматичний, змішаний ручний, автоматичний, змішаний
можливість складання кількох варіантів розкладу в автомат. режимі і вибір кращого так ні ні
врахування побажань і можливостей викладачів, груп студентів, приміщень так ні так
консолідація розкладів так ні ні
вибір критеріїв оптимізації так так так
можливість складання довільних розкладів так невідомо так
врахування максимально допустимої кількості занять на день для групи студентів, або викладача при складанні розкладу так тільки кількість пар на день так
побудова розкладу для 2-х і більше змін так так так
оперативне резервування приміщень так ні так
перегляд розкладів по web-інтерфейсу так ні так
завантаження довідників в форматах excel, xml немає excel, xml
оперативна зміна розкладів так, (шляхом перетягування) занять на шахматці невідомо невідомо
складання розкладу сесії так ні невідомо
пріоритетність використання ресурсів невідомо ні так
врахування паралельних занять, розбиття на підгрупи потокових лекцій при складанні розкладу так ні невідомо
дотримання інтервалу між певними заняттями невідомо ні так
розмежування прав доступу так ні ні

Системні вимоги підсистем:

  1. 1с СУБД – MS SQL, IBM DB2, Oracle Database, ОС Windows, Linux, Mac OS, iOS [7];
  2. Ректор вузу ОС Windows XP, Windows Vista або Windows 7, СУБД не потрібно [8];
  3. Галактика ОС Windows (XP, 7), NET Framework v.4 і вище СУБД MS Server 2008, Server 2003 [9].

Програма Ректор вузу є найпростішою, вона погано масштабується, не використовує СУБД, що вельми погано позначається на веденні довідкової інформації, абсолютно не пристосована для взаємодії з іншими підсистемами, має малу кількість налаштувань для складання розкладу в автоматичному режимі. З вище сказаного можна зробити висновок, що дана програма не здатна автоматично сформувати розклад з урахуванням всіх обмежень, при цьому вихідний код є закритим і самостійне внесення змін, або доповнень неможливе. Програма є платною і поширюється по ліцензії. Ліцензія на 1 комп'ютер – 8.000.00 руб [8].

Програма 1С: Автоматизоване складання розкладів. Університет програмний продукт, що добре масштабується, має можливість відображення в системі великої кількості обмежень, вимог. При цьому система має вбудовану систему інтеграції з 1С: Університет і 1С: Університет ПРОФ. Продукт реалізує функціонал складання розкладу в автоматизованому режимі, на додаток до ручного режиму, наявного в 1С: Університет ПРОФ. При цьому 1С: Автоматизоване складання розкладів. Університет може працювати і як самостійний продукт, що забезпечує взаємодію всіх підрозділів ВНЗ і об'єднує їх в одну систему управління вузом. При цьому всі компоненти системи можуть працювати на комп'ютерах як під управлінням Windows, так і під управлінням Linux 1С: Підприємства 8.2, а з появою Веб-клієнта для користувачів з'явилася можливість працювати з системою через браузери Microsoft Internet Explorer або Mozilla Firefox. До недоліків даної системи можна віднести її вартість 1С: Підприємство 8.2 ліцензія на сервер – 13 200.00 гривень, 1С: Автоматизоване складання розкладу. Університет – 70.000.00 руб., Ліцензії на робочі місця 1–місце – 1 800.00 грн [10].

5. Методи вирішення завдань складання розкладу [11]

  1. Методи цілочисленого програмування

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

    Застосування алгоритму:

    1. виділення змінних;
    2. складання математичної моделі (виділення обмежень для змінних);
    3. складання цільової функції;
    4. знаходження максимуму (мінімуму) цільової функції за допомогою математичних методів.

    Основні недоліки:

    1. експоненціальне збільшення витрат часу на пошук кращого (прийнятного) рішення з ростом розмірності розв'язуваної задачі;
    2. відсутність гарантії отримання прийнятного рішення;
    3. в силу великої розмірності математичної моделі складно оцінити вплив різних чинників процес вирішення завдання і його результат;
    4. складність врахування переваг.

  2. Метод теорії графів

    В цьому випадку будується неорієнтовані граф, в якому кожна вершина являє собою заплановане навчальним планом заняття. Якщо між якимись двома вершинами можливі конфлікти, то вони з'єднуються ребром. Це еквівалентно забороні одночасного проведення занять. Тоді задача зводиться до розфарбуванні графа в задану кількість кольорів.

    Застосування алгоритму:

    1. виділення безлічі занять в навчальному плані;
    2. уявлення кожного заняття у вигляді вершини графа;
    3. з'єднання вершин графа ребрами в разі неможливості одночасного проведення занять;
    4. рішення задачі розмальовки графа в задану кількість кольорів.

    Недоліки:

    1. мала ефективність при застосуванні точних методів для розмальовки графів великої розмірності;
    2. відсутність можливості обліку переваг.

    Переваги:

    1. проста в розумінні математичної модель;
    2. застосування графа разом з наближеними методами може дати хороші результати.

  3. Агентний підхід

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

    Застосування алгоритму:

    1. розбиття глобальної задачі на більш дрібні під завдання;
    2. для кожного виду під завдання реалізується особливий вид агентів;
    3. складання моделі простору, в якому діють агенти у вигляді правил і аксіом;
    4. складання онтології понять;
    5. заміщення всіх користувачів розкладу агентами, метою кожного знайти оптимальне (для себе) розклад.

    Недоліки:

    1. відсутня гарантія отримання прийнятного рішення задачі побудови розкладу занять (на тестах змагання itc 2007 мульти–агентна система не знайшла жодного допустимого розкладу);
    2. практично неможливим стає оцінка впливу значень параметрів для внутрішньої логіки кожного з агентів на результат рішення задачі.

    Переваги:

    1. можливість гнучкого налаштування індивідуальних переваг за рахунок можливості реалізації власної логіки для кожного з агентів;
    2. можливість динамічного зміни уподобань.

  4. Метод мурашиної колонії

    Заснований на здатності мурах знаходити найкоротші шляхи до їжі за допомогою виділення феромону.

    Застосування алгоритму:

    1. подати завдання у вигляді зваженого графа;
    2. визначити значення сліду феромону;
    3. визначити евристику поведінки мурашки при побудові рішення;
    4. реалізувати локальний пошук.

    Недоліки:

    1. збіжність алгоритму гарантується, але час збіжності не визначений;
    2. висока ітеративна алгоритму;
    3. результат роботи методу залежить від початкових параметрів пошуку, які підбираються експериментально;
    4. теоретичний аналіз значення початкових параметрів ускладнений, дослідження є більше експериментальними.

    Переваги:

    1. може використовуватися в динамічних додатках;
    2. використовує пам'ять усієї колонії, що досягається за рахунок моделювання виділення феромонів;
    3. збіжність до оптимального рішення гарантується.

  5. Метод імітації відпалу

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

    Застосування алгоритму:

    1. скласти коректне розклад і задати високе значення температури T = T0;
    2. змінити розклад Z = Z';
    3. обчислити цільову функцію для зміненого розкладу Δ = f(Z') – f(Z);
    4. замінити попереднє розклад отриманим, якщо воно є кращим за попередній (Δ ≤ 0), якщо немає, то ймовірність заміни p = e–Δf/T;
    5. знизити температуру;
    6. доки не виконаний критерій зупинки перехід до пункту 2.

    Недоліки:

    1. мало ефективний для складання розкладів у сучасних системах масового освіти на увазі великої розмірності задачі;
    2. для отримання ефективного вирішення необхідно застосовувати схему Больцмана, або Коши що призводить до значних витрат обчислювальних потужностей.

  6. Генетичний алгоритм

    Генетичні алгоритми засновані на використанні механізмів теорії природної еволюції.

    Застосування алгоритму:

    1. згенерувати випадковим чином популяцію розміру P;
    2. обчислити цільову функцію;
    3. виконати операцію репродукції;
    4. виконати операцію схрещування (рис. 1);
    5. виконати операцію мутації;
    6. виконати оператор редукції;
    7. перевірить критерій зупинки і, якщо він не досягнуть, перейти до кроку 2, інакше завершити роботу.
    Операція схрещування

    Рисунок 1 - Операція схрещування

    (анімація: обсяг - 81 876 байт; розмір - 554х216 пікселів; складається з 5 кадрів; затримка між кадрами - 120 мс)

    Недоліки:

    1. якість рішення значним чином залежить від розміру і різноманітності початкової популяції;
    2. рішення, отримані в результаті декількох експериментів для однієї і тієї ж задачі, можуть незначно відрізнятися;
    3. слабке врахування специфіки завдання складання розкладу навчальних занять.

    Переваги:

    1. алгоритм працює з кодами, в яких представлений набір параметрів, що прямо залежать від аргументів цільової функції;
    2. в процесі пошуку алгоритм використовує кілька точок пошукового простору, а не переходить від точки до точки;
    3. в процесі роботи алгоритм може не використовувати ніякої додаткової інформації про завдання, але, якщо така є можна прискорити збіжність алгоритму;
    4. генетичний алгоритм використовує як імовірнісні правила для породження нових точок пошуку, так і детерміновані для переходу від одних точок до інших;
    5. для задач високої розмірності швидкість роботи алгоритму можна регулювати розмірами популяції.

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

6. Математична постановка задачі

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

S (P,G,A,T,D,V),
Де G – безліч навчаються груп;
A – безліч аудиторій;
D – безліч дисциплін;
P – безліч викладачів;
T – безліч навчальних пар (тимчасових інтервалів проведення занять);
V – робочі навчальні плани тривимірна матриця, яка визначає для кожного заняття які викладачі його проводять, і які групи на ньому присутні.

Якщо спростити завдання і не розглядати навчальні плани і дисципліни, то розклад можна представити у вигляді декартового добутку

S=G×P×A×T→{0,1},
де G безліч учнів груп;
A – безліч аудиторій;
P – безліч викладачів;
T – безліч навчальних пар (тимчасових інтервалів проведення занять).

Цей вираз розшифровується так, якщо в певний час Т викладач Р у групи G проводить заняття в аудиторії А, то значення виразу дорівнює 1, інакше 0.

Цільова функція Р є сумою штрафів за порушення переваг при складанні розкладу.

Цільова функція P, (1)


де NW – кількість вимог;
W – список штрафних коефіцієнтів довжиною NW, який відповідає вимогам;
N – кількість занять в розкладі (кількість генів в хромосомі);
Z – список занять довжиною N;
zir – список з булевих довжиною NW значень, де кожному значенню відповідає вимога і штрафний коефіцієнт зі списку W.

У більшості навчальних закладів основними обмеженнями до розкладу є:

  1. відсутність накладок в розкладі викладача груп і аудиторій;
  2. відповідність аудиторії вимогам для проведення заняття;
  3. обмеження кількості занять на тиждень для викладача і групи.

7. Очікувані результати

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

8. Висновки

Зроблено аналіз існуючих методів, моделей і алгоритмів, що дозволяють складати ефективне розклад занять у ВНЗ, були виявлені їх переваги та недоліки.

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

Визначено критерії ефективності розкладу в умовах ДонНТУ.

Проведені експериментальні дослідження підтверджують ефективність складених розкладів, а також визначені параметри, що дозволяють підвищити ефективність алгоритму.

На підставі результатів експериментальних досліджень сформульовано та надано рекомендації щодо складання ефективних розкладів в умовах ДонНТУ.

Список джерел

  1. Буділовський Дмитро Михайлович Оптимізація вирішення завдань теорії розкладів на основі еволюційно–генетичної моделі розподілу завдань // Системний аналіз, управління і обробка інформації (по галузях) // Ростов–на– Дону 2007;
  2. Лопатеева Ольга Миколаївна Система автоматизованого формування навчального розкладу у вищому навчальному закладі на основі евристичних алгоритмів // Системний аналіз, управління і обробка інформації (по галузях) // Дисертаційна робота Красноярськ 2006 ;
  3. Нізамова Гузель Фанісовна Математичне і програмне забезпечення складання розкладу навчальних занять на основі агрегатних генетичних алгоритмів // автореферат // Уфа 2006;
  4. Секірін А. І. Програмний комплекс для моделювання, аналізу та оптимізації роботи автоматизованих технологічних комплексів обробки // Наукові праці Донецького національного технічного університету. Серія: Обчислювальна техніка та автоматизація. Випуск 90 – Донецьк: ДонНТУ, 2005;
  5. Конькова І.С. Генетичні алгоритми в рішенні завдання со–дання розкладу занитій в вузі. // Проблеми інформатики в освіті, управлінні, економіці і техніці: Зб. статей XII Міжнар. Науково–техн. Конф. – Пенза: ПДЗ, 2012. – С. 26 29;
  6. Про випуск програмного продукту 1С: Автоматизоване складання розкладів. Університет [Електронний ресурс]. – Режим доступу: http://www.1c.ru/news/info.jsp?id=18039 – Загл. з екрану;
  7. 1С: Автоматизоване складання розкладу. Університет, [Електронний ресурс]. – Режим доступу: http://solutions.1c.ru/asp_univer – Загл. з екрану;
  8. Програма Ректор–ВНЗ [Електронний ресурс]. – Режим доступу: http://rector.spb.ru/raspisanie–vuz–4u.php – Загл. з екрану;
  9. Програма: Галактика [Електронний ресурс]. – Режим доступу: http://www.galaktika.ru/ruz – Загл. з екрану;
  10. Прайс–Лист 1С [Електронний ресурс]. – Режим доступу: http://www.bgs–solutions.com.ua/prices/price.php – Загл. з екрану;
  11. М.О. Безуглий, О.І. Секірін, доц. каф. АСУ. Методи підвищення ефективності складання розкладу в умовах навчального закладу. // Міжнародна науково–технічна конференція студентів, аспірантів та молодих вчених "Комп'ютерна та програмна інженерія ––2015" // Донецький національний технічний університет 2015.