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

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

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

Розглянемо розклад У початковий момент часу T = 0, процесор починає обробку завдання , процесор - завдання , А процесор - завдання . процесор закінчує виконання завдання в момент часу
, Поки процесори і все ще працюють над своїми початковими завданнями. при T = 3процесор знову закінчує завдання і починає обробляти завдання , Яке завершується в момент T = 4. Тоді він починає виконувати останнє завдання . Процесори і закінчують завдання при T = 5, Але, так як список Lпорожній, вони зупиняються. процесор завершує виконання завдання при T = 12. Розглянуте розклад проілюстровано на рис.1. тимчасової діаграмою, відомої як схема Ганта. Очевидно, що розклад не оптимальне. Можна «підібрати», наприклад, розклад, яке дозволяє завершити всі завдання за T * = 8одиниць часу (рис.2.).

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

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

література

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест

Алгоритми: побудова й аналіз. М .: МЦНМО, 2000..

2. Д.Кнута Мистецтво програмування, том 1. Основні алгоритми. Уч. сел. М.: Изд. Будинок "Вільямс", 2000.

3. Вірт Н. Алгоритми і структури даних .: Пер. З англ. - М .: Світ, 2001..

4. Хусаїнов Б.С. Структури і алгоритми обробки даних. приклади на

мові Сі. Учеб. посібник. М: Фінанси і статистика, 2004.

5. А. Ахо, Дж.Хопкрофт, Дж.Ульман, Структури даних і алгоритми М: СПб: Київ: Вільямс, 2001 р.

Запанувала тиша, яку порушив сам Швейк, зітхнувши:
- ... На військовій службі повинна бути дисципліна - без неї ніхто б і пальцем для діла не ворухнув. Наш обер-лейтенант Макіївці завжди говорив: «Дисципліна, бовдури, необхідна. Не будь дисципліни, ви б, як мавпи, по деревах лазили. Військова служба з вас, йолопи, людей зробить! » Ну, хіба це не так? Уявіть собі парк, скажімо, на Карлаку, і на кожному дереві сидить солдат без дисципліни. Це мене страшенно лякає.
Ярослав ГашекПригоди бравого солдата Швейка

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

Постановка задачі

Скажу коротко.

• При проведенні заняття можуть бути відсутні будь-які його учасники, наприклад, на засіданні кафедри студенти, як правило, не приходять або студенти пішли на військову кафедру(У них свій розклад), а для того роду занять немає дисципліни, викладача і аудиторії.
• Як правило, необхідною вимогою ставиться безперервність (відсутність вікон) у студентів і бажано у викладачів.
• Розклад може складені на семестр / полсеместра по тижнях, за двома тижнями та чисельник / знаменник (непарна тиждень / парна тиждень). Також буває розклад на місяць.
• Заняття повинна мати можливість постановки в ручному режимі (іншими словами в редакторі). Наприклад вчена рада або пара великого начальника і навіть заняття просто хорошу людину.
• Повинна бути система заборон для всіх учасників заняття. Наприклад, зараз практично всі викладачі підробляють на стороні (інакше не проживеш) або аудиторний фонд розділений між факультетами та після обіду в частину аудиторій заняття ставити не можна.
• Наявність витончених побажань викладачів, одному став 5 пар в день, щоб звільнити інші дні, а іншому більше двох пар в день не ставити, він перевтомлюватися, а якщо лекцію, то одну пару і обов'язково 2 або 3-ю пару.
• Заняття в різних корпусах, які потребують для переходу час більше, ніж час перерви між заняттями. Природно і умова мінімізації переміщень.

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

Картинка взята звідси.

генетичний алгоритм

Чисто риторично, повторю основні етапи генетичного алгоритму:

1. Задати цільову функцію (пристосованості) для особин популяції
2. Створити початкову популяцію
3. (Початок циклу)
   1. Розмноження (схрещування)
   2. мутирование
   3. Обчислити значення цільової функції для всіх особин
   4. Формування нового покоління (селекція)
   5. Якщо виконуються умови зупинки, то кінець циклу, інакше (початок циклу).

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

1. По набору генів рішення шуканої завдання повинно будується швидко і однозначно.
2. При схрещуванні нащадок повинен наслідувати характерні риси батьків.

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

Алгоритм складання розкладів

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

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

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

Схрещування можна організувати декількома способами. Наприклад один з них. Нехай маємо наступні гени

3 1 2 5 6 4 7
2 3 5 7 1 4 6

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

_ * * * * _ _ Для 1 заняття
* * * _ _ _ _ Для 2 заняття
* * _ _ _ _ _ Для 3 заняття
_ _ _ _ _ * _ Для 4 заняття
_ _ * * _ _ _ Для 5 заняття
_ _ _ _ * * * Для 6 заняття
_ _ _ * * * * Для 7 заняття

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

1 позиція (2, 3)
2 позиція (1, 2, 3)
3 позиція (1, 2, 5)
4 позиція (1, 5, 7)
5 позиція (1, 6, 7)
6 позиція (4, 6, 7)
7 позиція (6, 7)

Для побудови рішень можна використовувати наступний алгоритм. Спочатку будемо ставити ті номери занять, які рідше зустрічаються. Якщо їх впорядкувати за зростанням, то матимемо
1 раз 4
2 рази 3, 5
3 рази 2, 6
4 рази 1, 7
Отже спочатку ставимо 4 заняття на 6-ту позицію, потім 3 або 5 на позиції (1, 2) або (3, 4) відповідно. На кожному кроці можна кидати коробок сірників. В результаті можна отримати наприклад такі кроки для алгоритму схрещування

* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6

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

Мутацію можна організувати досить просто, випадкової перестановкою номерів занять.

висновок

Це продовження, в деякому сенсі, моїх постів Програма щодо складання розкладу занять у ВНЗ і Розрахунок навантаження по кафедрі.

Повторно пропоную наступні рішення (малюнок).

• GUI на PyQt або PySide
• СУБД PosgreSQL (у мене тут готове приблизно на 80%), в ній крім самого розкладу ще заявки і навантаження викладачів, навчальні плани і ще багато чого (з цією метою опублікую один або кілька топіків)
• web інтерфейс на CherryPy + Cheetah (але це може обговорюватися)
• експорт будь-яких звітів (розкладів, карток навчальних доручень і т.д.) в форматі OpenDocument (ГОСТ ISO / IEC 26300-2010. Держстандарт Росії (01.06.2011)) за допомогою ODFPY
• алгоритми складання розкладу від мене (про це цей топік)
• постановка від мене
• для зацікавлених робота над спільним ядром
• для зацікавлених адаптація під власний ВНЗ і можливість гнучко все міняти, життя йде, а чиновники не дрімають

Дякуємо Всім хто відгукнувся, після обговорення цього топіка можна буде зі організуватися.

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

Прийнятність уроків і шкільний розклад

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

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

У правовому аспекті проблема складання шкільного розкладу знайшла відображення в нових гігієнічних вимогах до складання розкладу, які ґрунтуються на даних сучасних наукових досліджень биоритмологии розумової працездатності і таблиці труднощі предметів І.Г. Сівкова. Однак для заступника директора школи, який складає розклад, важливо не тільки знати, наскільки важкий предмет, але і представляти силу стомлюючого впливу уроків з того чи іншого предмету на стан здоров'я учнів. На жаль, таблиця труднощі І.Г. Сівкова зовсім не враховує такого компонента навчання, як втому предметів, яка в першу чергу впливає на здоров'я учня.

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

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

Таблиця 1

Орієнтовна шкала прийнятності предметів

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

У середній загальноосвітній школі№ 618 м Санкт-Петербурга ми отримали наступну шкалу прийнятності предметів (див. Таблицю 2).

Таблиця 2

Шкала прийнятності предметів

Алгоритм складання розкладу

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

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

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

При використанні автоматизованих програм доцільно виконувати розстановку предметів за допомогою автоматизованої програми поетапно на підставі запропонованого алгоритму. Як показує практика, дані програми можуть бути використані тільки як допоміжний інструмент для:

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

Після автоматизованого розподілу предметів (програма, як правило, розставляє від 40 до 70%) враховувати гігієнічні вимоги до розкладу уроків практично неможливо, так як доводиться не тільки доставляти залишилися нерасставленние предмети, а й істотно змінювати (до 60%) автоматизовану розстановку предметів за принципом «аби розставити».

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

Порядок зміни розкладу

Алгоритм коригування шкільного розкладу

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

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

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

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

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

Критерії гігієнічної оцінки шкільного розкладу

1. Кількість класів початкової школи – ______.

2. Кількість класів початкової і середньої школи - ___________.

3. Всього навчальних кабінетів, які використовуються для проведення уроків - ___________.

4. Наявність шкали прийнятності для свого освітнього закладу:

5. Облік шкали прийнятності предметів в шкільному розкладі:

6. Розподіл уроків на день для учнів:

7. Всі класи починають навчання з першого уроку:

8. Раціональне чергування предметів різної спрямованості і складності:

9. Дотримання в розкладі обліку працездатності учнів (в тижневої динаміці):

10. Раціональна розстановка уроків для вчителів:

11. Максимальна кількість уроків у вчителів в день:

а) до 4 уроків - у ____ вчителів - ______ (%);

б) 5 і 6 уроків - у ____ вчителів - _____ (%);

в) 7 уроків і більш - у ____ вчителів - ___ (%).

12. Методичний день є (вказати кількість вчителів):

а) з навантаженням до 24 годин на тиждень - у ____ вчителів;

б) з навантаженням від 25 до 30 годин на тиждень - у ___ вчителів;

в) з навантаженням понад 30 годин на тиждень - у ___ вчителів.

1. Підготувати набори з назвами предметів з 5-го по 11-й клас.
2. Учням роздати набори карток з назвами предметів і листки для відповідей.
3. Запропонувати вибрати картки з назвами тих предметів, які вивчаються в даному класі (по щоденнику).
4. Уточнити поняття «труднощі» предметів.
5. Запропонувати самостійно визначити труднощі кожного предмета шляхом ранжирування, тобто розкладання карток в порядку убування труднощі предмета (картки укладати зверху вниз, тобто на першому місці зверху - картка з найважчим предметом, нижче - менш важким і т.д.).
6. Отриманий розклад предметів записати на аркуші відповідей.
7. Після цього розібрати і уточнити поняття «втому» предметів.
8. Виконати аналогічну процедуру ранжування і записати отриманий розклад на аркуші відповідей.
9. Листи з відповідями зібрати і обробити (див. Форму зведеної таблиці нижче).

- де: mk - середній балпо предмету одного класу;

n - кількість класів в досліджуваній паралелі;

або за формулою:

- де: Mk - сума балів по предмету одного класу;

n - кількість учнів однієї паралелі, що беруть участь в дослідженні.

Наприклад, в паралелі 7-х класів є п'ять класів, взяли участь в діагностиці 130 осіб. Сума балів по російській мові в паралелі склала 469. Підставляємо в формулу числа:

Пор. б. пр. = (469/130) = 3,61 - середній бал з російської мови в паралелі 7-х класів склав 3,61, діти сприймають цей предмет як досить важкий.

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

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

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

Форма зведеної таблиці для обробки відповідей

Додаток 2

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

1 - найбільш сприятливі годинник; 10 - найбільш несприятливі.

6-7 - знижений рівень працездатності (малосприйнятливі годинник для проведення уроків).

8-10 - низький рівень працездатності (несприятливі годинник для проведення уроків).

Таблиця розподілу тижневого навантаження вчителя

додаток 3

Технологія виконання макета таблиці розкладу уроків

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

• 4 листа картону (товщина 1-2 мм, висота - 42 см, ширина - 22 см, висота рядків - 0,8 см, ширина стовпця - 1 см) *;
• 4 листа кольорового паперу (краще світлих тонів) щільністю 200 г / см і розмірами, аналогічними розмірами листів картону;
• широкий прозорий скотч;
• ледерин (паперовий вiнiл) для склеювання картону в папку (стрічки шириною 4-5 см; довжиною 49-50 см);
• клей ПВА (досить сильний, типу «сілакра»).

Алгоритм виконання макета

1. Склеить аркуші картону в «розкладачку»:

2. На одному аркуші кольорового паперу помістити всю необхідну інформацію для складання розкладу (помістити на лист картону № 1); приклад: таблиця на с. 27.

3. На двох наступних аркушах кольорового паперу накреслити сітку, по три дні на кожному аркуші, по 7 осередків на кожен день (помістити на 2-й і 3-й лист картону).

4. На 4-му аркуші розкреслити суцільну сітку без поділу на дні (осередки - аналогічних розмірів).

5. Готові розкреслені листи покрити скотчем, щоб при розрізах осередків не було розривів.

6. Зробити прорізи в осередках розміром від 0,5-0,6 см.

7. Приклеїти паперові листи по бічних частинах листів картону на готову «розкладачку». Макет готовий.

8. Окремо зробити різнокольорові бирки з літерою класу (5-й «А», 7-й «Г» і т.д.), кількість - з розрахунку навантаження 5- або 6-денний тижня + додатково на уроки, де класи діляться на підгрупи. Розмір бирки: ширина - 8 мм; висота - 15 мм.

9. Підготувати бирки будь-якого кольору без написів літер класу для розрахунку тижневого навантаження на кожного вчителя. Розміри: ширина 5 мм; висота 12-14 мм.

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

Інформація, необхідна для складання розкладу

___________ * Розміри аркуша картону індивідуальні, тому що в кожній школі різну кількість вчителів, різний режим роботи (5- і 6-денний навчальний тиждень). Ми пропонуємо розміри для розкладу з розрахунку 6-денного навчального тижня та школи, в якій працюють 50-55 вчителів.

Те, що ви тут прочитаєте в більшості своїй нісенітниця. Проте в деяких місцях на мою думку присутні здорові думки, на жаль таких місць вийшло не так вже й багато L Не здумайте здавати це там, де проблемами теорії розкладів займаються серйозно. Тим, хто захоче написати що-небудь краще цього, настійно рекомендую почитати книгу Ху. Т. "Цілочисельне програмування і потоки в мережах", крім цього мабуть варто почитати лекції ВМиК з теорії оптимізації Н.М. Новікової (де це в інеті лежить, не пам'ятаю). Зараз активно займаюся проблемами теорії оптимізації, так що кому теж цікава ця тема, то завжди радий поспілкуватися. Пишіть [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. Формулювання задачі складання рапісанія в застосуванні до розкладу навчальних занять.

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

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

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

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

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

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

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

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

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

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

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

Врахування побажань викладачів;

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

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

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

Об'єднання груп в потоки по будь-якої сукупності дисциплін;

Розбиття на підгрупи;

Після складання розкладу при необхідності здійснювати заміну викладачів або змінювати час проведення заняття.

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

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

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

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

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

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

Розклад складається з розрахунку не більше двох пар в день (що цілком підходить для випадку вечірньої форми навчання);

Всі пари проводяться в одному корпусі;

Завдання ставиться в термінах лінійного програмування;

Подальша декомпозиція моделі не проводиться;

Всі коефіцієнти моделі і шукані змінні цілочисельних;

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

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

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

2.1.1. позначення

У вузі є N навчальних груп, об'єднаних в R потоків; r - номер потоку, r = 1, ..., R, k r - номер навчальної групи в потоці r, k r = 1, ..., G r.

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

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

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

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

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

позначимо:

t - номер робочого дня тижня, t Є T kr, де

T kr - безліч номерів робочих днів для групи k r;

j - номер пари, j = 1, ..., J;

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

З кожної навчальної групою k r потоку r протягом тижня, згідно з навчальним планом, проводиться W kr занять, з яких S r лекційних і Q kr практичних. позначимо:

s r - номер дисципліни у списку лекційних занять для потоку r, s r = 1, ..., S r;

q kr - номер дисципліни у списку практичних занять для групи k r, q kr = 1, ..., Q kr.

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

ВИКЛАДАЧІ

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

Навчальне навантаження викладачів планується до складання розкладу занять, внаслідок чого на даному етапі величини і можна вважати заданими. Для кожного викладача p, p = 1, ..., P, задана також його аудиторне навантаження - N p годин в тиждень.

аудиторний фонд

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

(A 1 r) - безліч аудиторій для лекцій на потоці r;

(A 2 r) - безліч аудиторій для практичних занять на потоці r;

A 1 r - число елементів множини (A 1 r);

A 2 r - число елементів множини (A 2 r);

A 1 r + A 2 r - число аудиторій об'єднання множин (A 1 r) ∩ (A 2 r).

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

2.1.2. змінні

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

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

=

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

2.1.3. обмеження

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

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

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

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

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

Крім того, для всіх сукупностей пересічних множин (A 1 r) і (A 2 r) повинні виконуватися умови:

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

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

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

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

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

де M - довільне позитивне достатньо велике число; - шукана булева змінна.

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

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

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

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

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

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

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

2.2.1. ПОВНІСТЮ целочисленном АЛГОРИТМ

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

Нехай задана задача цілочисельного лінійного програмування:

максимізувати

за умов

Умови (12) можуть бути записані як

Припустимо, що для t = 0 (тобто для початкової таблиці) всі a ij - цілі і стовпці (j = 1, ..., n) - лексикографічно позитивні. Тоді всі стовпці протягом обчислень залишаються лексикографічно позитивними.

Перш ніж викласти спосіб отримання додаткового обмеження з виробляє рядки, введемо нове уявлення чисел. Нехай [x] позначає найбільше ціле число, яке не перевищує x. Для будь-якого числа y (позитивного або негативного) і позитивного можна записати:

де (r y - невід'ємні залишок від ділення без остачі y на). Зокрема, . Тому якщо, то і r = 1. Якщо, то і r = 0.

Введене додаткове нерівність має виконуватися при будь-якому цілому вирішенні задачі (12). Розглянемо деякий рівняння в t - таблиці (опускаючи індекс рядка) з a 0

де x - відповідна компонента вектора, а - поточні небазисних змінні. Можна висловити x, a 0 і a j, використовуючи введене вище уявлення (14):

Підставивши вирази (16) і (17) в (15) і переставивши члени, отримаємо:

Оскільки, і на змінні x і накладено вимога невід'ємності, ліва частина рівняння (18) завжди неотрицательна. Розглянемо вираз в правій частині, укладену в фігурні дужки. Коефіцієнти в цьому виразі є цілі числа, а змінні підпорядковані вимогу целочисленности. Тому все вираз в дужках має бути цілим. Позначимо його через s, тобто .:

.

Цілочисельна слабка змінна s є неотрицательной. Дійсно, якби s було негативним, тобто брало б значення -1, -2, ..., то множення на зробило б всю праву частину рівняння (18) негативною, в той час як ліва частина неотрицательна.

Розглянемо два випадки і. Для і. Підставляючи в рівняння (19) вираз для x з (15), отримаємо:

Рівняння (21) має виконуватися для будь-якого цілочисельного рішення задачі (12). Зауважимо, що якщо a 0 в рівнянні (21). Тому рівняння (21) може використовуватися в якості провідного рядка в симплекс-методі. Зокрема, завжди можна вибрати досить великим, так щоб ведучий елемент в рядку (21) став рівним -1, що дозволить зберегти цілочисельність таблиці. Вибір відповідного впливатиме на швидкість збіжності алгоритму. Перш за все опишемо сам алгоритм. В якості початкового необхідно взяти двояко допустиме рішення, яке можна отримати додаванням обмеження xn + m + 1 = M - x 1 - - ... - xn 0, де M - досить велика константа, і проведенням однієї ітерації з доданою рядком і з лексикографічно мінімальним стовпцем , взятими в якості ведучих. Алгоритм складається з наступних кроків:

Крок 0. Почати з двояко допустимої матриці A 0 в рівнянні (13), елементи якої - цілі числа (матриця A 0 може містити і нецілі елементи, про це див., Стор. 306).

Крок 1. Серед рядків з a i 0 0 (i = 1, ..., n + m), то задача вирішена.)

Крок 2. Вибрати (правило вибору буде описано далі) і написати внизу таблиці додатковий рядок

Цей рядок вибирається в якості ведучої.

Крок 3. Провести крок двоїстого симплекс-методу, викреслити додатковий рядок і повернутися до кроку 1.

Доказ кінцівки алгоритму см., Стор. 303-304.

Правило вибору формулюється в такий спосіб.

Крок 0. Нехай рядок з номером v є виробляє.

Крок 1. Нехай - лексикографічно мінімальний стовпець серед стовпців з a vj

Крок 2. Для кожного a vj - найбільше ціле, таке, що (лексикографічно менше).

Крок 3. Нехай, а (рядок v - виробляє). тоді

.

Крок 4. Покласти для a vj

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

2.2.2 Прямий алгоритм цілочисельного програмування

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

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

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

максимізувати

Припустимо, що стовпець обраний в якості ведучого і рядок v - провідна рядок в ітерації симплекс-методу, тобто для всіх рядків I, в яких a is> 0. Перш ніж провести процедуру виключення Гауса в симплекс-методі, додамо до таблиці відсікання Гомори, отримане з рядка v:

де J - безліч індексів небазисних змінних в (22), s k - нова (базисна) слабка змінна і - невизначена (тимчасово) позитивна константа.

Зауважимо, що якщо покласти = a vs, відсікання (23) буде володіти двома важливими властивостями. По перше,

Це означає, що пряма допустимість таблиці зберегтися, якщо використовувати відсікання (23) в якості провідного рядка. По-друге,, тобто провідний елемент дорівнює 1 (якщо відсікання використовується як провідна рядок). Легко переконатися (шляхом дослідження формул зміни базисних змінних), що перетворення симплексной таблиці з одиничним провідним елементом зберігає цілочисельність елементів симплексного таблиці.

Ці ідеї послужили підставою прямого алгоритму в целочисленном програмуванні:

Крок 0. Почати з столбцовую таблиці, в якій a i 0 0 (i 1) і всі елементи a 0 j, a ij і a i 0 - цілі.

Крок 1. Перевірити виконання умов a 0 j 0 (j 1); якщо вони виконані, то кінець, поточний базисне рішення оптимально; якщо немає - перейти до кроку 2.

Крок 2. Вибрати провідний стовпець s з a 0 s 0. Цей рядок служить виробляє для відсікання Гомори.

Крок 3. Отримати відсікання Гомори з виробляє рядки і дописати її внизу таблиці, тобто додати до обмежень задачі рівняння (23), де.

Крок 4. Провести перетворення таблиці, використовуючи відсікання (23) як провідний рядок. Слабка змінна s k в (23) стане небазисной. Повернутися до кроку 1.

Доказ кінцівки алгоритму см., Стор. 346-353.

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

де визначається з умови

Визначимо безліч V (s) як сукупність рядків, що задовольняють умові (25).

Наступні два правила являють собою приклади допустимих правил вибору виробляє рядки:

Правило 1.

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

2. Якщо список порожній або не містить жодного індексу з V (s), повернутися до 1 .; в іншому випадку знайти в списку перший індекс v V (s). Вибрати рядок v як виробляє. Вивести зі списку індекс v і всі попередні йому індекси. Перейти до 3.

3. Послідовно вибирати рядок v, взяту в 2., як виробляє, до тих пір, поки v V (s). Як тільки v V (s), повернутися до 2.

Правило 2.

1. Нехай V t (s) - безліч V (s), відповідне t-й таблиці. Якщо V t (s) містить більше одного елемента: V t (s) = (v 1, v 2, ..., vk +2), то в якості виробляє вибрати такий рядок, що в послідовності множин V 1 (s 1), V 2 (s 2), ..., V t (s) рядок з'явилася раніше (не пізніше) інших і потім зберігалася аж до V t (s); перейти до 2.

2. Послідовно вибирати рядок v, взяту в 1., до тих пір, поки. Як тільки, повернутися до 1.

2.2.3. ТЕХНІКА ОТРИМАННЯ ПОЧАТКОВОГО ДОПУСТИМОГО БАЗИСУ

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

Нехай задача лінійного програмування записана в канонічної формі:

мінімізувати

за умов

Всі b i можна зробити невід'ємними, помноживши, якщо треба, відповідне рівняння на -1. Тоді можна додати в кожне рівняння штучну змінну (штучні змінні повинні бути невід'ємними) таким чином, щоб з штучних змінних утворити початковий базис:

Штучні змінні можна отримати зі слабких змінних, використовуваних для перетворення нерівностей в рівняння. Дійсно, якщо вихідні обмеження задачі лінійного програмування задані у вигляді нерівностей:

то, додавши слабку змінну в кожне нерівність, отримаємо:

Якщо b i 0, то s i можна використовувати в якості початкових базисних змінних.

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

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

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

Розглянь як приклад наступну задачу лінійного програмування:

мінімізувати

за умов

де всі b i невід'ємні.

Якщо ввести штучні змінні і нову цільову функцію, то отримаємо задачу:

мінімізувати

,

за умов

Якщо відняти всі рівняння, що містять b i, з-форми, отримаємо:

-z

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

2.3. ОСОБЛИВОСТІ ПРАКТИЧНОЇ РЕАЛІЗАЦІЇ СИСТЕМИ

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

2.3.1. ВИБІР МОДЕЛІ

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

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

В даний час существовует три основні підходи до формування моделі даних: ієрархічний, мережевий і реляційний.

Ієрархічному методі ОРГАНІЗАЦІЇ

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

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

СЕТЕВОЙ СПОСІБ ОРГАНІЗАЦІЇ

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

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

Тип зв'язку визначається для двох типів запису: предка і нащадка. Примірник типу зв'язку складається з одного примірника типу записи предка і упорядкованого набору примірників типу записи нащадка. Для даного типу зв'язку L з типом запису предка P і типом запису нащадка C повинні виконуватися наступні дві умови:

1. Кожен екземпляр типу P є предком тільки в одному екземплярі L;

2. Кожен екземпляр C є нащадком не більше, ніж в одному екземплярі L.

Реляційна СПОСІБ ОРГАНІЗАЦІЇ

Основними недоліками іерархічекого і мережевого типів моделей даних є:

1. Занадто складно користуватися;

2. Фактично необхідні знання про фізичну організації;

3. Прикладні системи залежать від цієї організації;

4. Їх логіка перевантажена деталями організації доступу до БД.

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

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

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

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

Після попереднього аналізу математичної моделі системи і способів організації даних, а також наявного на ринку ПО (ієрархічний і мережеві способи організації припускають об'єктно - орентіровани підхід до організації даних і на сьогоднішній день є такі СУБД (наприклад, Jasmin або Informix Dynamic Server), але на момент розробки можливості їх використання не було, в той же час існують дуже "потужні" реляційні СУБД (наприклад Oracle 8i)) вибір був зроблений на користь реляційного способу організації зберігання даних.

2.3.2. ОПИС ВХІДНИХ ІНФОРМАЦІЇ

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

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

Таблиця 2. Опис реквізитів вхідної інформації

Найменування реквізитів	характеристика реквізитів
вхідних документів	Тип	Макс. довжина	точність
Прізвище, ім'я, по батькові викладача; Контактний телефон викладача; Наукова ступінь; Вчене звання; Назва гурту; Чисельний склад групи; Назва читаного курсу; Кількість аудиторних годин; Номери аудиторій; Інформація про аудиторіях; Назва предмета, що читається викладачем; Номер групи, де читається предмет; Інформація про аудиторіях, де читається предмет.

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

2.3.3. РОЗРОБКА ІНФОРМАЦІЙНОГО ЗАБЕЗПЕЧЕННЯ ЗАВДАННЯ

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

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

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

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

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

Рис.1. Инфологическая модель бази даних задачі складання розкладу занять

2.3.4. ОСОБЛИВОСТІ ФОРМУВАННЯ ОБМЕЖЕНЬ МОДЕЛІ ЗАВДАННЯ СКЛАДАННЯ розкладу

Складання обмежень (1) - (7) математичної моделі задачі складання розкладу є досить тривіальним завданням, розв'язуваної за допомогою нескладних SQL - запитів і не вимагає попереднього аналізу вхідної інформації. Тому докладніше лише зупинимося на обмеженнях виду (8).

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

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

Рис.2. Лінійно пересічні безлічі

У разі такого розташування множин аудиторій для проведення занять загальне числообмежень виду (8) буде n-1, де n - кількість множин. Описане вище розташування пересічних множин може бути названо лінійним, так як при цьому n пересічних множин розташовані як би в лінію. Можна розглянути випадок, коли безлічі перетинають один одного довільним чином (див. Рис. 3.).

Рис.3. Довільно пересічні безлічі

Число обмежень виду (8) в цьому випадку можна зменшити завдяки формування цих обмежень за аналогією з випадком лінійного розташування множин. Для цього необхідно передбачити, що, наприклад, множини B і D, пересічні з A, є одним безліччю, визначити область перетину такого безлічі з безліччю A, після чого провести ті ж самі дії з отриманою областю перетину.

Детальніше про це див., Стор. 210.

2.4. Результати роботи програми

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

Ядро системи і інтерфейсна частина були написані на Delphi 6.0. Методи рішення і алгоритми формування обмежень написані з використанням об'єктно-оріентірованнних технологій, що дозволить в майбутньому легко инкапсулировать їх в подальші модифікації системи, не порушуючи цілісності взаємодії різних алгоритмів. Текст об'єктів методів вирішення задачі наведено в додатку 2. База даних була реалізована на СУБД Oracle 8i, запити до неї здійснюються на мові PL / SQL.

Вихідні дані завдання заносяться в таблиці бази даних за допомогою Запитальний форм. Одна з таких форм приведена на рис. 3.

Рис.3. Форма занесення вихідних даних

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

Мал. 4. Приклад розкладу занять

Алгоритми рішення задачі були протестовані на різних вибірках вихідних даних. Тестування проводилося на ЕОМ з процесором Intel Pentium 350 Мгц, СУБД Oracle 8i був встановлений на двопроцесорним сервері: 2 CPU Intel Pentium II 350 Мгц, ОЗУ 384 Мб; в якості каналу зв'язку використовувалася LAN з пропускною спроможністю до 100 Мбіт / с. В якості тестових вихідних даних були використані як реальні дані про групи, викладачів і читаються предметах вечірньої форми навчання ЧДУ на 1999/2000 навчальні роки, Так і випадково що формуються вихідні дані (читаним предметів випадковим чином визначали аудиторії для проведення занять). В середньому починали від 5 до 10 тестів для кожної тестованої розмірності вихідних даних. В результаті отримали дані, наведені в таблиці 2. На малюнку 5. наведено графік залежності середнього часу виконання завдання від кількості популярних предметів і кількості груп.

2.5. Аналіз отриманих результатів

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

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

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

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

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

ЛІТЕРАТУРА

1. Лагоша Б.А., Петропавлівська А.В. Комплекс моделей і методів оптимізації розкладу занять у вузі // Економіка і мат. методи. 1993. Т. 29. Вип. 4.

2. Ху Т. Целочисленное програмування і потоки в мережах. М .: Мир, 1979.

3. Лебедєв С.С. Модифікація методу Бендерс частково цілочисельного лінійного програмування // Економіка і мат. методи. 1994. Т. 30. Вип. 2.

4. Лебедєв С.С., Заславський А.А. Використання спеціального методу гілок і меж для вирішення целочисленной узагальненої транспортної задачі // Економіка і мат. методи. 1995. Т. 31. Вип. 2.

5. Заславський А.А. Використання стратегії розшарування змінних в загальних завданняхцелочисленного лінійного програмування // Економіка і мат. методи. 1997. Т. 33. Вип. 2.

6. Лебедєв С.С. Про метод впорядкує індексації целочисленного лінійного програмування // Економіка і мат. методи. 1997. Т. 33. Вип. 2.

7. Лебедєв С.С., Заславський А.А. Модифікований метод позначок для задач булева програмування // Економіка і мат. методи. 1998. Т. 34. Вип. 4.

8. Заславський А.А. Комбінований метод вирішення завдань про рюкзаку // Економіка і мат. методи. 1999. Т. 35. Вип. 1.

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

Зистема АВТОР-2 + призначена для швидко і зручного складання розкладів занять і супроводу їх протягом всього навчального року.
АВТОР-2 + - універсальна система. Є кілька версій програми, розраховані на будь-які навчальні заклади:

Сpедние і спеціалізіpованние (математичні, мовні тощо) школи, ліцеї, гімназії;

Технікуми, училища та коледжі;

ВНЗ з одним навчальним корпусом;

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

АВТОР-2 + дозволяє максимально полегшити і автоматизованого складний тpуд укладачів розкладу. Система допомагає легко стpоить, коppектіpовать і pаспечативать у вигляді зручних і наочних документів:

Pаспісанія занять класів (навчальних груп);

Розклади пpеподавателей;

Розклад аудиторій (кабінетів);

Учбові плани;

Тарифікацію.

АВТОР-2 + має приємне дизайн і дpужеcтвенний сеpвіс. Програма досить проста в освоєнні. Є докладний посібник, в якому описані всі можливості і способи роботи з програмою.
Программа працює на будь-яких IBM-сумісних комп'ютерах, починаючи з 486DX з оперативною пам'яттю 4Mb (і вище), займає близько 1 Mb на жорсткому диску. Операційна система: MS DOS, або WINDOWS 95/98.
Время роботи залежить від розмірності навчального закладу і потужності комп'ютера. Повний розрахунок і оптимізація розкладу школи середнього розміру (30 класів, 60 викладачів, дві зміни) йде близько 15 хвилин на комп'ютері типу Celeron-400.

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

АВТОР-2 + дозволяє:

Оптимізувати "вікна" в розкладі;

Враховувати необхідний діапазон днів / годин як для класів, так і для викладачів;

Оптимально розміщувати заняття по кабінетах (аудиторіям) з урахуванням особливостей класів, предметів, пpеподавателей і місткості кабінетів;

Враховувати хаpактеp АДВОКАТУРИ та побажання як штатних сотpудников, так і сумісників-погодинників;

Легко з'єднувати ( "спаpівать") кілька класів (навчальних груп) в потоки пpи пpоведення будь-яких занять;

Розділяти класи пpи пpоведення занять з іноземної мови, фізичної культури, тpудом, інформатики (і будь-яким іншим предметам) на будь-яку кількість підгруп (до десяти!);

Вводити (крім основних предметів) спецкуpси і факультативи;

Оптимізувати рівномірність і трудомісткість розкладу.

2. Система "Розклад" ver 4.0 Москва - ЛінТех

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

- ПроМежує максимальний номер уроку - тобто кількість уроків, максимально допустимий в день;

- Равномерность розподілу навантаження викладачів між днями розкладу;

- Равномерность розподілу навантаження класів між днями розкладу;

- Доонтроль вікон в розкладі викладачів;

- Программа враховує ту обставину, що класи можуть довільно об'єднуватися і дробитися (класи можуть об'єднуватися в потоки або ж дробитися на більш дрібні підгрупи, причому ці підгрупи, в свою чергу, можуть служити основою для об'єднання в більш великі групи. Приклад: в школі №1859 є 2 старших класу, але в кожному з цих класів є дві підгрупи по спеціалізації, заняття із загальноосвітніх предметів проводяться відразу для всього класу, а предмети за спеціалізацією - окремо. але оскільки підгрупи по спеціалізації занадто малі, а викладачів не вистачає, з деяких предметів підгрупи 11а і 11б також можуть об'єднуватися (наприклад, на ин.яз.) - це ускладнює забезпечення безперервності розкладу для класів (необхідно забезпечувати безперервність розкладу для кожної з підгруп);

- НАліче декількох змін - у цьому випадку окремі класи повинні приходити пізніше, ніж групи першої зміни, крім цього, ускладнюється контроль вікон в розкладі викладачів, якщо є викладачі, які працюють в обидві зміни - в цьому випадку в розкладі цих викладачів їх заняття необхідно "стягувати" навколо перетину змін;

- УСлово прив'язки викладачів до аудиторії - окремі викладачі мають "свою" аудиторію, в якій проводять всі свої заняття;

- НАліче "плаваючою" зміни - коли час початку першого уроку точно не визначено, тому що воно формується динамічно, в залежності від звільнення пов'язаних з відповідним класів, викладачів, аудиторій;

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

- НАліче комбінованих предметів - типу "ин.яз. / інформатика" "інформатика / праця" і т.п. - коли клас розбивається на підгрупи;

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

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

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

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

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

- Виполненіе умови необхідних послідовностей предметів - коли необхідно забезпечувати установку груп занять, в яких заняття повинні йти в певній послідовності, наприклад, фізика-астрономія і т.п .;

- НАліче класів, прив'язаних до аудиторій - основна маса занять для таких класів проводиться саме в цій аудиторії, за винятком тих занять, для яких потрібно спеціалізована аудиторія;

- Необходимо розстановки занять з окремих предметів по два заняття підряд ( "парами", "Спарк"), причому ця умова може бути жорстким (ні в якому разі не розривати "Спаркі" занять), а може носити кращий характер (якщо не виходить переміщати по два заняття, "спарку" можна розривати);

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

3. Система "Методист"

Випускається в двох версіях.

Версія virtual.

Випускається без модуля автоматичного складання розкладу. Можливості версії virtual:

Швидкий пошук в списках викладачів, аудиторій, класів (груп), дисциплін, корпусів;

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

Контроль і можливість перерозподілу годин між тижнями по будь-якої дисципліни уч. групи;

Автоматична перевірка можливих помилок введення даних (відповідність загальної суми годин і за видами занять, непризначення викладачів по підгрупах, бюджет часу уч. Групи і викладача, невідповідність годин в групах потоку і мн. Ін.);

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

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

Можливість перегляду, друку і редагування готового розкладу з перевіркою коректності змін (зайнятість ауд., Викл., Груп / підгруп, ...);

У будь-який момент можна замовити модуль формування розкладу для підготовлених даних;

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

Якщо виявлена ​​необхідність незначного (до 10%) зміни вихідних даних (виявлені помилки, раптові доповнення), можливий повторний замовлення модуля формування розкладу за незначну плату;

У будь-який момент можна перейти на версію стандарт;

Методист - стандарт.

Крім можливостей версії virtual включає в себе:

Модуль автоматичного складання розкладу;

Розподіл і контроль навчального навантаження;

Cтрогий витримування послідовності проходження дисципліни (лекції - 2 год., Практичні - 4 год., Лабораторні ...);

Складання розкладу для будь-якого типу навчального закладу: тижневе або семестрове (від 1 до 23 тижнів);

Облік об'єднання груп (класів) в потоки і / або розбиття їх на підгрупи;

Закріплення спеціальних аудиторій (комп'ютерні класи, лінгафонні кабінети, басейн, ...);

Облік зайнятості викладачів і аудиторій (сумісництво, використання загальної навчальної бази);

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

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

Вказівка ​​причин "невдалого призначення" занять (зайнята аудиторія, викладач призначений в небажаний для нього день тижня) з можливістю їх "ручного" виправлення;

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

Можливість зміни значущості враховуються при складанні розкладу факторів;

Можливість введення пріоритетів викладачів - ступеня врахування їх індивідуальних побажань;

Обмеження функціональності "Методиста":

Багатозмінної розкладу обмежені максимальним кол-вом уроків в день - 7;

Заняття завжди починаються з першого уроку / пари (при необхідності можливе призначення на першу пару "вільного заняття");

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

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

Тривалість занять постійна (неможливо складання розкладу для 30 хв. Уроку в молодших і 45 хв. - в старших класах).

Додаток 2. Лістинг програмного модуля методів рішення задачі автоматичного складання розкладу

type MyArray = array of array of real;

MyArray_X = array of longint;

procedure Step_Dual_simplex (var a: MyArray; m, n, i1, j1: integer);

(Виробляє один крок двоїстого симплекс-методу,

провідний елемент - a)

var i, j: integer;

b, b1: array of real;

SetLength (b, m); Setlength (b1, n);

for i: = 0 to m-1 do b [i]: = a;

for i: = 0 to n-1 do b1 [i]: = a;

for i: = 0 to m-1 do

for j: = 0 to n-1 do begin

if (i = i1) and (j = j1) then a: = 1 / b

if (i = i1) then a: = b1 [j] / b

if (j = j1) then a: = - b [i] / b

else a: = a-b [i] * b1 [j] / b;

for i: = 0 to n-1 do a: = 0; a: = - 1;

Finalize (b); Finalize (b1);

function Lexikogr_few (a: MyArray; m, n: integer; i, i1: integer): boolean;

(Перший стовпець лексикографічно менше другого)

Lexikogr_few: = false;

while (a = a) and (j

function Find_nu (a: MyArray; m, n: integer; i, i1: integer): longint;

(I - індекс лексикографічно мінімального стовпчика)

while (a = a) and (j

if (j 0) then Find_nu: = Round (Int (a / a));

procedure Full_Integer_Simplex (var x: MyArray_X; a: MyArray; m, n: integer);

(Повністю цілочисельний алгоритм задачі лінійного цілочисельного

програмування,

см. Ху Т. "Цілочисельне програмування і потоки в мережах", стор. 300-309,

a - матриця розміром m + n + 2 * n + 1, за аналогією:

Потрібно знайти максимум

z = - 10x1 - 14x2 - 21x3

2x1 + 2x2 + 7x3> = 14

8x1 + 11x2 + 9x3> = 12

9x1 + 6x2 + 3x3> = 10,

процедура повертає вектор X, перші m компонент якого - шукане рішення,

якщо остання компонента вектора = 1, то рішення не існує або воно = нескінченності)

var i, i1: integer;

while (i = 0) do Inc (i); (Виробляє рядок)

while (j = 0) do Inc (j);

for i1: = 1 to n-1 do if (a

мінімальний стовпець)

(Вибір альфа)

(Writeln (i, "", j); readln;)

for i1: = 1 to n-1 do if a

j1: = Find_nu (a, m, n, j, i1);

if (j1> 0) and (-a / j1> alfa) then alfa: = - a / j1;

(Writeln (alfa, "", i, "", j); readln;)

(Отримання відсікання Гомори)

for i1: = 0 to n-1 do if a> 0 then a: = round (Int (a / alfa))

a: = round (Int (a / alfa));

if Frac (a / alfa) 0 then a: = a-1;

Step_Dual_simplex (a, m, n, m-1, j);

until (i> = m-1) or (j> = n);

for i: = 0 to m-1 do x [i]: = round (a);

if j> = n then x: = 1 else x: = 0;

procedure Step_One_Simplex (var a: MyArray; m, n, i: integer);

var i1, i2: integer;

(Один крок прямого целочисленного методу (виробляє рядок - остання

i - виробляє стовпець))

for i1: = 0 to m-2 do a: = a / (- a);

for i2: = 0 to n-1 do

for i1: = 0 to m-2 do

if i2i then a: = a + a * a;

procedure Direct_Integer_Simplex (var x: MyArray_X; a: MyArray; m, n: integer);

(Прямий цілочисельний алгоритм задачі цілочислового лінійного програмування,

см. Ху Т. "Цілочисельне програмування і потоки в мережах", стор. 344-370,

a - матриця розміром m + n + 3 * n + 1 за аналогією:

потрібно максимізувати

z = x1 + x2 + x3

4x1 + 5x2 + 2x3

тоді матриця а буде виглядати:

10 1 + 1 1 - у цьому рядку перше число - груба max суми небазисних змінних

0 0 0 0 - рядок для відсікання Гомори,

алгоритм працює тільки при a> = 0

повертає вектор X - на місці одиничної матриці шукане рішення,

якщо в останній компоненті одиниця - помилка при розрахунках)

var i, j, i1, j1: integer;

b, b1, b2: array of byte;

SetLength (b, m); SetLength (b1, m);

for i: = 0 to m-1 do b1 [i]: = 0;

(Перевірка умови оптимальності)

for j: = 1 to n-1 do if a

while bool do begin

(Пошук виробляє стовпчика)

bool: = false; j1: = 0;

for j: = 1 to n-1 do begin

if a> 0 then

for i: = 0 to m-3 do a: = a / a;

if not bool then begin j1: = j; bool: = true; end else if Lexikogr_few (a, m, n, j, j1)

(Пошук виробляє рядки)

for j: = 1 to n-1 do

if a> 0 then

for i: = 0 to m-3 do a: = a * a;