Математичний опис керованого виробничого або організаційного технологічного процесу, в якому визначено безліч допустимих управлінь (розкладів) цього процесу, можна розуміти як математичну модель теорії розкладів.
Під математичною моделлю теорії розкладів розуміється математичний опис деякого керованого виробничого, організаційно-технологічного процесу, в якому визначено безліч допустимих управлінь (розкладів) цього процесу. Тривалість в часі деякого дискретного процесу є критерієм оптимальності для задач теорії розкладів. Завданням оптимізації теорії розкладів в основному є мінімізація часу виконання даного процесу. Прикладом завдань теорії розкладів є завдання календарного і мережевого планування [1, 2].
Завдання складання розкладу вузу складається з двох підзадач: складання розкладу занять та складання розкладу іспитів. Це завдання відіграє особливу роль в управлінні організаційно-технологічним процесом установи з лінійно-штабної (з тимчасово-цільовими компонентами) моделлю організаційної структури управління. Вищі навчальні заклади, безумовно, належать до даного типу установ [3-5].
У найбільш загальному формулюванні завдання складання розкладу полягає в наступному: за допомогою деякого безлічі ресурсів або обслуговуючих пристроїв повинні бути розподілені тимчасові ресурси таким чином щоб була виконана деяка фіксована система завдань. Мета полягає в тому, щоб при заданих властивостях завдань та ресурсів і накладених на них обмеження знайти ефективний алгоритм упорядкування завдань в часі, що оптимізує або прагне оптимізувати необхідну міру ефективності вирішення поставленого завдання. В якості основних заходів ефективності є довжина розкладу і середній час перебування завдань в системі. Модель цього завдання є детермінованою в тому сенсі, що вся інформація, на основі якої приймаються рішення про впорядкування, відома заздалегідь.
Загальна теорія розкладів припускає, що всі обслуговуючі пристрої (або процесори) не можуть виконувати в даний момент часу більше одного завдання. Так, наприклад, якщо в якості процесора при розподілі завдань взяти навчальну аудиторію, то під час, коли аудиторія зайнята однієї з груп (неважливо, чи проходить там навчальне заняття або здається іспит), вона не може використовуватися іншою групою.
Тому при перенесенні загальної теорії розкладів на розклад екзаменаційної сесії необхідно зробити наступні обмеження:
- як безлічі завдань для розподілу виступають безлічі навчальних груп та їх іспитів;
- всі іспити повинні бути проведені в період часу, визначеного для екзаменаційної сесії;
- для проведення іспиту повинні виділятися аудиторії з необхідним для здачі даного предмета обладнанням;
- для підготовки до кожного з іспитів повинно виділятися не менше 3 вільних днів;
- у викладача не повинно бути занять з іншими групами на час проведення іспиту;
- аудиторії повинні бути вільні від занять інших груп під час проведення іспиту;
- завдання мають належність до об'єктів, в якості яких виступають навчальні аудиторії та викладачі.
В результаті формулювання задачі складання розкладу екзаменаційної сесії звучить наступним чином. Для заданого набору навчальних груп, їх іспитів і заданого тимчасового інтервалу (період екзаменаційної сесії) необхідно побудувати такий розподіл всіх об'єктів (викладачі та аудиторії) в часі, при якому будуть враховані всі вимоги та обмеження, що пред'являються до розкладу екзаменаційної сесії.
Складання розкладу відноситься до завдань цілочисельного програмування, складність вирішення яких зростає експоненціально з ростом числа і можливих значень варійованих змінних (такі завдання ставляться до класу NP-важких задач). Крім того, для неї характерна наявність великого обсягу різної за своїм складом вихідної інформації і великої кількості важко формалізованих вимог. Зазначені складності перешкоджають автоматизації процедури складання розкладу, незважаючи на наявність широкого спектра методів цілочисельного програмування.
Однак існування вдало складених розкладів говорить про те, що завдання складання оптимального розкладу можна вирішити, чи хоча б про те, що для неї існують допустимі рішення.
Для складання розкладу використовуються наступні методи [6]:
- точні (класичні) методи і алгоритми цілочисельного програмування;
- метод імітації відпалу;
- метод розмальовки графів;
- логічне програмування в обмеженнях;
- евристичні методи, в тому числі засновані на генетичних алгоритмах;
За допомогою даних методів можливе отримання точної математичної моделі, що відповідає всім обмеженням, але в силу NP-складного характеру завдання складання розкладу ця модель буде громіздкою і складною. Щоб уникнути цього, застосовується імітаційне моделювання. У цьому випадку алгоритм оперує безпосередньо розкладом і списком занять, які необхідно включити в розклад (навчальним планом). Тоді алгоритм формування розкладу іспитів є ітераційним. Процес пошуку в ньому представляє рух від одного несуперечливого (що не містить конфліктів) розкладу до іншого в напрямку поліпшення його якості. Вихідна точка пошуку - початкова (опорна) розклад, результат - розклад, якість якого поліпшити не можна або коли виконається фіксована кількість ітерацій.
При реалізації алгоритму, заснованого на принципах імітаційного моделювання, особлива увага приділяється розробці евристичних правил вибору чергового заняття зі списку, визначення найкращої для нього позиції в розкладі та оцінці одержуваного розкладу.
До позитивних рис такого підходу можна віднести можливість детального врахування специфіки розв'язуваної задачі в разі складання розкладу для конкретного вузу. Однак при цьому сильно обмежується можливість застосування розробленої системи в інших навчальних закладах. Крім того, очевидно, знадобиться вносити істотні зміни в алгоритм при незначних внутрішніх змінах у вузі.
Однак, так як алгоритм заснований на діях, що здійснюються диспетчером при складанні розкладу, то існує можливість організації діяльного діалогу між користувачем і системою при пошуку оптимального розкладу.
Якщо під фазою розуміти операцію, яка одноразово обробляє всі безліч даних, то автоматизоване складання розкладу на будь-якому етапі його формування є багатофазним процесом, що включає:
- розробку структури представлення даних, що враховує більшість обмежень, що накладаються на розклад;
- розробку алгоритму побудови опорного рішення, результатом роботи якого є хоча б одне несуперечливе розклад, якщо воно існує в рамках заданих початкових умов;
- оцінку отриманого безлічі рішень і вибір найбільш підходящого.
Не можна не помітити принципові відмінності строгих обмежень при формуванні розкладу іспитів від строгих обмежень, які використовуються при формуванні розкладу занять. Наприклад, в розкладі іспитів необхідно обов'язкове включення тимчасових інтервалів (пауз) між іспитами групи таким чином, щоб студенти мали час на підготовку, тоді як при формуванні розкладів занять навпаки - відсутність тимчасових «вікон» між заняттями є одним з видів строгих обмежень.
Основні терміни (генеруються автоматично). складання розкладу, розкладу іспитів, теорії розкладів, завдання складання розкладу, екзаменаційної сесії, розкладу занять, складання розкладу, складання розкладу екзаменаційної, складання розкладу вузу, оптимального розкладу, завдання складання розкладу, формування розкладу, завдань теорії розкладів, складання оптимального розкладу, і складання розкладу іспитів, складання розкладу занять, процедури складання розкладу, в разі складання розкладу, складання навчального ра списання, методів складання розкладу.