Теорія розкладів

Теорія розкладів — розділ дискретної математики, що вивчає проблеми впорядкування. У загальному випадку проблеми формулюються так: Дано деяку множину робіт (вимог) $J=\{J_{1},J_{2},\dots ,J_{n}\}$ з певним набором характеристик: тривалість опрацювання вимоги (найпростіший випадок), вартість опрацювання вимоги, момент надходження вимоги, директивний термін закінчення опрацювання вимоги. Задано деяку множину машин (приладів) $M=\{M_{1},M_{2},\dots ,M_{m}\}$, на яких вимоги мають опрацьовуватися відповідно до деякого порядку.

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

Задачі теорії розкладів можна розділити на дві групи:

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

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

За дисципліною виконання робіт на машинах можна виділити чотири основні класи задач:

1. Відкрита лінія (англ. Open shop) — для кожної вимоги задано свою підмножину машин, на кожній з яких вона має опрацьовуватися протягом певного часу. Порядок опрацювання на цих машинах довільний. Задаються різноманітні цільові функції.
2. Робочий цех (англ. Job shop) — для кожної вимоги задано свою впорядковану підмножину машин (маршрут), на яких вона має опрацьовуватися в заданому порядку. Задаються різноманітні цільові функції.
3. Flow shop, потокова лінія — всі машини впорядковано — $M_{1},M_{2},\dots ,M_{m}$ і кожна вимога проходить всі машини в цьому порядку. Розклад задано перестановкою вимог. Як правило, мінімізується загальний час опрацювання вимог.
4. Задача з директивними термінами — для кожної вимоги задано момент надходження, час опрацювання і директивний термін закінчення опрацювання. Порядок опрацювання на машинах довільний. Необхідно знайти розклад, за якого буде дотримано директивні терміни. При існуванні такого розкладу можна ставити задачу мінімізації числа переривань.

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

Зокрема, для задачі «Потокова лінія» на двох машинах існує алгоритм Джонсона з часовою складністю $O(n\log(n))$, який будує розклад з мінімальним загальним часом опрацювання.

Для задачі з директивними термінами з довільним числом приладів і перериваннями опрацювання існує алгоритм з часовою складністю $O(n^{3})$, який будує розклад з дотриманням директивних термінів.

Розв'язком задач «Відкрита лінія» і «Робочий цех» з одним приладом без переривань є деяка перестановка вимог і для довільної цільової функції ці задачі NP-повні. Але для деяких конкретних цільових функцій знайдено поліноміальні алгоритми.

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

Два способи зведення початкових задач до задач упорядкування ґрунтуються на поняттях компактних (англ. active) і квазікомпактних (англ. semiactive) розв'язків. У зазначеному вище препринті В. В. Шмельова поняття компактних і квазікомпактних розв'язків узагальнено і на цій основі запропоновано нове поняття монотонних розв'язків. Кожен монотонний розв'язок є і компактним, і квазікомпактним одночасно, тому таких розв'язків, як правило, менше. Це спрощує розв'язування задач упорядкування.

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

Література

• Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний. Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
• Танаев В.С., Шкурба В. В. Введение в теорию расписаний. (серия «Экономико-математическая библиотека»), Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1975.
• Richard W. Conway, William L. Maxwell, Louis W. Miller. Theory of scheduling
• Левин В. И. Структурно-логические методы в теории расписаний. Пенза: Изд-во Пенз. гос. технол. акад., 2006.
• Peter Brucker Scheduling Algorithms [Архівовано 21 лютого 2016 у Wayback Machine.]. Heidelberg, Springer. Fifth ed. ISBN 978-3-540-24804-0

Науково-популярні видання

• Шкурба В. В. «Задача трёх станков [Архівовано 18 травня 2021 у Wayback Machine.]». — М.: Наука, 1976. — 96 с., илл.