Розробка математичної моделі та ВО для завдань складання розкладу

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

Тим, хто бажає написати щось краще цього, настійно рекомендую читати книжки Ху. Т. «Целочисленное програмування і потоки у мережах «, крім цього мабуть стоїть почитати лекції ВМиК з теорії оптимізації М.М. Новикової (де це у інеті лежить, не помню).

Зараз активно займаюся проблемами теорії оптимізації, отже кому теж цікава цю тему, то завжди радий поспілкуватися. Пишіть [email protected].

Содержание Введение 8 1. Опис технологічної області 10 1.1. Формулювання завдання складання розкладу 10 1.1.1. Загальна формулювання завдання складання розкладів 10 1.1.2. Формулювання завдання складання раписания стосовно розкладу уроків. 11 1.2. Аналіз існуючого ПО 12 1.3. Постановка завдання. 15 2. Розробка математичну модель і практична реалізація системи автоматичного складання розкладу 16 2.1. Математична модель розкладу у ВНЗ 16 2.1.1. позначення 16 2.1.2. Змінні 18 2.1.3. Обмеження 19 2.1.4. Цільова функція 21 2.2. Методи рішення поставленого завдання 22 2.2.1. Повністю целочисленный алгоритм 23 2.2.2 Прямий алгоритм целочисленного програмування 28 2.2.3. Техніка отримання початкового припустимого базису 32 2.3. Особливості практичної реалізації системи 36 2.3.1. Вибір моделі 36 2.3.2. Опис вхідний інформації 39 2.3.3. Розробка інформаційного забезпечення завдання 41 2.3.4. Особливості формування обмежень математичну модель завдання складання розкладу 44 2.4. Результати роботи програми 45 2.5. Аналіз отриманих результатів 49 Висновки 50 Література 51 Додаток 1. Можливості програмних продуктів систем складання розкладів. 52 Додаток 2. Лістинг програмного модуля методів виконання завдання автоматичного складання розкладу 61.

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

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

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

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

1. ОПИС ТЕХНОЛОГІЧНОЇ ОБЛАСТИ.

1.1. Формулювання завдання складання расписания.

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

1.1.1. Загальна формулювання завдання складання расписаний.

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

1.1.2. Формулювання завдання складання раписания стосовно розкладу навчальних занятий.

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

Тому, за перенесення загальної теорії розкладів на розклад навчальних занять було зроблено такі допущения:

— все процесори (тобто. у разі навчального розкладу — аудиторії) мають місткість — певна кількість З? 1. Місткість процесора визначає кількість завдань, який може одновременно.

" обробляти «в момент часу (щодо неединичности процесорів було б цікавим розглянути варіант, коли як процесора виступає не аудиторія, а викладач, а ролі завдання — потік з одного чи більш навчальних груп, із якими работает);

— як безлічі завдань задля розподілення виступають навчальні заняття викладача з навчальними группами;

— модель часу у системи є дискретної; все розподіл передбачається періодично повторюваним протягом деякого тимчасового интервала;

— все завдання виконуються за однаковий час, яке приймається за одиницю дискретизації тимчасового интервала;

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

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

1.2. Аналіз існуючого ПО.

На цей час часу сектор ринку ПО систем складання розкладу занять представлений велику кількість різних програмних продуктів. У таблиці 1. представлені лише окремі з відомих мне.

[pic].

[pic].

З огляду на об'єктивних причин система складання розкладу у ВНЗ (мають на увазі великий державний вуз) неодмінно повинна реалізовувати ряд основних функций:

— облік побажань преподавателей;

— закріплення обов’язкових аудиторий;

— вказівку бажаних аудиторий;

— облік переходу між корпусами;

— об'єднання груп у потоки за якою сукупності дисциплин;

— розбивка на подгруппы;

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

Можливості мій погляд найпопулярніших російському ринку програмних продуктів наведені у додатку 1.

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

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

1.3. Постановка задачи.

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

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

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

2.1. Математична модель розкладу в вузе.

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

2.1.1. Обозначения.

ГРУППЫ.

У вузі є N навчальних груп, об'єднаних в R потоків; r — номер потоку, r = 1, …, R, kr — номер навчальної групи серед r, kr = 1, …, Gr.

Розбивка на груп на потоки здійснюється з принципов:

1. Використання двома групами однієї й тієї ж аудиторного фонду на свої лекцій автоматично передбачає приміщення в 1 поток.

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

2. Группа (или значна її частина), як одиниця процесу у ВНЗ, може укладати різні потоки, але тільки за одному разів у кожен із них.

3. Кількість потоків не лимитируется.

ЗАНЯТИЯ.

Заняття проводять у робочі дні у полуторочасовые інтервали, які називатимемо парами.

Означимо: t — номер робочого дня тижня, t Є Tkr, где.

Tkr — безліч номерів робочих днів групи kr; j — номер пари, j = 1 ,…, J;

J — загальна кількість пар.

З кожної навчальної групою kr потоку r протягом тижня, відповідно до навчальному плану, проводиться Wkr занять, у тому числі Sr лекційних і Qkr практичних. Означимо: sr — номер дисципліни у списку лекційних занять для потоку r, sr = 1 ,…, Sr; qkr — номер дисципліни у списку практичних занять для групи kr, qkr = 1 ,…, Qkr.

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

ПРЕПОДАВАТЕЛИ.

Нехай p — номер (ім'я) викладача, p = 1 ,…, P. Введемо в розгляд булевы значення [pic]и [pic]:

[pic].

[pic]=.

Навчальне навантаження викладачів планується до складання розкладу занять, унаслідок чого поки що величини [pic]и [pic]можно вважати заданими. До кожного викладача p, p = 1 ,…, P, задана також наявність його аудиторне навантаження — Np годин на неделю.

АУДИТОРНИЙ ФОНД.

Заняття кожного потоку можуть відбуватися лише у певних аудиторіях (наприклад, практичні заняття з інформатики можуть проводиться лише у дисплейных класах). Пусть:

{A1r} - безліч аудиторій до лекцій на потоці r;

{A2r} - безліч аудиторій для практичних занять на потоці r;

A1r — число елементів безлічі {A1r};

A2r — число елементів безлічі {A2r};

A1r + A2r — число аудиторій об'єднання множин {A1r}?{A2r}.

Аудиторний фонд визначається на початок складання розкладу, тому безлічі вважатимуться заданными.

2.1.2. Переменные.

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

Введемо такі шукані булевы переменные:

[pic]=.

[pic]=.

Що стосується складання розкладу для груп вечірньої форми навчання J=2. Узагальнення моделі попри всі форми навчання див. [1], стор. 669.

2.1.3. Ограничения.

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

[pic].

У будь-якій день t з кожної парі j кожної групи kr можна проводити трохи більше одного занятия:

[pic].

Кожні лекція sr і практичне заняття qkr відповідно всім потоків r і батько всіх груп kr можуть відбуватися трохи більше разу на будь-який день t:

[pic].

Якщо перемінні [pic]и [pic]увязывают всі види занять із часом їх проведення, то твори [pic]и [pic]связывают час проведення ім'ям преподавателя.

У середньому кожен день t в кожній парі j викладач p може вести трохи більше одного заняття з однієї дисципліни однією потоці чи однієї группе:

[pic].

Кожен викладач p протягом тижня повинен провести аудиторні занятия:

[pic].

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

[pic].

[pic].

З іншого боку, всім сукупностей від перетинання множин {A1r} і {A2r} їх необхідно виконувати условия:

[pic] [pic].

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

2.1.4. Цільова функция.

Щоб повноцінно вести наукову, навчально-методичну роботу, готуватися до занять, викладач вузу, має мати вільний час. Це умова недостатнє, але необхідне. Вочевидь, що вільний час він має розташовувати над «рваному» режимі, яким, наприклад, є «вікна» між заняттями зі студентами, а, по можливості у повністю вільні робочі дні. Цьому еквівалентна максимізація аудиторного навантаження викладачів в дні, що вони її мають (див. (5)). Однак цьому претензії на вільний час у викладачів нерівні, тому що в них різний творчий потенціал. Тому необхідно провести вагові коефіцієнти, у вигляді що має враховуватися відповідний статус викладача — його вчені й звання, зайнята посаду, научно-общественная активність тощо. У окремих випадках можна виходячи з експертні оцінки використовувати індивідуальні вагові коефіцієнти, враховують інші факторы.

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

Розглянемо вираз для величини аудиторного навантаження щодня t викладача p:

[pic].

Вводяться обмеження вида:

[pic].

где M — довільне позитивне досить багато; [pic] - бажана булева переменная.

З (10) випливає, що й [pic], то [pic] = 1, і якщо [pic], то [pic] = 0.

З урахуванням вищезазначеного змістовного сенсу критерію оптимізації в додаткових обмеженнях (10), і навіть вводячи вагові коефіцієнти статусу викладача [pic], отримуємо шуканий критерій оптимальности:

[pic].

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

2.2. МЕТОДИ РІШЕННЯ ПОСТАВЛЕНОЇ ЗАДАЧИ.

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

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

У зв’язку з цим у ролі методів рішення було обрані достойні [2] модифікації симплекс-метода для випадку завдання целочисленного лінійного програмування. У випадку кількість операцій симплекс-метода не допускає полиномиальной оцінки (було навіть показаний клас завдань, котрим кількість операцій становить O (en)), але для випадку нашої завдання середнє кількість операцій допускає полиномиальную оцінку: O (n3m1/(n-1)) (n — кількість змінних; m — кількість ограничений).

2.2.1. ПОВНІСТЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ.

Цей алгоритм названо повністю целочисленным, бо якщо вихідна таблиця складається з цілочислових елементів, усі таблиці, отримувані в процесі роботи алгоритму, утримують тільки целочисленные елементи. Подібно двойственному симплекс-методу, алгоритм починає працювати з двояко припустимою таблиці. Якщо ai0 (і = 1 ,…, n+m; ai0 — коефіцієнти цільової функції) — неотрицательные цілі, то завдання виконане. Якщо якийнибудь рядки ai0.