Ви є тут

Модель та методи формалізації процесу формування розкладу навчальних занять

Автор: 
Сафонова Ганна Феліксівна
Тип роботи: 
Дис. канд. наук
Рік: 
2009
Артикул:
3409U000619
129 грн
Додати в кошик

Вміст

змістом або логічним взаємозв'язком. []2.Планування занять за складними дисциплінами на дні в середині тижня. Складність дисципліни - поняття невизначене, яке важко піддається формалізації.[]2.Рівномірний розподіл протягом тижня складних і змістовних видів роботи.Вимога суперечлива за тими ж причинами, що і попередня. 2.Вимоги, пов'язані з врахуванням наукової, адміністративної або іншої діяльності викладачів, тобто врахування індивідуальних побажань викладачів.При ФРЗ інтереси студентів потрібно вважати більш пріоритетними в порівнянні з інтересами викладачів, якщо вони суперечать один одному. []2.Максимізація навантаження аудиторій.Максимізація навантаження частини аудиторій дозволить більш ефективно використовувати існуючий аудиторний фонд, завдяки вивільнення інших аудиторій, які можуть бути використанні для проведення спеціалізованих або позааудиторних занять. [] Продовж. табл. 1.
№Вимоги та обмеженняХарактеристикаДжерело2.Планування занять в першу чергу в аудиторіях, які закріплені за кафедрами, факультетами, до яких відноситься спеціальність даної академічної групи.Забезпечує певну свободу локального корегування розкладу в межах кафедри, факультету, спеціальності, тощо.[]2.Мінімізація "вікон" у розкладі викладачів.Критерій суперечливий, оскільки індивідуальний план викладача повинен формуватися з врахуванням його особливостей. []
Таким чином, однією з головних проблем позитивного розв'язання задачі ФРЗ є необхідність врахування усіх вимог та обмежень до РНЗ, за умови, що деякі з них можуть бути суперечливими (наприклад, врахування побажань викладачів може стати причиною нерівномірного розподілу занять), тобто задача ФРЗ є багатокритеріальною.
Складність формалізації частини вимог та обмежень, особливо бажаних, зумовлює ще одну проблему розв'язання задачі ФРЗ - проблему апріорної невизначеності [].
Велика кількість вхідних даних призводить до проблеми розмірності задачі, це пов'язано з тим, що майже у всіх формалізаціях вона є NP-повною [].
Проблема динаміки розкладу пов'язана з тим, що ЖЦ задачі ФРЗ не закінчується з початком використання розкладу. Вхідні дані задачі протягом навчального семестру припускаються постійним змінам (наприклад, планові, вимушені заміни викладачів), які потребують формування не абсолютно нового розкладу, а лише довизначення існуючого (рис. 1.).
Рис. 1.1. Схема життєвого циклу задачі ФРЗ.
Тобто, враховуючи особливості ЖЦ задачі ФРЗ, алгоритм її розв'язання має бути адаптивним, перетворюючись в заданих межах при зміні вхідних даних задачі з метою отримання прийнятного РНЗ.
1.2. Підходи до розв'язання задачі ФРЗ
На практиці в більшості навчальних закладів використовується технологія ФРЗ "вручну", яка містить збирання і класифікацію початкової інформації, складання допоміжних таблиць, безпосередньо формування розкладу, його перевірку і корегування []. При такій технології дуже важко одержати розклад, який би враховував всі особливості навчального закладу. Цей процес є довготривалим і потребує максимальної зосередженості та великої кількості людських ресурсів, адже людині, яка зайнята цією справою, необхідно враховувати значну кількість інформації. Тому усунути усі недоліки розкладу, створеного таким чином, фактично неможливо, а будь-яке корегування або зміна призводять до труднощів, пов'язаних зі створенням паперових варіантів розкладу.
Автоматизація процесів ФРЗ може значно полегшити планування навчального процесу [ - ]. Це пов'язано не тільки з можливістю реалізації функції автоматичного розподілу занять на початку семестру, на якій використання створеної автоматизованої системи ФРЗ і закінчується. Розклад у даному випадку є інструментом організації навчального процесу, і для більш повного його використання необхідно, щоб автоматизована система поєднувала в собі не тільки засоби для формування якісного розкладу, але й засоби для підтримки його якості у випадку зміни деяких вхідних даних, які на момент складання розкладу вважалися постійними. Така ситуація є звичайною для розкладу занять ВНЗ, в якому впроваджено КМСОНП. Це пов'язано з тим, що РНЗ вже не повторюється циклічно кожні два тижні протягом семестру, бо заміна змістовного модуля дисципліни може відбуватися неодноразово протягом семестру, що автоматично зумовлює і зміну РНЗ. Таким чином така автоматизована система, у разі планової заміни змістовного модулю, буде дискретно змінювати свій поточний стан.
Не зважаючи на усі переваги, пов'язані зі зручністю отримання РНЗ, автоматизація процесу ФРЗ загострює усі виявлені проблеми задачі ФРЗ, що пов'язано з необхідністю знаходження чітких алгоритмів їх вирішення.
1.3. Аналіз автоматизованих методів ФРЗ
В залежності від алгоритму, який використовується для ФРЗ, дану задачу можна сформулювати як задачу пошуку чи задачу оптимізації [ - ]. Для задачі пошуку необхідно знайти розв'язок, який задовольняє всім обмеженням. Метою задачі оптимізації є мінімізація (максимізація) значення цільової функції, яка включає "м'які" (бажані) обмеження при обов'язковому виконанні "жорстких" (обов'язкових) обмежень [ - ]. В [] задача оптимізації реалізується шляхом довизначення цільової функції для задачі пошуку.
Методи розв'язання задачі ФРЗ можна
розділити на детерміновані, евристичні та комбіновані [].
Крім того, відомі підходи, які складають альтернативу даним методам, наприклад, логічне програмування в обмеженнях, апарат нечітких множин, тощо [].
1.3.1. Переваги та недоліки детермінованих методів. Детерміновані методи дають точну оцінку досліджуваному процесу і однозначно визначають функціональні зв'язки між "входами" і "виходами".
Більшість точних методів пошуку використовують модель розкладу у вигляді графа []. Вершини графа відповідають різним заняттям. Заняття, які не можуть проводитися одночасно, тобто є такими, що конфліктують, з'єднуються ребрами графа. Розв'язання задачі ФРЗ полягає у розфарбуванні отриманого графу в мінімальну кількість кольорів, при умові, що кількість вершин, розфарбованих в один колір, не буде перевищувати кількості аудиторій. Розфарбовувавши граф, отримуємо розподіл занять за періодами розкладу, при цьому кожен колір відповідає певному періоду; тобто одержимо набори занять, які можуть бути проведені одночасно.
Доведено, що задача розфарбовування графа є NP-повною [ - ]. Для розв'язання цієї задачі були розроблені ряд методів і підходів [ - ], в яких, у переважній більшості, використовуються "жадні" алгоритми. Проте, завдання знаходження прийнятного РНЗ не зводиться тільки до розфарбовування графа. Зазвичай метод розфарбовування є тільки основою системи складання розкладу, тоді як для задоволення обмежень різних видів потрібне введення додаткових процедур і модифікацій, наприклад, якщо заняття повинно бути проведено в певний період, то відповідний йому вузол додається в граф тільки перед початком розгляду відповідного періоду. Задача закріплення занять за аудиторіями також є складною, особливо при браку останніх [].
Задача ФРЗ за допомогою розфарбування графа може мати поліноміальний час розв'язання тільки при умові неврахування частини додаткових (бажаних) вимог [].
З іншого боку модель РНЗ у вигляді графу не є замкнутою системою, що дозволяє легко здійснити її динаміку при зміні вхідних даних задачі, завдяки додаванню (вилученню) відповідних вершин, ребер графу.
Для врахування найбільш важких вимог застосовуються відомі підходи математичного програмування. Існує декілька варіантів формалізації задачі ФРЗ у термінах лінійного цілочисельного програмування [, , - ]. Для розглянутої в під
розділі 1. постановки задачі маємо наступний варіант []: задані q груп g,., gi., gq; і s викладачів р,., рj., рs. Визначено t періодів планування ,., к,., t і відома кількість аудиторій lк, які доступні протягом кожного періоду k. Задана також невід'ємна цілочисельна матриця R, яка називається матрицею вимог; її елемент rij відповідає кількості занять, які повинен провести викладач рj для групи gi.
Необхідно знайти такі уijк, , які задовольняють наступним обов'язковим умовам:
- для кожної групи повинна бути проведена задана кількість занять:
(1.)
- для кожного періоду в кожній групі може бути проведено не більше одного заняття:
(1.)
- для кожного періоду кожним викладачем може бути проведено не більше одного заняття:
(1.)
- кількість занять для кожного періоду не повинна перевищувати кількості доступних аудиторій:
(1.)
де уijk = , якщо для викладача рj визначене заняття в групі gi на період k, та уik = - в іншому випадку; і мінімізувати значення цільової функції:
(1.)
де dijk - коефіцієнт штрафу за призначення рj викладача в gi групі на період k. Більше значення dijk призначається на періоди, для яких не бажане призначення заняття викладача рj в групі gi.
Більш розповсюджений варіант, коли цільова функція представляє собою суму штрафів за порушення деяких додатково визначених умов, які виражають бажані властивості РНЗ [].
Побудована таким чином модель відображає основні фактори, які враховуються при ФРЗ, і відноситься до класу оптимізаційних задач, розв'язання яких може бути знайдене, наприклад, методом гілок та границь [ - , ].
Розв'язання задачі ФРЗ за допомогою лінійного цілочисельного програмування виявляється малоефективним через наступні причини []:
) відсутня гарантія отримання прийнятного розв'язку через необмеженість ітерацій;
) експоненціальне збільшення часових витрат на пошук оптимального (прийнятного) розв'язку з ростом розмірності задачі;
) практично неможливо (через велику розмірність, громіздкість, складність отриманої математичної моделі) оцінювати вплив на розв'язок задачі бажаних факторів (вимог та обмежень);
) математична модель задачі ФРЗ в термінах цілочисельного програмування представляє замкнуту систему (розмірність множин, які описують об'єкти цілочисельної оптимізації задачі ФРЗ фіксовані), тому вона не враховує можливість динаміки даних задачі.
Теоретичні та емпіричні оцінки складності розв'язання задачі ФРЗ показали, що за допомогою лише точних методів побудувати розклад на реальних даних ВНЗ неможливо. Такі методи можуть розв'язати тільки задачі малої розмірності або без врахування багатьох необхідних вимог [, ]. Виходячи з цього, більшість автоматизованих систем ФРЗ мають за основу евристичні методи.
1.3.2. Використання евристичних методів. Протилежними детермінованим є евристичні методи, які дозволяють знаходити розв'язок задачі за припустимий час [].
Прямі евристичні методи базуються на принципах, що імітують міркування людини при розв'язанні задачі. Розклад складається послідовно: лекція за лекцією. Основою практично всіх прямих евристичних підходів є стратегія розміщення найбільш "конфліктних" лекцій першими, а відмінності виникають у визначенні поняття "конфліктності".
За схемою роботи такі алгоритми можна
розділити на наступні типи:
- так звані, "жадні", які обирають наступні заняття за деяким правилом без подальшого їх перепризначення; ці алгоритми не можуть самостійно вийти з тупикових ситуацій, в яких призначення наступного заняття неможливе [];
- алгоритми неповного перебору з поверненням, які змінюють раніше призначені заняття, якщо на певному кроці призначення наступного заняття неможливе [];
- алгоритми, які шукають можливість призначення наступного заняття та варіанти перепризначення раніше спланованих занять, які конфліктують з наступним; якщо перепризначення одного заняття знайти не вдалося, деякі методи шукають ланцюжки перепризначень раніше спланованих занять [];
- декомпозиційні евристики, які
розділяють первинну задачу на підзадачі меншої розмірності і застосовують до них інші методи або подальші кроки декомпозиції [].
Типовим прикладом прямого евристичного методу є система Schola [], в якій застосовуються наступні три стратегії.
Стратегія А - призначити найбільш "важку" лекцію на період, найбільш бажаний для її планування.
Стратегія В - якщо на період можна запланувати тільки одну лекцію, то вона планується.
Стратегія С - перемістити вже розміщену лекцію на вільний період так, щоб звільнити період для тієї лекції, яку необхідно розмістити в даний момент.
Лекція вважається "важкою", якщо для групи і викладача задана велика величина навантаження і, відповідно, мала кількість вільного часу. Період для неї вважається більш бажаним, якщо кількість інших лекцій, які можна поставити на цей період, найменша. Система спочатку складає розклад, використовуючи стратегії А і В, поки це можливо, а потім застосовує стратегію С.
Основний недолік прямих евристичних методів - ненаправленість, хаотичність процесу пошуку розв'язку, що є причиною виникнення більшості тупикових ситуацій (суперечливості розв'язку), в свою чергу, спроба усунути цей недолік (алгоритми з поверненнями, перепризначеннями) робить розв'язання задачі громіздким та "блукаючим". Тому в такій ситуації складно оцінити якість отримання наближених розв'язків.
До позитивних рис такого підходу можна віднести підтримання можливості динаміки моделі.
Серед багатьох евристичних чисельних методів (методів випадково-направленого пошуку), які застосовуються для автоматизованого ФРЗ найбільш розповсюдженими є пошук з заборонами, метод моделювання "отжигу" та еволюційний метод. Спільним, в таких підходах, є навмисне включення елементу випадковості в алгоритм пошуку, який оснований на принципах моделювання; а також введення критеріїв оптимальності та цільової функції оптимізації замість вимог до розкладу.
Пошук з "заборонами" (метод "табу") відноситься до методів локального пошуку, які базуються на понятті околиці розв'язку, залежного від структури конкретної задачі []. У випадку застосування методу табу для розв'язання задачі ФРЗ пошук починається з початкового розкладу sinit, або з розкладу, який генерується випадковим чином, або отриманий за допомогою будь-якого іншого методу (наприклад, розклад, складений "вручну"). У циклі досліджується деяка підмножина V околиці поточного розв'язку (розкладу) s. З неї вибирається новий розклад s' з найкращим значенням цільової функції f(s'), незалежно від того, кращий він або гірший, ніж поточний розв'язок.
Підчас вибору нового розкладу з околиці поточного використовується два типи ходів. Одинарний хід полягає в перестановці у розкладі викладача рj двох занять для випадково вибраних періодів t і t або переміщенні тільки одного заняття, якщо один з періодів вільний. Описаний хід задається трійкою (pj, t, t). Передбачається, що t > t2. Такі ходи часто приводять до виникнення конфліктів в розкладі викладача. Тому розглядаються також подвійні ходи, які складаються з пари одинарних, де другий хід ліквідує конфлікт або один з конфліктів, який виник в першому ході занять. Якщо ж в першому ході конфліктів не виникає, то в другому їх також не повинно бути.
Для запобігання зациклення, ходи, зроблені для створення останніх k прийнятих розкладів, заносяться в, так званий, список