2025__ТР Тема 5 - Основи побудови розкладів класифікація, стратегії та правила пріоритетів ST

1. Основи побудови розкладів: класифікація, стратегії та правила пріоритетів

ТЕМА 5

2. КЛАСИФІКАЦІЯ алгоритмів

3. Класифікація за точністю

Точні алгоритми
• забезпечують отримання оптимального розв'язку
Наближені алгоритми (евристики, метаевристики)
• дозволяють отримувати наближені розв'язки (за прийнятний
час)

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

On-line алгоритми
• інформація про задачу поступає частково, в
режимі реального часу
Off-line алгоритми
• вся інформація про задачу доступна на початку

5. Алгоритмічні стратегії побудови розкладів

Евристичні правила (жадібні алгоритми,
правила переваг)
Локальний пошук
Метаевристики (GA, SA, ACO, Tabu Search)
Інші

6. Фактори вибору алгоритму

Розмірність задачі (n, m)
Онлайн/офлайн
Необхідна точність та швидкість
Складність структури
• передування, переривання

7. Класифікація за незмінністю призначень

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

8.

Класифікація
за незмінністю
призначень
однократні
On-line
алгоритми
Off-line
алгоритми
кориговані

9. Онлайн-розклад

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

10. Онлайн-парадигма «Роботи надходять з часом»

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

11. Онлайн-парадигма. «Планування робіт по одній»

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

12. Алгоритмічні стратегії побудови розкладу: що, де і коли

13. три ключові аспекти алгоритмів

Що виконувати
• Вибір операції
Де виконувати
• Вибір машини
Коли виконувати
• Визначення моменту початку виконання

14. Дані задачі