Те, що ви тут прочитаєте в більшості своїй нісенітниця. Проте в деяких місцях на мою думку присутні здорові думки, на жаль таких місць вийшло не так вже й багато (Не думайте здавати це там, де проблемами теорії розкладів займаються серйозно.
Тим, хто захоче написати що -небудь краще цього, настійно рекомендую почитати книгу Ху. Т. "Цілочисельне програмування і потоки в мережах", крім цього мабуть варто почитати лекції ВМиК з теорії оптимізації Н. М. Новікової (де це в инете лежить, не пам'ятаю).
Зараз активно займаюся проблемами теорії оптимізації, так що кому теж цікава ця тема, то завжди радий поспілкуватися. Пишіть [email protected].
Зміст
Введення 8 < br>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. Формулювання задачі складання рапісанія в застосуванні до розкладу навчальних занять.
Загальна теорія розкладів припускає, що всі обслуговують пристрої
(або процесори) не можуть виконувати в даний момент часу більш одногозавдання, що для розкладу учбових занять не є достатнім, якщо вяк процесор при розподілі завдань взяти навчальну аудиторію.
Так в деяких випадках в одній аудиторії можуть проводитися заняття з більшніж однією групою одночасно, наприклад загальні лекції для декількохпотоків.
Тому при перенесенні загальної теорії розкладів на розклад навчальнихзанять були зроблені наступні допущення:
- всі процесори (тобто в разі навчального розкладу - аудиторії) мають місткість - деяке число C? 1. Місткість процесора визначає кількість завдань, які він може одночасно
"обробляти" в даний момент часу (у відношенні непоодинокими процесорів було б цікавим розглянути варіант, коли як процесор виступає не аудиторія, а викладач, а як завдання - потік з однієї або більше навчальних груп, з якими він працює);
- як безлічі завдань для розподілу виступають навчальні заняття викладача з навчальними групами;
- модель часу в системі є дискретної; весь розподіл передбачається періодично повторюються протягом деякого тимчасового інтервалу;
- всі завдання виконуються за однаковий час, який приймається за одиницю дискретизації тимчасового інтервалу;
- завдання мають належність до об'єктів, у якості яких виступають навчальні групи і викладачі.
У підсумку, формулювання задачі складання розкладу навчальних занятьзвучить наступним чином: "Для заданого набору учбових аудиторій (у даномувипадку під навчальною аудиторією розуміється широке коло приміщень, у якихпроводяться навчальні заняття (від комп'ютерної аудиторії до спортивного залу))і заданого набору часових інтервалів (тобто по суті, уроків або навчальнихпар) побудувати такий розподіл учбових занять для всіх об'єктів
(вчителі та навчальні групи), для якого вибраний критерій оптимальностіє найкращим ".
1.2. Аналіз існуючого ПЗ
На даний момент часу сектор ринку ПЗ систем складання розкладузанять представлений великою кількістю різних програмних продуктів. Утаблиці 1. представлені лише деякі з відомих мені.
У силу об'єктивних причин система складання розкладу у вузі
(мається на увазі великий державний вуз) обов'язково повиннареалізовувати ряд основних функцій:
- врахування побажань викладачів;
- закріплення обов'язкових аудиторій;
- вказівка бажаних аудиторій;
- облік переходу між корпусами;
- об'єднання груп в потоки з будь-якої сукупності дисциплін;
- розбиття на підгрупи;
- після складання розкладу при необхідності здійснювати замінувикладачів або змінювати час проведення заняття.
Крім цього існують ще й специфічні для кожного вузу вимоги дофункціональними можливостями програмного продукту.
Можливості на мій погляд найбільш популярних на російському ринкупрограмних продуктів наведено у додатку 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. Введемо врозгляд булеві значення і:
=
Навчальне навантаження викладачів планується до складання розкладузанять, внаслідок чого на даному етапі величини і можна вважатизаданими. Для кожного викладача p, p = 1, ..., P, задана також йогоаудиторні навантаження - Np годин на тиждень.
Аудиторний фонд
Заняття кожного потоку можуть проводитися тільки в певнихаудиторіях (наприклад, практичні заняття з інформатики можуть проводитьсятільки в дисплейних класах). Нехай:
(A1r) - безліч аудиторій для лекцій на потоці r;
(A2r) - безліч аудиторій для практичних занять на потоці r;
A1r -- число елементів множини (A1r);
A2r - число елементів множини (A2r);
A1r + A2r - число аудиторій об'єднання множин (A1r)? (A2r).
Аудиторний фонд визначається до початку складання розкладу, томубезлічі можна вважати заданими.
2.1.2. Змінні
Завдання складання розкладу полягає у визначенні для кожноїлекції (на потоці) і практичного заняття (в групі), дня тижня і пари вЦього дня з урахуванням виконання конструюються нижче обмежень і мінімізаціїдеякої цільової функції.
Введемо наступні шукані булеві змінні:
=
=
У разі складання розкладу для груп вечірньої форми навчання J = 2.
Узагальнення моделі на всі форми навчання см. [1], стор 669.
2.1.3. Обмеження
Для кожної групи kr повинні виконуватися всі види аудиторної роботи впротягом тижня:
У будь-який день t на кожній парі j для кожної групи kr може проводитисяне більше одного заняття:
Кожні лекція sr і практичне заняття qkr відповідно для всіхпотоків r і всіх груп kr можуть проводитися не більше одного разу в будь-якійдень t:
Якщо змінні і пов'язують всі види занять з часом їхпроведення, то твори і пов'язують час проведення з ім'ямвикладача.
У кожен день t і в кожній парі j викладач p може вести не більшеодного заняття по одній дисципліні на одному потоці або в одній групі:
Кожен викладач p протягом тижня повинен провести аудиторнізаняття:
Нарешті, в кожен день на кожній парі число лекцій і практичнихзанять не повинно перевищувати наявний у вузі аудиторний фонд:
Крім того, для всіх сукупностей пересічних множин (A1r) і
(A2r) повинні виконуватися умови:
представленими співвідношеннями вичерпуються безумовні обмеження, зякими завжди вважаються при складанні розкладу. Можуть, однак бути іспецифічні умови, перш за все проведення окремих видів роботи з
"Верхній" або по "нижній" тижня (тобто одна година на тиждень). Чи невиключені й інші спеціальні умови, але для спрощення моделі вони нерозглядалися.
2.1.4. Цільова функція
Щоб повноцінно вести наукову, навчально-методичну роботу, готуватисядо занять, викладач вузу повинен мати вільний час. Ця умованедостатнє, але необхідна. Очевидно, що вільний час він повиненрозташовувати не в "рваному" режимі, яким, наприклад, є "вікна" міжзаняттями зі студентами, а по можливості в повністю вільні робочідні. Цьому еквівалентна максимізація аудитрной навантаження викладачів уті дні, коли вони її мають (див. (5)). Однак при цьому претензії навільний час у викладачів нерівні, тому що у них різний творчийпотенціал. Тому необхідно ввести вагові коефіцієнти, за допомогоюяких має враховуватися відповідний статус викладача - йоговчені ступені і звання, посада, науково-громадськаактивність і т.п. У деяких випадках можна на підставі експертних оціноквикористовувати індивідуальні вагові коефіцієнти, що враховують іншіфактори.
Отже, виберемо критерій якості складання розкладу занять у виглядімаксимізації зваженого числа вільних від аудиторної роботи днів для всіхвикладачів, що за умови фіксованої довжини робочого тижняеквівалентно максимального сукупного ущільнення аудиторного навантаження.
Розглянемо вираз для величини аудиторного навантаження в день tвикладача p:
Вводяться обмеження виду:
де M - довільне позитивне достатньо велике число; --шукана булева змінна.
З (10) випливає, що якщо, то = 1, і якщо, то
= 0.
З урахуванням зазначеного вище змістовного сенсу критерію оптимізації вдодаткових обмеженнях (10), а також вводячи вагові коефіцієнтистатусу викладача, одержуємо шуканий критерій оптимальності:
Введена цільова функція не є єдино можливою. Введенняінших цільових функцій не змінює обмежень математичної моделі іметодів вирішення задачі, але може істотно вплинути на результатиобчислень.
2.2. МЕТОДИ вирішення поставлених завдань
Поставлена в попередньому пункті завдання максимізації лінійної цільовоїфункції при заданій системі обмежень є задачею лінійногоцілочисельного булева програмування, оскільки всі коефіцієнтиобмежень цілочисельних в силу дискретності вихідних даних задачі; крімцього шукані змінні математичної моделі можуть приймати тільки двазначення. На даний момент часу існує кілька можливих методіввирішення такого роду завдань.
В [3] - [8] описані методи впорядкованої індексації та модифікованихпозначок, засновані на Лагранжа декомпозиції вихідної моделі на низкуоднорядковий завдань, що вирішуються відповідно методами впорядкуєіндексації або модифікованих позначок. На жаль кількість операційкожного з методів не допускає поліноміальною оцінки; крім того,розмірність таблиці наборів (проміжних значень) методів різкозростає при збільшенні розмірності розв'язуваної задачі, що неприпустимо внашому випадку. Можливо, зміна алгоритму декомпозиції під конкретнуматематичну модель дозволить зменшити розмірність таблиць, але поки такогоалгоритму не існує.
У зв'язку з цим як методів рішення були вибрані описані в [2]модифікації симплекс-методу для випадку завдання цілочисельного лінійногопрограмування. У загальному випадку кількість операцій симплекс-методу недопускає поліноміальною оцінки (був навіть показаний клас задач, для якихкількість операцій становить O (en)), але для випадку нашого завдання середнєчисло операцій допускає поліноміальних оцінку: O (n3m1/(n-1)) (n --кількість змінних; m - кількість обмежень).
2.2.1. ПОВНІСТЮ Цілочисельне АЛГОРИТМ
Цей алгоритм названий повністю цілочисельності, тому що якщо вихіднатаблиця складається з цілочисельних елементів, то всі таблиці, що виходять впроцесі роботи алгоритму, містять тільки цілочисельні елементи. ПодібноДвоїстий симплекс-метод, алгоритм починає працювати з двоякодопустимої таблиці. Якщо ai0 (i = 1, ..., n + m; ai0 - коефіцієнтицільової функції) - невід'ємні цілі, то задача вирішена. Якщо для будь -якого рядка ai0
