Лекція №2 - Методи розв’язання задач теорії розкладів

Вступ

1. Математичне програмування і ТР

2. Комбінаторний підхід

3. Евристичні та імовірнісні методи

«Часовий» характер задач ТР виділяє їх в особливий клас, який істотно відрізняється від «об'ємних» економічних задач. Якщо в останніх потрібно відповісти на питання, що і скільки виробляти, то в задачах ТР необхідно визначити, коли, в якій послідовності виконувати роботи. Ця різниця в суті завдань визначає відмінність в методах і можливостях їх розв’язання. Для задач об’ємного характеру розвинений досить потужний апарат, головним чином математичного програмування, що дозволяє, загалом, з успіхом добиватися їх вирішення. Для задач ТР апарат розв’язання розвинений в набагато меншій мірі.

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

- математичного програмування;

- комбінаторного;

- евристичного;

- статистичного (імовірнісного).

Деякі області використання результатів ТР в інформатиці й обчислювальній техніці:

- організація великих інформаційних систем - створення апаратно-програмних комплексів паралельної обробки даних (масово-паралельних систем МРР);

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

- розробка ПО планування колективної роботи (управління проектами).