СІПКО Олена Миколаївна. МОДЕЛІ ТА ЕВОЛЮЦІЙНИЙ МЕТОД СКЛАДАННЯ РОЗКЛАДУ ЗАНЯТЬ У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ : СИПКО Елена Николаевна. МОДЕЛИ И ЭВОЛЮЦИОННЫЙ МЕТОД СОСТАВЛЕНИЯ РАСПИСАНИЯ ЗАНЯТЫ В ВЫСШЕМ УЧЕБНОМ ЗАВЕДЕНИИ SIPKO Elena Nikolaevna. MODELS AND EVOLUTIONARY METHOD OF COMPILATION OF SCHEDULE CLASSES IN HIGHER EDUCATIONAL INSTITUTION

Краткое описание

СІПКО Олена Миколаївна. Назва дисертаційної роботи: "МОДЕЛІ ТА ЕВОЛЮЦІЙНИЙ МЕТОД СКЛАДАННЯ РОЗКЛАДУ ЗАНЯТЬ У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ"

Київський національний університет імені Тараса Шевченка
На правах рукопису
СІПКО ОЛЕНА МИКОЛАЇВНА
УДК 004.942:378.145
МОДЕЛІ ТА ЕВОЛЮЦІЙНИЙ МЕТОД СКЛАДАННЯ РОЗКЛАДУ
ЗАНЯТЬ У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ
05.13.06 – інформаційні технології
Дисертація на здобуття наукового ступеня кандидата технічних наук
Науковий керівник
Снитюк Віталій Євгенович
Доктор технічних наук, професор
Київ – 2016
2
ЗМІСТ
ВСТУП ............................................................................................................... 5
Розділ 1. АНАЛІЗ ПРОБЛЕМИ ФОРМУВАННЯ ЕФЕКТИВНОГО
РОЗКЛАДУ У ВИЩОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ...................................... 11
1.1 Формування розкладу у вищому навчальному закладі – необхідна
умова ефективного навчального процесу............................................................... 12
1.2 Аналітичний огляд принципів, моделей, методів і програмноалгоритмічного забезпечення для складання розкладів занять............................ 17
1.3 Формалізація задач підвищення ефективності роботи вищого
навчального закладу.................................................................................................. 29
1.4 Постановка задачі дослідження та структурно-логічна схема ........ 35
Висновки до розділу 1 ................................................................................. 39
Розділ 2. ЦІЛЬОВІ ФУНКЦІЇ ТА ВИД ПОТЕНЦІЙНИХ РОЗВ’ЯЗКІВ У
ЗАДАЧІ СКЛАДАННЯ РОЗКЛАДІВ..................................................................... 40
2.1 Домінуючий суб’єктивізм як принцип формування ефективного
розкладу……………………………………………………………………………..41
2.2 Інтегральна цільова функція та критерій ефективності розкладу
навчальних занять ..................................................................................................... 46
2.3 Визначення коефіцієнтів цільової функції відображення
суб’єктивних переваг учасників навчального процесу......................................... 48
Висновки до розділу 2 ................................................................................. 54
Розділ 3. ЕВОЛЮЦІЙНА ТЕХНОЛОГІЯ СКЛАДАННЯ РОЗКЛАДІВ З
ВИКОРИСТАННЯМ НЕЧІТКИХ ВИСНОВКІВ................................................... 55
3.1 Обґрунтування використання еволюційного моделювання в задачі
складання розкладу навчальних занять .................................................................. 56
3.2 Особливості формування структури розв’язку та початкової
популяції…………………………………………………………………………….65
3.3 Модифікований метод розв’язання задачі складання розкладу з
використанням штрафної функції ........................................................................... 75
3
3.4 Алгоритмізація еволюційного методу розв’язання задачі складання
розкладу навчальних занять..................................................................................... 89
Висновки до розділу 3 ................................................................................. 92
Розділ 4. ІНФОРМАЦІЙНО-АНАЛІТИЧНА СИСТЕМА
СКЛАДАННЯ РОЗКЛАДУ ЗАНЯТЬ ТА ВЕРИФІКАЦІЯ ОДЕРЖАНИХ
РЕЗУЛЬТАТІВ……………………………………………………………………...93
4.1 Обґрунтування вибору засобів створення програмного продукту 93
4.2 Особливості представлення вхідної інформації та структура
інформаційно-аналітичної системи складання розкладу занять ........................ 104
4.3 Структура бази даних......................................................................... 107
4.4 Принципи функціонування автоматизованої системи та
експериментальна верифікація одержаних результатів...................................... 118
Висновки до розділу 4 ............................................................................... 122
ВИСНОВКИ .................................................................................................. 123
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ..................................................... 125
ДОДАТКИ ..................................................................................................... 141
4
СПИСОК ПРИЙНЯТИХ СКОРОЧЕНЬ
NP
АССР
АСУ
ВНЗ
ГА
ЗСР
ЗСРНЗ
ІАС
ІМД
МАІ
МД
НП
ПАВ
ПАС
РБД
РМД
СКВ
СУБД
ЧДТУ
– nondeterministically polynomial
– автоматизована система складання розкладів
– автоматизована система управління
– вищий навчальний заклад
– генетичний алгоритм
– задача складання розкладу
– задача складання розкладу навчальних занять
– інформаційно-аналітична система
– інфологічна модель даних
– метод аналізу ієрархій
– модель даних
– навчальний процес
– послідовний аналіз варіантів
– програмно-алгоритмічні системи
– реляційна база даних
– реляційна модель даних
– середнє квадратичне відхилення
– система управління базами даних
– Черкаський державний технологічний університет
5
ВСТУП
Актуальність теми. Ефективність функціонування сучасного виробництва
значною мірою визначається рішеннями, прийнятими на етапах календарного
планування та оперативного управління. Поряд з поліпшенням якості планових
рішень все більш жорсткими стають вимоги до скорочення термінів виробництва, підвищення оперативності та гнучкості управління. Сьогодні у створенні
автоматизованих систем управління виробництвом активно використовуються
нові для вітчизняної практики технології: управління проектами, управління
ресурсами, промислова логістика тощо. Їх спільною метою є оптимізація і використання наявних матеріальних ресурсів та кадрового потенціалу шляхом
складання різного роду розкладів. Особливе місце серед них займає задача
складання розкладу занять у навчальних закладах. Якість підготовки фахівців у
вищих навчальних закладах і, особливо, ефективність використання науковопедагогічного потенціалу залежать певною мірою від рівня організації навчального процесу. Одна з основних складових цього процесу – розклад занять – регламентує трудовий ритм, впливає на творчу віддачу викладачів, тому його можна розглядати як фактор оптимізації використання обмежених трудових ресурсів – викладацького складу. Таким чином, вирішення проблеми розробки оптимальних розкладів занять у вищих навчальних закладах має ще і очевидну
економічну складову.
Теорія розкладів є добре вивченою і описаною в багатьох роботах, починаючи з 60-х років минулого сторіччя, такими відомими вченими як Р.В. Конвей, Е.Г. Кофман, В.Л. Максвел, Л.В. Міллер; зокрема, проблемою складання
розкладів навчальних занять займались такі вчені як Д. де Верра, М.М. Глибовець, Б.А. Лагоша, А.В. Петропавловська, К.Г. Самофалов, В.П. Симоненко, Т.
Строхлейн, В.М. Томашевський, Г. Шмідт та інші.
Свого часу був сформульований клас NP-повних задач теорії розкладів,
для розв’язання яких не знайдено ефективних алгоритмів. Саме до таких задач
можна віднести більшість реальних задач виробничого планування, зокрема і
6
задачу складання розкладу навчальних занять. У порівнянні з серединою минулого століття в останні роки з’явилась значна кількість програмних і апаратних
засобів (мови програмування високого рівня, сучасні персональні комп’ютери),
які розширюють можливості розробників методів розв’язання задач теорії розкладів.
Проведений аналіз сучасного стану досліджень у теорії розкладів вказує на
наявність ряду нерозв’язаних задач. Серед них основними є такі:
– здійснено формальні постановки задач й описані моделі і методи, що враховують різні обмеження, в той же час безпосереднє розв’язання практичних
задач за допомогою цих моделей виявляється неможливим як внаслідок їх
великої розмірності та NP-складності, так і тому, що в практичних задачах
необхідно враховувати не лише формальні, але і якісні критерії та обмеження;
– проблеми розв’язання слабко структурованих задач на даний час розглядаються в межах окремих наукових дисциплін (починаючи від системного
аналізу і теорії систем і закінчуючи теорією оптимізації), що веде до розрізненості досліджень, відсутності єдиного підходу;
– не вивчено проблеми залежності якості отриманих розв’язків від структурних характеристик та рівня визначеності середовища;
– недостатньо досліджено проблеми відображення системи переваг зацікавлених осіб та їх врахування в цільових функціях.
Оптимізація навчального процесу пов’язана з важливістю розв’язання вищевказаних задач, що вказує на актуальність розробки еволюційних технологій
складання розкладів занять на основі суб’єктивних переваг.
Зв’язок роботи з науковими програмами, планами, темами. Дисертаційне дослідження виконане відповідно до плану науково-дослідної роботи на
тему: «Мультиагентні та еволюційні технології розв’язання високорозмірних
задач» (номер державної реєстрації 0115U005344), що виконувалась у Черкаському державному технологічному університеті.
7
Мета і задачі дослідження. Метою дисертаційного дослідження є підвищення ефективності процесу диспетчеризації занять у вищих навчальних закладах шляхом розробки моделей і методів формування розкладу навчальних занять на основі суб’єктивних переваг та еволюційних технологій.
Для досягнення поставленої мети необхідно розв’язати наступні задачі:
– провести аналіз існуючих принципів, моделей, методів та програмноалгоритмічного забезпечення для розв’язання задачі складання розкладу;
– здійснити формалізовану постановку та розв’язати задачу складання розкладу занять для підвищення ефективності освітнього процесу;
– побудувати математичні моделі, які дозволять визначати якість розкладу навчальних занять;
– розробити структуру потенційних розв’язків задачі складання розкладу занять;
– розробити еволюційний метод оптимізації цільової функції задачі складання
розкладу занять;
– виконати верифікацію розроблених моделей та методу і сформувати структурні та функціональні елементи інформаційно-аналітичної системи.
Об’єктом дослідження є процеси диспетчеризації занять у вищих навчальних закладах.
Предмет дослідження – моделі, методи та інструментальні засоби формування розкладу занять у вищих навчальних закладах.
Методи дослідження. Аналіз технологій складання розкладів здійснено на
основі системного підходу. Розробка моделей та методу складання розкладу
навчальних занять виконані на основі технологій еволюційного моделювання,
методу аналізу ієрархій та нечіткої логіки. При розробці структури та формуванні елементної бази інформаційно-аналітичної системи складання розкладу
занять використані технології об’єктно-орієнтованого проектування.
Наукова новизна одержаних результатів. У дисертаційному дослідженні
виконано формалізацію і розв’язано науково-технічну задачу розробки моделей, методів та інструментальних засобів складання розкладу навчальних за-
8
нять у вищих навчальних закладах на основі еволюційного моделювання та нечітких експертних висновків, що дозволило одержати теоретичні та практичні
результати, які характеризують новизну дослідження та особистий внесок автора, зокрема:
вперше:
 побудовано математичні моделі для формування розкладу занять, в яких,
на відміну від існуючих, диференційовано враховані вимоги суб’єктів
освітнього процесу та штрафи за їх невиконання, що дозволило підвищити ефективність процесу диспетчеризації занять у вищому навчальному
закладі;
 розроблено матрично-еволюційний метод оптимізації цільової функції
формування розкладу занять, у якому забезпечено неперервність потенційних розв’язків-розкладів, що зменшує час їх побудови та верифікації;
удосконалено:
 цільові функції для розв’язання задачі складання розкладу навчальних занять шляхом об’єктивізації процесу визначення вагових коефіцієнтів переваг суб’єктів освітнього процесу, що дозволило здійснювати порівняльний аналіз ефективності розкладів;
дістали подальшого розвитку:
 методи еволюційної спрямованої оптимізації за рахунок їх адаптації до
розв’язання дискретної задачі формування розкладів занять у вищих навчальних закладах, що дозволило більш повно задовольнити вимоги
суб’єктів освітнього процесу та збільшити швидкість пошуку прийнятного (квазіоптимального) розкладу.
Практичне значення одержаних результатів. Отримані автором теоретичні результати доведені до конкретних методик і алгоритмів, розроблено автоматизовану систему складання розкладу навчальних занять. Основні положення, одержані в дисертації, спрямовані на подальший розвиток технологій
складання розкладів навчальних занять. Розроблені моделі та методи складають
методологічну базу для оптимізації освітнього процесу шляхом формування
9
покращених розкладів навчальних занять. Результати дисертаційної роботи
впроваджені або використані в Черкаському державному технологічному університеті, Черкаському інституті пожежної безпеки імені Героїв Чорнобиля
Національного університету цивільного захисту України та Черкаському національному університеті імені Богдана Хмельницького.
Особистий внесок здобувача. Всі основні результати, що виносяться на
захист, отримані здобувачем особисто. У роботах, опублікованих у співавторстві, здобувачеві належать, зокрема, у статті [34] – структурні елементи цільової
функції, у роботах [35, 121, 129, 131-134,] – матрично-еволюційний метод з використанням штрафної функції для оптимізації цільової функції, а також еволюційний метод формування оптимального розкладу, що базується на розробці
та використанні цільової функції, в основі якої лежать врахування вимог викладачів і студентів.
Апробація результатів дисертації. Основні висновки, положення і результати дисертації доповідались і обговорювались на:
 IV Міжнародній науково-практичній конференції студентів, аспірантів та
молодих вчених “Шевченківська весна” (м. Київ, 2006 р.);
 VІІІ Міжнародній конференції „Інтелектуальний аналіз інформації” (м. Київ,
2007 р.);
 VІ, VІІ, VІІІ Всеукраїнських конференціях молодих науковців “Інформаційні
технології в освіті, науці й техніці” (м. Черкаси, 2008 р., 2010 р., 2012 р.);
 ХVI Всеукраїнській науковій конференції „Сучасні проблеми прикладної
математики та інформатики ” (м. Львів, 2009 р.);
 ІV Міжнародній науково-технічній конференції “Комп’ютерні науки та інформаційні технології” (м. Львів, 2009 р.);
 XII, XVI Міжнародних науково-технічних конференціях System Analysis and
Information Technologies (м. Київ, 2010 р., 2014 р.);
 V, VІ, VІІ Міжнародних школах-семінарах «Теорія прийняття рішень» (м.
Ужгород, 2010 р., 2012 р., 2014 р.);
10
 І, ІІ Міжнародних науково-технічних конференціях «Обчислювальний інтелект» (м. Черкаси, 2011 р., 2013 р.);
 ІХ Міжнародній науково-практичній конференції «Математичне та імітаційне моделювання систем» (м. Київ-с. Жукін, 2014 р.);
 ХХ Міжнародній конференції «Knowledge-Dialogue-Solution» (м. Київ, 2014
р.);
 ІІ Міжнародній конференції «Інформаційні технології та взаємодії» (м. Київ,
2015 р.).
Публікації. Результати дисертації викладені в 24 публікаціях, серед яких
7 статей опубліковано у фахових виданнях, затверджених ДАК України, з них 2
– у наукових фахових іноземних виданнях, а також 17 тез доповідей у матеріалах конференцій та наукових семінарів.
Структура та обсяг дисертації. Дисертаційна робота складається із
вступу, 4 розділів, списку використаних джерел (145 найменувань), 3 додатків.
Основний текст роботи викладено на 120 сторінках. Робота включає 14 рисунків, 15 таблиць.

Список литературы

ВИСНОВКИ
У дисертаційному дослідженні розв’язана науково-технічна задача підвищення ефективності функціонування вищого навчального закладу шляхом розробки моделей і методів формування розкладу навчальних занять, зокрема:
1. Проведений аналіз принципів, моделей, методів та інструментальних
засобів свідчить про домінування механістичного підходу до формування розкладу занять у вищих навчальних закладах з мінімальним урахуванням вимог
суб’єктів навчального процесу.
2. Виконано формалізовану постановку та розв’язано задачу складання розкладу занять з урахуванням вимог викладачів і студентів та штрафів за їх невиконання, що дозволило здійснювати порівняльний аналіз ефективності розкладів навчальних занять як ступеня задоволення таких вимог.
3. Побудовано математичні моделі, в яких диференційовано враховано вагові коефіцієнти студентів та викладачів, а також пріоритетність вимог студентських груп та індивідуальні переваги викладачів, оптимізація ступеня задоволення яких і визначає процес формування оптимізованого розкладу занять.
4. Сформовано структуру потенційних розв’язків задачі складання розкладів та їх подання у вигляді вузлів решітки прямокутного паралелепіпеда, що дозволило зменшити кількість таких розв’язків. Їх генерація здійснюється з урахуванням «жорстких» обмежень, а нові розв’язки отримують шляхом варіації
можливих варіантів, що залишились, з урахуванням їх перевірки на суперечливість. Це дозволяє скоротити час пошуку оптимізованого розкладу на 28-31%.
5. Розроблено інтегральний матрично-еволюційний метод оптимізації цільової функції задачі складання розкладів, синергетичний ефект використання
якого досягається через скорочення розмірності задачі та спрямований пошук
оптимального значення складної негладкої поліекстремальної залежності, які
дозволяють визначати ефективність розкладу як ступінь задоволення вимог
студентів і викладачів.
124
6. Результати експериментальної верифікації свідчать про те, що запропоновані моделі та метод не дозволяють гарантувати отримання оптимального
розв’язку, вони спрямовані на пошук розкладів, ефективність яких можна порівняти і, відповідно, вибрати найкращий з них. У порівнянні з методом «ручного» складання розкладу занять у ВНЗ застосування запропонованої технології
дозволяє одержати розклад, який на 5-9% є ефективнішим.