Національний університет “Львівська політехніка”

Верес Олег Михайлович

УДК 51.001.57+371.214

МЕТОДИ ТА ЗАСОБИ РОЗВ’ЯЗАННЯ

Слабоструктурованих задач

формування розкладів та розподілу ресурсів

01.05.02. – математичне моделювання та обчислювальні методи

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Львів - 2002

Дисертацією є рукопис.

Роботу виконано на кафедрі “Інформаційні системи та мережі” Національного університету “Львівська політехніка”.

Науковий керівник:

кандидат економічних наук, доцент Катренко Анатолій Васильович, Національний університет “Львівська політехніка”, кафедра “Інформаційні системи та мережі”, м. Львів

Офіційні опоненти:

доктор фізико-математичних наук, професор Слоньовський Роман Володимирович, Національний університет “Львівська політехніка”, кафедра “Прикладна математика”, м. Львів

доктор технічних наук, старший науковий співробітник Русин Богдан Павлович, Фізико-механічний інститут ім.Г.В.Карпенка НАН України, завідувач відділу методів і систем обробки, аналізу й ідентифікації зображень, м.Львів

Провідна установа:

Державний науково-дослідний інститут інформаційної інфраструктури Державного комітету зв’язку та інформатизації і НАН України (м.Львів), відділ інформаційних технологій і систем

Захист відбудеться 25 жовтня 2002 р. о 1600 годині на засіданні спеціалізованої вченої ради Д 35.052.05 у Національному університеті “Львівська політехніка” (79013, Львів - 13, вул. С.Бандери, 12, ауд. 226 головного корпусу).

З дисертацією можна ознайомитися у бібліотеці Національного університету „Львівська політехніка” (79013, Львів, вул. Професорська, )

Автореферат розіслано 20 вересня 2002 р.

Вчений секретар

спеціалізованої вченої ради Д 35.052.05,

доктор технічних наук, доцент Федасюк Д.В.

Загальна характеристика роботи

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

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

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

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

· проблеми розв’язання слабоструктурованих задач на даний час розглядаються в межах окремих наукових дисциплін (починаючи від системного аналізу і теорії систем і закінчуючи теорією оптимізації), що веде до розрізненості, клаптиковості досліджень, відсутності єдиного підходу;

· слабо вивчено проблеми залежності якості отриманих рішень від структурних характеристик та рівня визначеності середовища;

· недостатньо досліджено проблеми відображення системи переваг особи, що приймає рішення (ОПР).

У роботі розглянуто задачі підсистеми “планування”, а саме задачі, пов’язані з розподілом навантаження між викладачами, формуванням розкладу занять та розподілу ресурсів у ВНЗ. Представлені розробки скеровані на створення і вдосконалення методів та засобів розв’язання слабоструктурованих задач укладання розкладу та розподілу ресурсів, впровадження процедур прийняття рішень на різних рівнях формування розкладу. Для експериментальних досліджень методів та засобів було обрано навчальний процес у ВНЗ – Національному університеті „Львівська політехніка”.

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалася в рамках пріоритетного наукового напрямку Міністерства освіти і науки України „Перспективні інформаційні технології, прилади комплексної автоматизації, системи зв’язку” по темах: „Дослідження процесів проектування розподілених інтелектуальних інформаційних систем прийняття рішень для слабоструктурованих проблем на основі реляційних баз даних (на прикладі сфери фінансів, бізнесу та управління)”, шифр 0196U000179; „Розробка макетів та моделей для проектування розподілених інтелектуальних інформаційних систем, алгоритмів і програм виявлення та апробації систем переваг особи, що приймає рішення, методів відсіювання та відбору альтернатив в слабоструктурованому середовищі”, шифр 0198U000179. У рамках робіт по цих темах розроблено методику тест-опитувань для формування значень показників критеріїв оптимізації системи прийняття рішень слабоструктурованої задачі укладання розкладів та розподілу ресурсів.

Мета і задачі дослідження. Метою роботи є теоретичне обґрунтування методів та засобів розв’язання слабоструктурованих задач формування розкладів та розподілу ресурсів, практична розробка комплексу алгоритмів та програм укладання розкладу навчальних занять.

Для досягнення поставленої мети необхідно:

· обґрунтувати необхідність розв’язання слабоструктурованих задач формування розкладів та розподілу ресурсів як задач укладання розкладу навчальних занять;

· розробити основи побудови моделі багатоаспектної задачі формування розкладу та розподілу ресурсів в слабоструктурованому середовищі;

· дослідити джерела інформації, методи підтримання прийняття рішень та проблеми синтезу розкладу і розподілу ресурсів задачі укладання розкладу навчальних занять;

· розробити методи та алгоритми розв’язання задачі укладання розкладу навчальних занять, а також оптимізації інтегрованої оцінки прийняття рішень на різних рівнях формування розкладу.

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

Предмет досліджень. Розв’язок задач планування ІС ВНЗ, таких як побудова навчальних планів спеціальностей; оптимальний розподіл навантаження між викладачами кафедри з урахуванням формальних та неформальних обмежень; укладання розкладу навчальних занять з урахуванням організаційних, методичних та оптимізаційних вимог; оптимальний розподіл аудиторного фонду ВНЗ з урахуванням множини обмежень та вимог.

Методи досліджень. При виконанні поставлених задач використовувалися методи системного аналізу, тест-опитувань, моделі теорії розкладів, експертні методи, апарат теорії дослідження операцій.

Наукова новизна одержаних результатів.

1) досліджено задачу формування розкладу та розподілу ресурсів як слабоструктуровану задачу.

2) Запропоновано формалізовану постановку задачі укладання циклічних семестрових розкладів навчальних занять з урахуванням особливостей багатопрофільного ВНЗ.

3) Розроблено та досліджено метод покрокового формування рішення з переміщенням раніше призначених подій.

4) Запропоновано класифікацію системи показників та критеріїв інтегрованої оцінки якості розкладу навчальних занять.

5) Побудовано методику тест-опитувань для формування значень критеріїв оптимізації.

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

Практичне значення одержаних результатів.

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

· Реалізовано розроблений метод покрокового формування рішення з переміщенням раніше призначених подій, який дозволив покращити об'єктивні характеристики розкладу навчальних занять.

· застосовано систему показників та критеріїв інтегрованої оцінки розкладу навчальних занять у ВНЗ, що дозволило врахувати множину неформальних та оптимізаційних вимог.

· Реалізовано методику тест-опитувань для формування значень критеріїв оптимізації, використання яких дало змогу обчислити показники якості варіанту призначення.

· Розроблено засоби, використання яких враховує дію показників оптимізації на інтегровану оцінку варіанту розкладу навчальних занять.

· Розроблено алгоритми оптимального розподілу основних ресурсів задачі укладання розкладу, які забезпечують врахування формальних та неформальних обмежень.

· Розроблено прототип інформаційної системи, який відображає результати наукових досліджень.

Реалізація результатів роботи. Отримані наукові і практичні результати досліджень використано у вигляді математичного і програмного забезпечення окремих задач інформаційної системи національного університету “Львівська політехніка”, а також для комплексного вирішення задач планування навчального процесу у Дрогобицькому державному педагогічному університеті імені Івана Франка (м.Дрогобич, Львівська область), в Інституті підприємництва та перспективних технологій (м.Львів), у Львівському банківському інституті, у Державному фінансово-економічному інституті (м.Львів), у Технічому коледжі (м.Свалява Закарпатської області), що підтверджується відповідними актами впровадження.

Особистий внесок здобувача. Основна частина досліджень дисертаційної роботи виконана автором самостійно, а саме: всі теоретичні та основні практичні розробки, висновки і рекомендації.

У публікаціях, написаних у співавторстві, авторові дисертації належать: [8] опис алгоритму нормалізації експертної САПР реляційних БД, в [9] опис та реалізація алгоритму побудови мінімального покриття множини багатозначних залежностей засобами мови ПРОЛОГ, в [10]розробка структури інформаційної складової та системи прийняття рішень в задачі „Вступні іспити”.

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи було виголошено і обговорено на таких конференціях та семінарах:

· V-ій Міжнародній науково-технічній конференції “Досвід розробки і застосування САПР в мікроелектроніці” CADSM’99 секція “Спеціальні застосування комп’ютерних технологій”, м.Львів, 1999р.;

· VI-ій Міжнародній науково-технічній конференції “Досвід розробки та застосування приладо-технологічних САПР в мікроелектроніці” CADSM’2001 секція “Спеціальні застосування комп’ютерних технологій”, м.Львів, 2001р.;

· Наукові семінари кафедри „Інформаційні системи та мережі” та щорічні наукові конференції викладачів та науковців національного університету “Львівська політехніка”.

Публікації. Результати виконаних досліджень за темою дисертаційної роботи викладено в 12 статтях загальним обсягом 70 сторінок (3 написано у співавторстві), опублікованих у науково-технічних журналах, і тезах конференцій.

Структура і обсяг дисертації. Обсяг дисертації 152 сторінки. Вона складається з вступу, чотирьох основних розділів, висновків, списку використаних літературних джерел і додатків. У роботі налічується 33 рисунки і 32 таблиці, що повністю займають 7 та 1 сторінки відповідно. Обсяг додатків - 24 сторінки. Список літератури містить 82 найменування.

Основний зміст роботи

У вступі викладено загальну характеристику роботи, обґрунтовано актуальність та важливість питань, які розглядаються в дисертаційній роботі, визначено мету і задачі дослідження, сформульовано основні наукові положення, які виносяться на захист, та практична цінність дисертаційної роботи.

У першому розділі подано аналіз наявних методів розв’язання задач формування розкладів та розподілу ресурсів, а також формалізованої оцінки прийняття рішень. Обґрунтовано необхідність розробки методів та засобів розв’язання даних задач як слабоструктурованих.

Проаналізовано класифікації задач теорії розкладів, типи розкладів. для ефективного вирішення слабоструктурованої задачі формування розкладу та розподілу ресурсів необхідно розробити її формалізовану постановку.

Обґрунтовано доцільність побудови алгоритму направленого пошуку найкращого рішення з використанням принципу покрокового формування рішення. З метою структуризації первинну інформацію потрібно впорядкувати з урахуванням пріоритетів. Обґрунтовано доцільність застосування при розв’язанні задач розподілу ресурсів методів та моделей дослідження операцій.

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

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

Системний аналіз предметної області дав змогу виявити та структурувати вимоги до розкладу занять у ВНЗ. Ці вимоги розділено на дві основні групи обов’язкові та бажані (оптимізуючі).

Дослідження властивостей критеріїв, системи вимог і основних аспектів цілі формування оптимального розкладу та розподілу ресурсів дозволило провести декомпозицію цілі до рівня окремих критеріїв (табл.1). Часовий аспект відображають критерії Q1 , Q2 , Q3 , а ефективність завантаження основних ресурсів Q4 , Q5 , Q6.

Таблиця 1

Критерії оптимізації укладання розкладу та розподілу ресурсів

Виконання завантаження в запланований період | Ефективність завантаження основних ресурсів

Q1 |

Кількість абсолютних відмов множини замовлень | Q4 |

Сумарний відносний обсяг незавантажених ресурсів по множині видів ресурсів

Q2 |

Мінімальна кількість невиконаних замовлень з категоричними вимогами | Q5 |

Максимально незавантажений відносний обсяг по множині видів ресурсів

Q3 |

Кількість від’ємних відхилень термінів виконання від запланованого періоду | Q6 |

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

Таким чином, загалом проблема укладання розкладу навчальних занять у ВНЗ є слабоструктурованою і потребує для свого вирішення відповідних методів та засобів.

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

для кожного zLZ необхідно призначити підмножину тактів часу , навчальне приміщення ySY виду vL в кожен з і викладача pLP таким чином, щоб виконати всі основні та, якщо можливо, всі додаткові вимоги до розкладу навчальних занять, де zL – навчальне заняття множини занять Z ВНЗ; підмножина тактів періоду розкладу, в які є можливим проведення навчальних занять zL ; yS – навчальне приміщення з множини Y; thk – часовий такт впорядкованої множина тактів періоду розкладу Т; pL – викладач множини викладачів Р.

Основні (обов'язкові) обмежувальні фактори формалізовано таким чином:

впорядкована множина тактів thk періоду розкладу

де Th множина часових тактів одного навчального дня; h кількість навчальних днів у періоді розкладу; k кількість тактів (пар навчальних занять) в навчальному дні; кількість тижнів у періоді розкладу;

множина навчальних груп ВНЗ:

де XI підмножина “зв’язаних” входженням у спільні потоки навчальних груп; вектор параметрів, який характеризує навчальну групу xi ; множина потоків, у які входить навчальна група xi ; множина підгруп навчальної групи xi ; підмножина часових тактів періоду розкладу, “дозволених” для проведення навчальних занять для групи xi ; множина часових тактів періоду розкладу, в які для групи xi проводять заняття, що призначені раніше і не повинні розглядатися при машинному укладанні; вектор, який вказує для кожного дня h періоду розкладу T номер навчального корпусу , в якому повинні відбуватися заняття групи xi ; множина навчальних занять групи xi;

множина навчальних потоків ВНЗ:

де множина груп, які входять до потоку qj ; множина навчальних занять потоку qj ;

множина навчальних приміщень ВНЗ:

де множина навчальних приміщень виду v; множина навчальних приміщень навчального корпусу ; підмножина тактів періоду розкладу, в які навчальні приміщення yS можуть використовуватися для проведення занять;

множина викладачів ВНЗ:

де С ідентифікатор кафедри, навчальні курси якої читає викладач рr; підмножина часових тактів періоду розкладу, в які викладач рr бажає проводити доручені йому навчальні заняття; підмножина часових тактів періоду розкладу, в які викладач рr проводить заняття, що не повинні розглядатися при машинному укладанні розкладу;

множина навчальних занять ВНЗ:

де підмножина тактів періоду розкладу, в які є можливим проведення навчальних занять zL; параметр, який вказує, скільки разів протягом періоду розкладу необхідно проводити навчальне заняття zL; тривалість заняття zL в тактах; кількість навчальних груп (навчальних потоків qj), для яких проводиться дане заняття zL; вид навчального приміщення для проведення заняття zL; викладач, якого необхідно призначити для проведення навчального заняття zL; категорія навчальних занять, яка визначає підмножину часових тактів , оптимальних з позиції тих чи інших організаційно-методичних вимог, що ставляться перед розкладом.

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

Задача формування оцінки варіанту призначення полягає в побудові рівняння множинної регресії:

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

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

Інтегрована оцінка варіанту розкладу, яка є критерієм прогнозованої валідності, включає в себе такі показники:

1) Оцінка варіанту призначення події – навчальної години (пара) проведення заняття в межах дня.

2) Завантаження навчальної групи протягом дня.

3) Завантаження студентів різними видами занять упродовж дня.

4) рівномірність розподілу занять одного виду з однієї дисципліни на тиждень.

5) Рівномірність розподілу занять з однієї дисципліни на тиждень.

6) Оцінка варіанту призначення викладача в межах дня.

7) Завантаження викладача протягом дня.

8) Завантаження викладача упродовж тижня.

9) Оцінка варіанту призначення аудиторії для проведення заняття.

10) Оцінка тривалості переходів навчальної групи та викладача між заняттями.

Для реалізації суб’єктивних рішень ОПР використовує шкалу відносної важливості, а саме: 1 - рівна важливість; 3 - помірна перевага; 5 - суттєва перевага; 7 - значна перевага; 9 - дуже велика перевага; 2,4,6,8 - проміжні значення.

Значення показника оцінки призначення навчального заняття для групи або викладача залежить від вибору такту часу і забезпечує врахування оптимальності тривалості навчального дня: 9 призначення на першу пару; 7 призначення на другу пару; 5 призначення на третю пару; 3 призначення на четверту пару; 1 призначення на п’яту або шосту пару. Показники 2ч8 відображають джерела слабоструктурованості задачі формування розкладу та розподілу ресурсів. Множини значень тестових показників 2ч8 формуються на основі проведених тест-опитувань (рядки таблиці тесту відповідають варіанту зайнятості, а колонки – параметр ознаки зайнятості, в заключній графі заноситься бал оцінки) та отримання таблиць переводу початкових балів в нормалізовану шкалу для кожного з показників критеріїв оптимізації слабоструктурованої задачі укладання розкладу та розподілу ресурсів, які і враховують неформальні параметри.

Задача переходів між навчальними корпусами є специфічним випадком транспортної, а саме задачею про призначення – навчальну групу або викладача розглянуто як пункти зберігання, аудиторію – як пункти споживання, запаси в кожному з пунктів зберігання та потреби в пунктах споживання дорівнюють одиниці, тариф на перевезення – cіj тривалість переходу і отримано задачу з n роботами та n виконавцями. Формальна постановка задачі виглядає так:

хіj=0, якщо і–та робота не виконується j–м виконавцем, та 1 – якщо виконується.

Для визначення коефіцієнтів ваги критеріїв оптимізації в інтегрованій оцінці варіанту розкладу застосовано метод вагових коефіцієнтнів важливості (ВКВ), який має переваги методу попарних порівнянь і меншу невизначеність за ентропійною оцінкою та дає змогу точніше визначити шукане сумарне ранжування.

З цією метою будується матриця суміжності (t=1,2,…,m) з такими елементами:

Для ранжування визначаються коефіцієнти важливості:

,

де ітераційна важливість (і=1,2,...,n) порядку k=l,2,..., яка визначається як сума відповідних рядків матриці суміжності.

При досить великому k величини стабілізуються і можуть служити значеннями критерію ранжування.

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

Інформаційну складову побудовано із застосуванням CASE-засобів, описано її структуру, розроблену реляційну базу даних слабоструктурованої задачі формування розкладу і розподілу ресурсів описано на логічному рівні.

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

Для формування розкладу використовуються дві основні стратегії або їх комбінація:

1) Покрокове формування розкладу із забезпеченням виконання як обов’язкових, так і бажаних вимог (декомпозиція в часі).

2) Формування розкладу занять з урахуванням спочатку обов’язкових, а потім додаткових (критеріїв та показників) вимог – декомпозиція за типами вимог.

Укрупнений алгоритм проектування розкладів, отриманий у результаті декомпозиції загальної моделі, складається з таких агрегованих кроків (рис.1):

1) Підготовка нормативної інформації, формування довідників; підготовка плану робіт на визначений період планування.

2) Формування розкладу попередньо заданих занять (“нульовий розклад”).

3) Укладання розкладу навчальних занять.

4) Аналіз отриманого варіанту розкладу. Якщо розклад є незадовільним, повернення до кроку 3, інакше - завершення роботи.

Перший етап є підготовчим, а всі інші є етапами проектування розкладу та розподілу ресурсів.

Укладання розкладу навчальних занять (крок 3) реалізується у два етапи. На першому етапі вирішується задача упорядкування множини замовлень на проведення занять з урахуванням всіх ресурсних обмежень та критеріїв оптимізації. На другому етапі проводиться покрокове конструювання розв’язку з переміщенням подій.

Процес побудови розкладу за комбінованою стратегією включає такі етапи:

· генерація попередніх варіантів розкладу, що відповідає безумовним вимогам;

· вибір варіантів для остаточного опрацювання;

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

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

Однією з основних задач при укладанні розкладу навчальних занять є розподіл основних ресурсів, тобто призначення викладача й аудиторії для проведення планового заняття.

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

Max

за умови

де ресурс, тобто загальний годинний фонд завантаження аудиторії і-го типу; аудиторія j-ої місткості; кількість занять (годин) і-го типу в аудиторії j-ої місткості; ціна (важливість) завантаження аудиторії j-го класу; наявна кількість аудиторій j-го класу. Функція мети оцінює ефективність завантаження аудиторного фонду.

Після того, як сформовано масив замовлень на проведення занять, проводиться дослідження системи обмежень задачі. Невиконання хоча б одного з обмежень свідчить про дефіцитність і-го виду ресурсу, в протилежному випадку має місце або повне використання ресурсу (знак рівності), або резерв. Отримана інформація є підставою для побудови відповідного сценарію розподілу аудиторного фонду.

Процес розподілу ресурсу поділяється на такі етапи:

· на першому етапі може призначатися аудиторія відповідно до необхідного вмісту і типу заняття, різниця між місткістю аудиторії і необхідною згідно із замовленням (кількість студентів) не може перевищувати нормативного значення (10%);

· на другому етапі кількість виділених для призначення аудиторій збільшується за рахунок частини аудиторій факультетського підпорядкування. Норматив різниці місткості для аудиторії збільшується (40%);

· на третьому етапі призначення аудиторний фонд для проведення занять розширюється відносно другого етапу за рахунок кафедральних аудиторій. Обмеження на місткість – місткість аудиторії повинна бути не меншою, ніж вимагає замовлення.

Пошук аудиторії проводиться для кожного визначеного часового такту призначення навчального заняття багатократно, тому задача розподілу аудиторного фонду розв’язується з використанням евристичних алгоритмів.

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

Інформаційна складова слабоструктурованої задачі формування розкладів та розподілу ресурсів реалізує реляційних підхід до побудови бази даних. До її складу входять: нормативно-довідкова інформація; замовлення на проведення занять; розклад навчальних занять.

Опрацьована модель збереження розкладу навчальних груп з використанням таблиць посилань дозволяє повно та ефективно будувати інформаційну модель слабоструктурованої задачі укладання розкладу та розподілу ресурсів.

Четвертий розділ містить опис прототипу інформаційної системи (ІС). Для забезпечення простоти впровадження та підтримки прототипу ІС, його побудовано в архітектурі клієнт-сервер на базі сучасних промислових СУБД з використанням універсальних засобів розробки. Представлено засоби взаємодії з користувачами.

Для експериментального дослідження моделей, методів та алгоритмів, представлених у роботі, обрано навчальний процес у Національному університеті „Львівська політехніка”. Деякі з наведених у роботі алгоритмів, а саме: формування множини замовлень на проведення навчальних занять, покрокового формування розв’язку слабоструктурованої задачі укладання розкладу та розподілу ресурсів, - було використано при проектуванні програмно-алгоритмічного комплексу першої черги підсистеми „Розклад” інформаційної системи Національного університету „Львівська політехніка”. Дослідна експлуатація проводилася на повній множині даних: 5880 замовлень на проведення занять для 630 навчальних груп. При дослідній експлуатації було розміщено 97,5% загальної кількості замовлень на заняття.

У додатку наведено форми розроблених тест-опитувань та проведення попарних порівнянь, модулі функціонального меню ІС, формування множини замовлень та пошуку аудиторії, наведено документи про впровадження результатів дисертаційної роботи.

Висновки

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

1. Запропоновано формалізовану постановку задачі укладання циклічних семестрових розкладів навчальних занять, що органічно поєднує як розроблені нові, так і наявні моделі.

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

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

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

5. Для побудови інтегрованої оцінки варіанту призначення та розподілу ресурсів розроблено систему оптимізаційних показників, а також принципи побудови тест-опитувань та отримання таблиць переводу початкових балів у нормалізовану шкалу для кожного з показників критеріїв оптимізації слабоструктурованої задачі укладання розкладу та розподілу ресурсів.

6. Для опрацювання введеної експертами інформації запропоновано алгоритм опрацювання тверджень експертів.

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

8. Удосконалено та експериментально досліджено алгоритми формування та упорядкування вхідної інформації із застосуванням пріоритетів. Для побудови інформаційної складової, застосувавши CASE-засоби, створено її структуру, реляційну базу даних слабоструктурованої задачі формування розкладу і розподілу ресурсів описано на логічному рівні.

9. Розроблено та експериментально досліджено комплекс математичних та програмних засобів автоматизації підготовки та ведення інформаційно-довідкової бази даних, яка реалізована засобами сучасних СУБД.

Результати експериментальних досліджень проектування розкладу навчальних занять, запропонованих у дисертації методів та засобів розв’язання слабоструктурованої задачі формування розкладу та розподілу ресурсів, є кращим, ніж розклад, що складався традиційним способом, за такими показниками:

· з розкладу виключено ситуації, що не допускаються або заважають проведенню занять (накладки за викладачами, групами або аудиторіями);

· скорочення кількості „вікон” у навчальних груп;

· покращується якість засвоєння навчального матеріалу при врахуванні функції інформаційної сприйнятливості на заняттях як протягом одного дня, так і всього навчального тижня;

· покращується якість завантаження викладача як упродовж одного дня, так і всього навчального тижня;

· зростає ефективність використання аудиторного фонду.

При дослідній експлуатації було розміщено 97,5% загальної кількості замовлень на проведення навчальних занять, тоді як у відомих розв’язках цей відсоток не перевищує 95%.

Список опублікованих праць

1. Верес О.М. Алгоритм укладання розкладу навчальних занять у ВНЗ // Інформаційні системи та мережі. Вісник ДУ “Львівська політехніка”. -1998. -№330.-С.40-51.

2. Верес О.М. Постановка задачі та система вимог до укладання розкладу навчальних занять у ВЗО // Інформаційні системи та мережі. Вісник ДУ “Львівська політехніка”. -1999. -№383.-С.18-23.

3. Верес О.М. Метод комп’ютерного проектування розкладу навчальних занять // Комп’ютерні системи проектування: Теорія і практика. Вісник ДУ “Львівська політехніка”. -1999. -№373. -С.210-214.

4. Верес О.М. Побудова множини критеріїв оптимізації укладання розкладу навчальних занять у ВЗО // Інформаційні системи та мережі. Вісник Національного університету “Львівська політехніка”. -2000. -№406. -С.59-65.

5. Верес О.М. Алгоритми розподілу основних ресурсів під час укладання розкладу навчальних занять // Комп’ютерні системи проектування: Теорія і практика. Вісник Національного університету “Львівська політехніка”. -2001. -№415. -С.176-179.

6. Верес О.М. Застосування психодіагностичних процедур в задачах укладання розкладу навчальних занять // Комп’ютерна інженерія та інформаційні технології. Вісник Національного університету “Львівська політехніка”. -2001. -№433. -С.225-233.

7. Верес О.М. Підтримання прийняття рішень в системі укладання розкладів вищого навчального закладу // Радиотехника и информатика. ХНУРЭ. -2001. -№3. -С.108-110.

8. Пасичник В.В., Верес О.М., Копчак О.И. Реализация процессов проектирования реляционнх баз даннх средствами язка ПРОЛОГ // Контрольно-измерительная техника. Респ.межведом. науч.технич. сборник. Львов, Вища школа. -1988. -№44.-С.85-90.

9. Пасичник В.В., Верес О.М., Копчак О.И. Реализация процессов проектирования реляционнх баз даннх средствами язка ПРОЛОГ // Контрольно-измерительная техника. Респ.межведом. науч.технич. сборник. Львов, Вища школа. -1989. №45.-С.104-111.

10. Верес О.М., Куріленков В.І., Лопатинський І.Є. Застосування комп’ютерних технологій при прийомі до ВЗО // Інформаційні системи та мережі. Вісник ДУ “Львівська політехніка”. -1999. -№383. -С.24-34.

11. Верес О.М. Метод комп’ютерного проектування розкладу навчальних занять // Тези доповідей V-ої Міжнародної науково-технічної конференції “Досвід розробки і застосування САПР в мікроелектроніці” CADSM’99. -1999. -С.178-179.

12. Верес О.М. Алгоритми розподілу основних ресурсів під час укладання розкладу навчальних занять // Тези доповідей VI-ої Міжнародної науково-технічної конференції “Досвід розробки та застосування приладо-технологічних САПР в мікроелектроніці” CADSM 2001. -2001. -С.263-264.

Анотація

Верес О.М. .-Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. -Національний університет „Львівська політехніка”, Львів, 2002.

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

Ключові слова: теорія розкладів, математичне моделювання, системний аналіз, слабоструктурованість, критерій, тест-опитування, експертні методи.

Аннотация

Верес О.М. Методы и средства решения слабоструктурированных задач формирования расписаний и распределения ресурсов.-Рукопись.

Диссертация на соискание научной степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы.-Национальный университет „Львовская политехника”, Львов, 2002.

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

Ключевые слова: теория расписаний, математическое моделирование, системный анализ, слабоструктурированность, критерий, тест-опрос, экспертные методы.

Abstract

Veres O.M. Methods and Means of Solving Semistructured Problems of Time-table Formation and Resources Distribution. – Manuscript.

Thesis for a degree of candidate of technical science on specialty 01.05.02 – Mathematical Modeling and Methods of Calculation. – Lviv National Polytechnic University, Lviv, 2002.

The analysis that has been carried out in the field of information science, theory of time-tables, decision-making systems, probability theory, theory of systems, artificial intelligence systems and fuzzy systems shows that there are a number of unsolved problems, namely:

· theory of time-tables is a developed discipline, in classical works of which problems allowing for quite different restrictions were formally set up; at the same time, immediate solution of the practical problems using these models proves to be impossible both due to their great dimension and NP-complexity and due to the necessity to take into consideration both formal and qualitative criteria and limitations in practical tasks;

· one of the features of the existing works in the sphere of decision-making on condition of weak structuredness is existence of different approaches and insufficiency of their theoretical substantiation;

· at present, issues of solving semistructured tasks are being treated within the scope of separate scientific disciplines in the range from system analysis to theory of optimization, which leads to fragmentary, patchy researches without a common approach;

· problems of dependence of the quality of solutions obtained on the structural characteristics and level of environment specificity have not been sufficiently studied;

· issues of presenting the system of DSS advantages have not been investigated adequately.

The objective of the work is theoretical substantiation of methods and means of solving semistructured tasks of time-table formation and resources distribution, practical development of a system of algorithms and programs for compiling classes’ time-tables.

A theoretical generalization and a new solution of the scientific problem have been presented in the thesis, which is revealed in development of a new approach to modeling time-tables and resources distribution as a semistructured task.

This improved formalized statement of the task of forming cyclic semester time-tables of classes organically combines both new models and the conventional ones.

A method of step-by-step decision formation with the movement of events appointed earlier, which is a new decision among the known solutions of the task of forming cyclic semester time-tables of classes, has been developed and studied in the work.

Under conditions of weak structuredness, the set of DSS advantages is not homogeneous. It comprises: a) direct and comparative assessments; b) assessments by different scales of measurements; c) accurate, probabilistic, qualitative or linguistic assessments. Therefore, in contrast to the conventional solutions, a number of different methods of decision making have been used for processing this information, namely: decomposition methods of theory of utility for aggregating criterion estimates into the assessment of integrated utility; methods based on determining weighting coefficients of value for aggregating individual strong points of experts into a consistent group advantage; questionnaires and other methods of psychodiagnostics for studying and constructing sets of indexes’ values.

A system of optimization indexes as well as principles of making up questionnaires and compiling tables for transformation of initial scores into the normalized scale for each of the optimization criteria’ indexes of the semistructured task of time-table formation and resources distribution have been developed for building up the integrated assessment of an assignment variant and resources distribution. The method of weighting coefficients of value, a version of the methods of peer review, has been used in the work to build up a set of weighting coefficients of the indexes. An algorithm for processing experts’ judgements has been devised to process information input by experts. It consists of base operations for mutual transformations and comparisons, and for implementation of statistical processing of collected information.

Algorithms for distributing main resources of the task of time-table formation, i.e. appointing a teacher and a classroom to carry out a planned class, have been proposed and experimentally investigated. Algorithms for forming and ordering input information arrays, using priorities, have been improved and studied. In order to build up the information element, using CASE-tools, the structure of the former has been described, and the relational database of the semistructured task of time-table formation and resources distribution has been described at the logical level. A system of mathematical and software tools for automation of preparing and inputting I&R database, realized with the help of the modern DBMS tools, has been devised and studied experimentally.

Results of the research of classes’ time-table design, using methods and tools of solving the semistructured task of time-table formation and resources distribution proposed in the thesis, surpass the conventionally-built time-table by the following indexes:

· elimination of situations that are unacceptable or impede classes conduction (lack of coordination with respect to teachers, academic groups and classrooms);

· reduction of the number of gaps for academic groups;

·