ТЕОРІЯ РОЗКЛАДІВ

Робоча програма навчальної дисципліни (Силабус)

Реквізити навчальної дисципліни

Програма навчальної дисципліни

1. Опис навчальної дисципліни, її мета, предмет вивчення та результати навчання

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

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

В результаті освоєння дисципліни повинні бути сформовані такі компетентності:

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

2. Пререквізити та постреквізити дисципліни (місце в структурно-логічній схемі навчання за відповідною освітньою програмою)

Для успішного засвоєння дисципліни студент повинен володіти освітніми компонентами:

• Вища математика;
• Теорія ймовірностей і математична статистика;
• Спеціальні розділи математики;
• Ймовірнісні моделі та статистичне оцінювання в інформаційно-управляючих системах.

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

• Прийняття рішень в інформаційних системах.

3. Зміст навчальної дисципліни

Тема 1. Предмет та задачі дисципліни Тема 2. Методи розв'язання задач ТР Тема 3. Системи обслуговування з однією машиною Тема 4. Системи обслуговування з декількома машинами Тема 5. Типи алгоритмів складання розкладів

4. Навчальні матеріали та ресурси

Базова література

1. Гуляницький Л. Ф. Прикладні методи комбінаторної оптимізації: навч. посіб. / Л. Ф. Гуляницький, О. Ю. Мулеса. – Київ: Видавничо-поліграфічний центр «Київський університет», 2016. – 142 с.
2. Ващук Ф. Г. Теорія розкладів / Ф. Г. Ващук, О. Г. Лавер, Н. Я. Шумило. – Ужгород: Видавництво «Два кольори», 2003. – 136 с.

Додаткова література

1. Conway R. W. Theory of Scheduling / R. W. Conway, W. L. Maxwell, L. W. Miller. – 2003. – 304 с.
2. Pinedo M. L. Scheduling. Theory, Algorithms and Systems / Michael Pinedo. – New York: Springer Science+Business Media, 2008. – 671 с.
3. Pinedo M. L. Planning and Scheduling in Manufacturing and Services / Michael Pinedo. – New York: Springer Science+Business Media, 2009. – 536 с.
4. Taha H. A. Operations Research. An Introduction. Eighth Edition / Hamdy Taha. – New Jersey: Pearson Education, 2007. – 813 с.
5. Rossi F. Handbook of Constraint Programming / F. Rossi, P. van Beek, T. Walsh. – Amsterdam: Elsevier, 2006. – 957 с.
6. Rudová H. Course on Constraint Programming and Scheduling [Електронний ресурс] / Hana Rudová. – 2009. – Режим доступу до ресурсу: https://www.fi.muni.cz/~hanka/konstanz09/.

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

Навчальний контент

5. Методика опанування навчальної дисципліни

5.1. Тематика лекцій

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

Таблиця 1 | № лекції | Назва теми лекції та перелік основних питань | | --- | --- | | | Тема 1. Предмет та задачі дисципліни | | 1 | Предмет та задачі теорії розкладів (ТР). Проблеми впорядкування. Питання «ідеального» впорядкування. Математична модель задачі ТР. Критерії оцінки розкладів. Вхідні величини при складанні розкладів. Шукані (вихідні) величини при складанні розкладів. Співвідношення між середніми вихідних величин. Розклад і вартість. Регулярний критерій. Діаграма Гантта. Класифікація задач ТР. Нотація Грехема. | | | Тема 2. Методи розв'язання задач ТР | | 2 | Методи розв'язання задач ТР. Математичне програмування і ТР. Класифікація методів розв'язання задач теорії розкладів. Наближені методи розв'язання. Правила диспетчеризації. Локальний пошук. Напрямки розвитку сучасних методів розв'язання задач теорії розкладів. | | | Тема 3. Системи обслуговування з однією машиною | | 3-4 | Системи обслуговування з однією машиною. Незалежні роботи без ваг та директивних строків. Практичні задачі, що зводяться до систем обслуговування з однією машиною. Переривання. Штучні простої. Теорема про оптимальність розкладу відносно регулярного критерію з класу розкладів без переривань та простоїв. | | 5 | Перестановочні розклади. Перестановочні розклади. Упорядкування за мінімумом тривалості робіт (SPT). Упорядкування за максимумом тривалості робіт (LPT). Теореми про оптимальність SPT, LPT. Методи доведення теорем: перестановочний прийом, метод попарних перестановок.| | 6 | Незалежні роботи з директивними строками. Впорядкування у відповідності з плановим строком. Теорема Джексона. Впорядкування у відповідності з резервом часу. Оптимізація за двома критеріями. Теорема про мінімізацію середньої тривалості проходження робіт при збереженні нульового запізнення. | | 7 | Незалежні роботи з вагами. Випадкове впорядкування. Властивості антитетичних правил. Упорядкування у випадку критерію, що враховує ваги. Мінімізація сумарної зваженої тривалості проходження робіт. Мінімізація середнього зваженого запізнення. Алгоритм Шилда-Фрідмана. | | 8 | Наявність налаштувань, неодночасне надходження. Тривалість налаштування, яка залежить/не залежить від впорядкування. Неодночасне надходження робіт. Системи з обслуговуванням «заново», системи з дообслуговуванням. Системи зі штучними простоями. | | 9 | Впорядкування за наявності обмежень на можливі варіанти розкладів. Складання розкладів при частковому впорядкуванні. Часткове упорядкування. Мінімізація середньої тривалості проходження груп робіт. Мінімізація середньозваженої тривалості проходження груп робіт. Мінімізація середньої тривалості проходження робіт. Впорядкування за наявності обмежень на можливі варіанти розкладів – відношення впорядкування у вигляді ланцюгів. | | | Тема 4. Системи обслуговування з декількома машинами | | 10-11 | Системи обслуговування з декількома машинами. Паралельні машини. Ідентичні, пропорційні, незалежні машини. Системи, в яких роботи можуть виконуватися кількома машинами одночасно. Системи, в яких заборонено одночасне виконання робіт кількома машинами. Задачі оптимізації загального часу обслуговування. Задачі з директивними строками. Мінімізація сумарного і максимального значення закінчення робіт. | | 12-13 | Конвеєрні системи. Особливості системи конвеєрного типу. Перестановочні розклади. Мінімізація максимальної тривалості проходження в конвеєрній системі з двох приладів. Мінімізація середньої тривалості проходження в конвеєрній системі з двох приладів. Конвеєрна система з трьох приладів. Впорядкування у великих системах конвеєрного типу. | | 14 | Складання розкладу в задачах з відношенням передування. Види відношень передування (ациклічний орієнтований граф, ланцюг, дерево). Метод критичного шляху. Задача складання розкладу виконання робіт з відношеннями передування у вигляді дерева (intree, outtree). Методи розв'язання часткових випадків задачі. | | 15 | Складання розкладу виконання робіт паралельними машинами, для яких виконується умова вкладеності. Вкладені множини машин. Методи розв'язання часткових випадків задачі. Правило найменш гнучкої роботи. | | | Тема 5. Типи алгоритмів складання розкладів | | 16-17 | Типи алгоритмів складання розкладів. Однократні алгоритми. Алгоритми, що коригуються. Алгоритми диспетчеризації. Пріоритет роботи (операції). Правила вибору операції RANDROM, MOPNR, MWKR-P, MWKR/P, SPT, MWKR, LWKR. | | 18 | Залікова робота |

5.2. Методи і засоби навчання

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

Основним засобом навчання є середовище MOODLE (Modular Object-Oriented Dynamic Learning Environment) версії 3.10, розгорнуте на базі Платформи дистанційного навчання «Сікорський». В цій системі на сторінці дисципліни для студентів доступні усі навчально-методичні матеріали (конспект лекцій, презентації, завдання домашніх робіт тощо).

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

6. Самостійна робота студента

Види самостійної роботи студентів:

• підготовка до лекцій, проходження тестів – 46 год (конспект та презентації лекцій завантажені в MOODLE, тести – також в MOODLE);
• підготовка до МКР – 4 год (виконання завдань теоретичного характеру, умови завдань наведені в MOODLE);
• підготовка до заліку – 4 год.

7. Модульна контрольна робота

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

МКР складається з трьох частин:

• частина 1: тест на тему «Мінімаксні та максимінні критерії. Упорядкування, що враховують директивні строки»;
• частина 2: контрольна робота на тему «Доведення теорем про оптимальність заданих критеріїв»;
• частина 3: тест на тему «Складання розкладів за наявності відношень передування у вигляді дерева».

МКР проводиться у системі MOODLE. За кожною частиною кожен студент виконує індивідуальне завдання.

Політика та контроль

8. Політика навчальної дисципліни (освітнього компонента)

Основні положення політики:

• політика щодо академічної доброчесності: Кодекс честі Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського» встановлює загальні моральні принципи, правила етичної поведінки осіб та передбачає політику академічної доброчесності для осіб, що працюють і навчаються в університеті, якими вони мають керуватись у своїй діяльності, в тому числі при вивченні та складанні контрольних заходів з дисципліни «Теорія розкладів»;
• правила відвідування занять: відвідування лекційних є обов'язковою складовою вивчення матеріалу; заохочувальні або штрафні бали за відвідування занять не нараховуються;
• політика щодо оцінювання результатів контрольних заходів, дедлайнів та перескладань: для кожного контрольного заходу в системі MOODLE вказаний термін виконання; студенти мають можливість підняти будь-яке питання, яке стосується процедури проведення та оцінювання контрольних заходів; студенти мають право оскаржити результати контрольних заходів, аргументовано пояснивши, з яким критерієм не погоджуються відповідно до оціночного листа та/або зауважень; у випадку виявлення факту академічної недоброчесності робота не зараховується, а її переписування не дозволяється; у разі невиконання (без поважних причин) контрольних заходів, можливість їх переписування студентові не надається;
• заохочувальні бали: виставляються за участь у розробці тестових завдань, оновленні методичних матеріалів, презентацій тощо; кількість заохочуваних балів не більше 10.

9. Види контролю та рейтингова система оцінювання результатів навчання (РСО)

9.1. Поточний контроль

Рейтинг студента з дисципліни складається з балів, що він отримує за:

1. виконання поточних контрольних робіт та проходження тестів;
2. виконання модульної контрольної роботи;
3. відповідь на заліку.

Умови завдань для самостійної проробки (в тому числі пробні тести), а також тести для поточного контролю знань, розміщені в системі MOODLE: https://do.ipo.kpi.ua/course/view.php?id=1665.

9.2. Система рейтингових (вагових) балів та критерії оцінювання

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

Таблиця 2

9.3. Календарний контроль

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

• за результатами навчальної роботи на першому календарному контролі (8-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 7 тижнів;
• за результатами навчальної роботи на другому календарному контролі (14-й тиждень) студент отримує «атестований», якщо його поточний рейтинг не менше 50% від максимально можливої кількості балів, які студент міг отримати за перші 13 тижнів.

9.4. Розрахунок шкали рейтингу

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

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

r_D = r + r_бонус,

де r = Σ_j=1,...,8 r_j – сума балів, що отримав студент протягом семестру за роботи, перелічені в табл. 2;

r_бонус – сума заохочувальних балів за участь у розробці тестових завдань, оновленні методичних матеріалів, презентацій тощо.

Студенти, які набрали протягом семестру рейтинг r_D менше 60 балів, зобов’язані виконувати залікову контрольну роботу.

Студенти, які набрали протягом семестру рейтинг r_D менше 40 балів, до залікової контрольної роботи не допускаються.

Студенти, які набрали протягом семестру рейтинг r_D не менше ніж 60 балів, отримують залікову оцінку так званим «автоматом» відповідно до набраного рейтингу (табл. 4). У цьому випадку, рейтингова оцінка обчислюється за формулою:

R = r_D.

9.5. Критерії оцінювання залікової контрольної роботи

Максимальна сума балів за питання залікової контрольної роботи складає 100 балів.

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

Таблиця 3 | № з/п | Задачі | | --- | --- | | 1 | Упорядкування за мінімумом тривалості робіт (SPT) | | 2 | Упорядкування за максимумом тривалості робіт (LPT) | | 3 | Упорядкування у відповідності з плановим строком | | 4 | Упорядкування у відповідності з резервом часу | | 5 | Оптимізація за двома критеріями (нульове запізнення + мінімізація середнього моменту закінчення) | | 6 | Мінімізація середнього зваженого запізнення. Алгоритм Шилда-Фрідмана | | 7 | Тривалість налаштування, яка залежить від впорядкування | | 8 | Неодночасне надходження робіт | | 9 | Одна машина: Упорядкування при наявності обмежень на можливі варіанти розкладу. Складання розкладів при частковому впорядкуванні | | 10 | Одна машина: Складання розкладів при заданому відношенні передування (ланцюг) | | 11 | Паралельні машини: Роботи можуть виконуватися одночасно кількома машинами | | 12 | Паралельні машини: Заборонено одночасне виконання робіт кількома машинами. Ідентичні машини. SPT та реверсний SPT | | 13 | Паралельні машини: Заборонено одночасне виконання робіт кількома машинами. Машини різної продуктивності. Складання розкладу виконання робіт паралельними пропорційними машинами з метою мінімізації середнього часу перебування робіт в системі | | 14 | Складання розкладу виконання робіт паралельними ідентичними машинами з метою мінімізації makespan | | 15 | Складання розкладу для P_m / t_j = 1, tree / T_max | | 16 | Складання розкладу для P_m / t_j = 1, M_i nested / T_max | | 17 | Мінімізація максимальної тривалості проходження в конвеєрній системі з двох машин |

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

R = r_Z,

де r_Z – кількість балів, набраних за виконання залікової контрольної роботи.

Для отримання студентом відповідних оцінок (ECTS та традиційних) його рейтингова оцінка переводиться згідно з таблицею 4.

Таблиця 4 | Бали (R) | Оцінка | | --- | --- | | 100…95 | Відмінно | | 94…85 | Дуже добре | | 84…75 | Добре | | 74…65 | Задовільно | | 64…60 | Достатньо | | Менше 60 | Незадовільно | | Не виконані умови допуску | Не допущено |

10. Додаткова інформація з дисципліни (освітнього компонента)

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

Робочу програму навчальної дисципліни (силабус):

Складено доц., к.т.н., доц. Ждановою Оленою Григорівною

Ухвалено кафедрою ІСТ (протокол №16 від 12.06.2024 р.)

Погоджено Методичною комісією факультету (протокол №10 від 21.06.2024 р.)