Проблеми складання розкладу у вузі

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

Складання розкладу - одна з найбільш поширених завдань в плануванні і оптимізації навчального процесу в навчальних закладах. Від того, наскільки добре складено розклад, залежить ефективність роботи викладачів, засвоєння навчально-го матеріалу студентами, раціональне використання матеріальних ресурсів.
Автоматизація складання розкладу - класична задача в системах управління навчальним закладом, але на даний момент немає єдиного, загальноприйнятого способу її вирішення.
Всі підходи до питання складання розкладу засновані на евристичних методах, які приходять до людини з досвідом роботи. Формалізувати ці методи проблематично, так як вони пов'язані з прийняттям рішень оператором, що становить розклад, який керується досвідом і інтуїцією. Найчастіше сам співробітник, що становить розклад, не може відповісти на питання, чому він вибрав певний варіант розміщення занять, а не який-небудь інший серед допустимих. Але, незважаючи на складність формалізації алгоритмів, можна виділити особливості таких евристичних підходів, виходячи з вимог, що пред'являються до складання розкладу. Безумовно, для кожного навчального закладу ці вимоги різні, адже вони історично обумовлені особливістю організації самого навчального процесу. Однак навіть при всіх деталях, можна виділити загальні вимоги, що пред'являються до розкладу:

1. Мінімальна кількість занять у того, хто навчається в день;
2. Максимальна кількість годин навчального навантаження на тиждень на кожного учня;
3. Максимальна кількість занять у того, хто навчається в день;
4. Мінімізація вікон в учнів;
5. Облік тимчасових відстаней між корпусами при зміні корпусу навчаються;
6. Облік побажань викладачів;
7. Цикл занять з дисципліни не повинен закінчуватися лекційним заняттям, якщо є семінарські (практичні) заняття;
8. Цикл занять з дисципліни не повинен починатися з семінарського (практичного) заняття, якщо є лекційні заняття;
9. До кожного лекційного заняття все групи потоку повинні підходити, отримавши однакову кількість годин семінарських (практичних) занять;
10. Чи не проводити більше двох лекцій по одній і тій же дисципліні в день і не більше одного / двох семінарських занять по одній і тій же дисципліні в день;
11. Мінімальна кількість занять у викладача в день;
12. Максимальна кількість занять у викладача в день;
13. Мінімізація вікон у професорсько-викладацького складу (далі ППС);
14. Мінімізація переробок викладачів згідно штатного розкладу;
15. Мінімізація кількості одночасно проводяться однакових дисциплін у навчальному закладі в один і той же час. Це безпосередньо впливає на кількість виробленого ППС для забезпечення навчального навантаження;
16. Максимальне використання аудиторного фонду. Сюди можна віднести вимоги до максимально щільному розміщенню навчаються по аудиторіях згідно місткості останніх, а також мінімізацію простою приміщень;
17. Облік тимчасових відстаней між корпусами при зміні корпусу викладачем.

Завдання складання розкладу безпосередньо залежить від початкових умов. Можна згрупувати завдання складання розкладу за такими умовами в певні групи:

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

Розглянемо більш детально особливості кожної з вищеописаних груп завдань.
У завданнях з відомою інформацією про розподіл груп між ППС виникає проблема обліку побажань викладача, контроль поїздок при зміні корпусу, накладки в розкладі викладача (наявність декількох занять в один і той же час). Співробітникові, що становить розклад, необхідно при складанні вести відразу два опорних розкладу: розклад груп і розклад ППС. Особливо складною завдання стає, якщо викладачі розподілили навантаження між собою з точністю до групи, і оператор розкладу не може змінити цей розподіл. Тому одним з підходів, що дозволяють зменшити жорсткі рамки обмежень, в яких виявляється оператор, є використання розподілу викладачів без груп: викладачі вказують лише факультет, курс і кількість груп, які вони будуть вести протягом семестру. Конкретну групу призначає оператор, що становить розклад. Це дозволяє отримати ще одну додаткову ступінь свободи, яка дозволить зменшити кількість тупикових ситуацій.
У завданнях, в яких використовується лише навантаження кафедр, оператору вже не доводиться враховувати побажання ППС або перетину їх занять, також оператору не потрібно вести відразу два розкладу: групи і викладача. Однак опосередковано все ж оператор змушений враховувати, що кафедра повинна мінімізувати необхідний ППС для забезпечення навчального навантаження, тому стає дуже важливим виконання вимоги № 15. Облік цієї вимоги призводить до появи такої величини, як потужність кафедри, яка показує, скільки занять кафедра може вести по однієї і тієї ж дисципліни одночасно. Після складання розкладу кафедрам доводиться розставляти викладачів самим.
У завданнях складання розкладу без урахування кафедр ступенів свободи набагато більше, ніж в інших, тому досить логічним підходом є рух від групи або потоку. Однак в такому випадку при складанні розкладу не можна враховувати при складанні вимоги, пов'язані з викладачами (№ 6, 11-17).
Кожна вимога, що пред'являється до що складається розкладом, з вище перерахованих (1-17), накладає свої особливості на складання розкладу. Наприклад, при одночасному присутності в завданні вимог 3, 4, 10, 11, 12 і 15 для оптимального розміщення занять для задач групи 1 в межах викладача і потоку припадає намагатися розміщувати навантаження, яка Новомосковскется викладачем для всіх груп потоку. Для оптимального розміщення занять для задач групи 2 через відсутність відомостей про викладача в межах потоку припадає намагатися розміщувати спочатку лекції, а по-тому, на наступних парах, семінарські заняття з дисциплін, лекції яких були на попередніх парах, що дозволяє скомпонувати навантаження по однієї і тієї ж дисципліни. Саме це дозволяє побічно врахувати вимоги 11, 12, 15, пов'язані з викладачем.
Вимога № 16 найбільш оптимально виходить виконати, якщо все заняття в навчальному закладі проводяться в фіксованою сітки єдиного (загального) плану дзвінків. Якщо ж в навчальному закладі проводяться заняття, які не належать сітці плану дзвінків або в сітці плану дзвінків, відмінного від загального, то перетин таких занять із заняттями загального плану дзвінків призводить до простою аудиторного фонду по 20-40 хвилин, і протягом усього семестру сумарне час простою приміщень накопичується.
Окремою проблемою можна виділити розміщення занять з профільних дисциплін (якщо групи потоку не були укомплектовані за профілем), дисциплін за вибором, іноземної мови, фізкультури і факультативним дисциплінам. Суть проблеми в тому, що не завжди відомо, з яких академічних груп набрана та чи інша група для відвідування вищевказаних дисциплін, що може привести до накладок для учнів, якщо в один і той же час розміщувати заняття з дисциплін обов'язково-го вивчення і вищевказаних дисциплінах . Виходом з цієї ситуації є або виділення окремих днів для таких дисциплін, або розміщення цих занять першими або останніми парами.
Ще однією проблемою в завданню складання розкладу є потоки. Як і струми можуть створюватися не тільки на лекції (мабуть, найпростіший випадок), але і для інших занять, наприклад, семінарських. Використання потоків на семінарські заняття ускладнює завдання, адже розміщувати потоки завжди клопітка, ніж заняття для однієї групи. Також може бути присутнім розбиття груп на підгрупи на лабораторні заняття, заняття, що проводяться в спец. приміщеннях і т.д. При складанні розкладу в таких випадках використовують розміщення занять для однієї підгрупи на тижні однією парності, а для іншої підгрупи на іншу парність, при цьому заняття розміщуються в окремо виділений день або в початок / кінець занять в дні, щоб в учнів іншої підгрупи НЕ утворилися вікна. До того ж, рекомендується розміщувати такі заняття в першу чергу.
Іншою важливою особливістю в завданню складання розкладу є те, що враховує вимоги оператор введення розкладу: вага (значимість) вимог (1-17) може змінюватися динамічно в залежності від локальних умов на кожному кроці складання розкладу. Алгоритм зміни ваги теж евристичний.
Головна проблема, що виникає при автоматичному складанні розкладу - це оцінка якості складання розкладу. Тут можна виділити наступні оцінки:

1. кількість годин розміщених занять;
2. кількість годин не повністю розміщених занять;
3. кількість годин повністю не розміщених занять;
4. кількість розміщених дисциплін і груп;
5. кількість не повністю розміщених дисциплін і груп;
6. кількість повністю не розміщених дисциплін і груп;
7. сумарна тривалість вікон навчаються;
8. сумарна тривалість вікон викладачів;
9. максимальна тривалість вікна навчається;
10. максимальна тривалість вікна викладача;
11. середня кількість занять у викладача в день;
12. мінімальна кількість занять у викладача в день;
13. максимальна кількість занять у викладача в день.

Якщо автоматичне складання розкладу занять використовується для завдання групи 2, то оцінки 11-13 доцільно замінити на наступні:

• середня кількість занять з дисципліни в день в навчальному закладі;
• мінімальна кількість занять з дисципліни в день в навчальному закладі;
• максимальна кількість занять з дисципліни в день в навчальному закладі.

При проектуванні алгоритму автоматичного складання розкладу частина цих оцінок можна розглядати як критерії, що вимагають оптимізації, а частину можна розглядати як обмеження. Також при складанні розкладу для критеріїв можна використовувати різного роду згортки [2, 5], для зведення задачі до однокритерійним завдання оптимізації, або розглядати многокритериальную завдання оптимізації з використанням принципу домінування по Парето [8, 9, 10] і наступною побудовою многокритериального компромісу [11 ]. Для реалізації такого алгоритму потрібно використовувати методи оптимізації. Існує велика різноманітність і кількість методів вирішення завдань оптимізації. Найбільш поширений клас алгоритмів для таких завдань - це «жадібні» алгоритми [1]. Їх особливістю, стосовно до задачі складання розкладу, є ухвалення рішення на кожній ітерації виходячи з поточних значень критеріїв, що призводить до передчасних зупинок алгоритму і передбачень у локальні мінімуми (тупикові варіанти розміщень занять). Можна комбінувати «жадібні» алгоритми локального пошуку з алгоритмами глобального пошуку [3, 4, 6, 7], але це значно збільшує кількість варіантів, які доведеться алгоритму розглянути в процесі розміщення занять.

Поведінка оператора при складанні розкладу більше схожий на поведінку «жадібних» алгоритмів: оператор послідовно розміщує заняття, не намагається по-будувати або розглянути більше одного варіанту розміщення занять, адже дуже рідко йому доводиться видаляти розміщені заняття і вибирати інший варіант розміщення. Але оператор, виходячи зі свого досвіду і інтуїції в процесі кожного прийняття рішення про вибір варіанта розміщення занять переоцінює важливість кожного з критеріїв / обмежень, що дозволяє дуже ефективно і якісно додатися необхідного результату.
Саме через те, що формалізувати всі вимоги, що пред'являються до що складається розкладом, досить складно, а також складно врахувати унікальність бізнес-процесів в кожного навчального закладу, використання «жадібних» алгоритмів оптимізації без використання евристичних підходів призводить до результату, що не задовольняє кожне конкретне навчальний заклад. Тобто не вийде розробити алгоритм, який би враховував всі особливості всіх навчальних закладів.
Таким чином, найбільш правильним підходом в таких ситуаціях є проектування алгоритму автоматичного складання розкладу для потреб і з урахуванням особливостей кожного конкретного навчального закладу з використанням евристичних підходів, найбільш наближених до дій оператора. Це призводить до висновку: алгоритм автоматичного складання розкладу в кожному навчальному закладі все-таки свій.
Щоб врахувати мінливість прийняття рішень оператора при складанні розкладу в залежності від ситуацій, можна розбити процес складання розкладу на етапи, в кожному з яких принцип прийняття рішень не змінюється. Тобто етап - це група умов, в яких би оператор ухвалював рішення з одного й того ж алгоритму.
Розглянемо приклад одного з евристичних алгоритмів, спроектованих для конкретного навчального закладу по багатоетапної схемою.
В даному навчальному закладі завдання складання розкладу за початковими умовами відноситься до групи 2: викладачі невідомі, проте, потрібно непрямим шляхом їх враховувати через вимогу № 15.
Склад обмежень наступний: вікон в учнів не повинно бути, мінімально 1 заняття в день для того, хто навчається, максимально - 4, не більше двох лекційних занять в день по дисципліні для того, хто навчається, не більше одного нелекційних заняття з дисципліни в день для того, хто навчається. Критерії оцінки якості складається розкладу: 1-6.

Алгоритм складання фронтального розкладу багатоетапний, де кожен етап оптимізується «жадібним» алгоритмом розміщення на основі дерева рішень з різним складом обмежень. Склад етапів наступний:
1. Ручне розміщення занять фізкультури, занять в комп'ютерних класах, іно-дивного мови.
2. Розміщення лекцій безперервними циклами на весь період розкладу в п'ятиденку. Причому при розміщенні день тижня стає лекційним. При цьому враховуються вимоги 2, 3, 4, 5, 10, 15, 16. Вимога № 1 враховувати на цьому етапі не має сенсу, адже комплектація занять в днях ще не завершена.
3. Розміщення нелекційних занять безперервними циклами на весь період рас-писання тільки в нелекційних дні в п'ятиденку. Причому при розміщенні день тижня стає лекційним. При цьому враховуються вимоги 2, 3, 4, 5, 8, 10, 15, 16.
4. Прийняття рішення для кожної групи про виділення додаткового шостого дня. День виділяється, якщо є хоч одне лекційне заняття, яке можна розмістити безперервним циклом на весь період розкладу. Якщо такий день виділяється, то для таких груп заповнюється шостий день тижня під лекційні заняття. При цьому враховуються вимоги 2, 3, 4, 5, 10, 15, 16.
5. Розміщення залишків лекцій в лекційні дні. При цьому можна задіяти нові лекційні дні, але не більше п'яти днів під всі заняття групи. При цьому враховуються вимоги 2, 3, 4, 5, 10, 15, 16.
6. Розміщення залишків лекцій в нелекційних дні. При цьому можна задіяти нові нелекційних дні, але не більше п'яти днів під всі заняття групи. При цьому враховуються вимоги 2, 3, 4, 5, 10, 15, 16.
7. Розміщення залишків нелекцій в нелекційних дні. При цьому можна задіяти нові нелекційних дні, але не більше п'яти днів під всі заняття групи. При цьому враховуються вимоги 1, 2, 3, 4, 5, 8, 10, 15, 16.
8. Розміщення залишків нелекцій в лекційні дні. При цьому враховуються вимоги 1, 2, 3, 4, 5, 8, 10, 15, 16.
9. Всі залишилися нерозміщені заняття залишаються на ручну обробку. При цьому на розсуд особи, яка приймає рішення, можна видалити всі заняття, які не задовольняють вимогу 1 в результаті роботи попередніх етапів.

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