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

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

Індекс рубрикатора НБУВ: Ч481.444 + З810.416

Рубрики:

Розклад навчальних занять у вищій школі

Багатокритерійні моделі прийняття рішень

Шифр НБУВ: РА349442 Пошук видання у каталогах НБУВ 

  Скачати повний текст

Рассмотрены новые подходы, обеспечивающие целесообразную перестройку процесса составления расписания учебных занятий, основанные на опыте и интуиции работников высшей спортивной школы. Выявлены нерешенные в этой области вопросы и на основе проведенного анализа сформулирована задача составления расписания учебных занятий. Предложена автоматизированная система синтеза расписания учебных занятий ВУЗов. С помощью этой системы можно строить оптимальное расписание занятий по выбранному алгоритму синтеза.

Рассмотрена проблема создания системы принятия решений при составлении расписания в ВУЗе. Предложена начальная модель системы принятия решений при составлении расписания, которая использует методы построения расписания на основе принципа вычисления свободы расположения отдельного занятия в полученном расписании. Начальная модель уже учитывает многокритериальность задачи составления расписания и трудоемкий технический процесс его создания, поэтому изначально нацелена на экономию времени процесса составления расписания и его качество.

Рассмотрена проблема решения задачи составления расписания занятий в высших учебных заведениях. Предложен метод, позволяющий увеличить точность полученных решений задачи составления расписания занятий.

Рассмотрена задача формирования расписаний занятий в высших учебных заведениях. Предложены новые подходы, модели и метод формирования целевой функции с ее последующей оптимизацией на основе применения эволюционных технологий и матричного представления расписания.

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

Описано розробку та реалізацію паралельного генетичного алгоритму (ГА) побудови розкладу ВНЗ на основі моделі "фермер-робітники" з елементами евристики для вибору аудиторій та пар під час ініціалізації, застосування нового (додаткового) оператора мутації, додання вдалих підрозв'язків в популяцію під час інціалізації початкової популяції. У алгоритмі введено специфічний спосіб кодування хромосоми, запропоновано функцію оцінки хромосоми з урахуванням низки обмежень, що накладаються на результуючий розклад-хромосому, а також розроблено спеціальні оператори кросинговеру та мутації. На основі експериментів запропоновано оптимальні значення параметрів ГА.

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

Мета роботи - формулювання принципів автоматичного формування нежорстких вимог до розкладу з боку викладачів у випадку їх відсутності, на основі аналізу розкладів попередніх періодів. Розв'язання даної задачі складає актуальність роботи. Для вирішення цього завдання проведено аналіз теоретичних й експериментальних робіт та використані метод найближчого сусіда для визначення прецедентів з інтегрованої бази розкладів та загальна теорія розкладів для розробки математичних моделей формування розкладу занять. Розроблено принципи автоматичного формування нежорстких вимог до розкладу з боку викладачів на основі аналізу розкладів занять попередніх періодів з використанням модифікованого методу найближчого сусіда для визначення прецедентів з інтегрованої бази розкладів, що дозволить зменшити кількість операцій введення нежорстких обмежень. У випадку відсутності сформульованих побажань викладачів до розкладу занять виконується аналіз розкладів за попередні роки з якого визначаються критерії якості розкладу з точки зору викладача, виходячи з припущення, що якщо розклади попередніх періодів задовольняли викладача, то і новий розклад складений за тими самими критеріями також буде задовільним. Таким чином, у підсумку база даних нежорстких вимог з боку викладачів може бути вичерпною, що дозволить задіяти автоматичний режим формування розкладу занять. До складу узагальненого критерію врахування інтересів викладачів входять наступні частинні критерії: число "вікон" у розкладі викладачів, виконання обмеження на максимальне число зайнятих днів у тиждень для викладачів, виконання обмеження на мінімальне число занять у довільний день тижня для викладачів, особисті побажання викладачів. Узагальнений критерій оптимальності розкладу викладачів враховує ступінь оптимальності індивідуального розкладу кожного викладача. Для кількісного порівняння та ранжування часткових критеріїв оптимальності вводиться числовий еквівалент ступеня важливості кожного часткового критерію оптимальності. Пошук рішення на основі прецедентів в базі даних попередніх розкладів полягає у визначенні ступеня подібності поточної ситуації з прецедентами, які мали місце раніше, а потім у виконанні спроби розв'язати сформовану проблемну ситуацію, використовуючи прецедент, що має найбільшу ступінь схожості з поточною ситуацією. Безумовного введення будуть потребувати тільки ті обмеження, що стосуються нових дисциплін, або потребують змінення на нові значення. Обмеження введені для поточного розкладу мають пріоритет перед сформованими автоматично.

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

Розглянуто відому задачу складання розкладу навчань в університеті. Такі задачі розв'язуються декілька разів на рік в кожному навчальному закладі. Не дивлячись на багаточисленні дослідження в даній галузі, проблема побудови оптимального розкладу залишається відкритою. Це пов'язано зі складністю відповідної оптимізаційної задачі, зокрема її значною розмірністю, що затрудняє чисельне розв'язування такої задачі існуючими методами оптимізації. Вдосконалення потребують також оптимізаційні моделі складання розкладів. Таким чином, оптимізація розкладу є складною обчислювальною проблемою і потребує розробки нових методів її розв'язування. Мета роботи - вдосконалення оптимізаційних моделей складання розкладів навчання в університеті та використання нових ефективних методів для їх розв'язування. Використано метод точної квадратичної регуляризації для розв'язування оптимізаційних задач складання університетського розкладу навчання. Точна квадратична регуляризація дозволяє перетворити складні оптимізаційні моделі з булевими змінними до задачі максимуму норми вектору на опуклій множині. Для розв'язування цієї задачі ми використовуємо ефективний прямо-двоїстий метод внутрішньої точки та метод дихотомії. Цей метод показав значно кращі результати при розв'язуванні багатьох складних мультимодальних задач. Це підтверджується багатьма порівняльними обчислювальними експериментами. Ще більшу ефективність метод точної квадратичної регуляризації демонструє при розв'язуванні задач складання розкладу навчання. Цей метод оптимізації використовується вперше для даного класу задач, тому він потребував розробки відповідного алгоритмічного забезпечення. Побудована нова більш проста оптимізаційна модель складання розкладу, яка легко реалізується програмно в пакеті Excel при наявності надбудов OpenSolver, RіskSolver та інших. Приведений невеликий приклад побудови розкладу та описана пошагова інструкція отримання оптимального розв'язку. Висновки: розроблена нова ефективна технологія складання розкладу навчань в університеті, яка виділяється простотою реалізації і не потребує розробки спеціального програмного забезпечення. Ефективність забезпечується використанням нового методу точної квадратичної регуляризації.