«Математика» 2014 9

Эффективно разрешимые случаи задачи календарного планирования с переменной интенсивностью потребления и поступления ресурсов нескладируемого типа

Авторы: А. В. Еремеев, Ю. В. Коваленко
Аннотация:

Рассматривается NP-трудная в сильном смысле задача календарного планирования с ограничениями на ресурсы нескладируемого типа и порядок выполнения работ. Особенностью постановки является то, что интенсивности потребления ресурсов работами могут меняться в процессе их выполнения и наличие ресурсов зависит от момента времени. Доказано, что если ширина заданного на множестве работ частичного порядка ограничена константой, то задача псевдополиномиально разрешима, являясь при этом NP-трудной. Найдены новые полиномиально разрешимые частные случаи.
Ключевые слова: календарное планирование, нескладируемые ресурсы, динамическое программирование, полиномиальная разрешимость, псевдополиномиальная разрешимость
УДК: 519.718
Литература: 1. Айгнер М. Комбинаторная теория / М. Айгнер. – М. : Мир, 1982. – 558 с.
2. Гимади Э. Х. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками / Э. Х. Гимади, В. В. Залюбовский, С. В. Севастьянов // Дискрет. анализ и исслед. операций. Сер. 2. – 2000. – Т. 7, № 1. – С. 9–34.
3. Еремеев А. В. Календарное планирование производства с непрерывным поступлением сырья / А. В. Еремеев, Ю. В. Коваленко // Российская конференция «Дискретная оптимизация и исследование операций»: материалы конференции. – Новосибирск : Изд-во Ин-та математики, 2010. – С. 138.
4. Коваленко Ю. В. Решение задачи календарного планирования производства с непрерывным поступлением сырья / Ю. В. Коваленко // «Молодежь третьего тысячелетия» : XXXIV регион. науч.-практ. студ. Конф. : сб. ст. секции «Физико-математические науки». – Омск : Изд-во ОмГУ, 2010. – С. 21–24.
5. Коваленко Ю. В. О задаче календарного планирования с возобновимым ресурсом / Ю. В. Коваленко // Автомат. и телемех. – 2012. – Вып. 6. – С. 140–153.
6. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – М. : Вильямс, 2005. – 1296 с.
7. Кочетов Ю. А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами / Ю. А. Кочетов, А. А.Столяр // Дискрет. анализ и исслед. операций. Сер. 2. – 2005. – Т. 12, № 1. – С. 12–36.
8. Сервах В. В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами / В. В. Сервах // Дискрет. анализ и исслед. операций. Сер. 2. – 2000. – Т. 7, № 1. – С. 75–82.
9. Bell C. E. A new heuristic solution method in resource constrained project scheduling / C. E. Bell, J. Han // Naval Res. Logistics. – 1991. – Vol. 38. – P. 315-331.
10. A branch and bound algorithm for the resource-constrained project scheduling problem / P. Brucker, S. Knust, A. Schoo, O. Thiele // Eur. J. Oper. Res. – 1998. – Vol. 107. – P. 272–288.
11. Brucker P., Kramer A. Polynomial algorithms for resource constrained and multiprocessor task scheduling problems / P. Brucker, A. Kramer // Eur. J. Oper. Res. –1996. – Vol. 90, N 2. – P. 214–226.
12. Christofides N. Project scheduling with resource constraints: a branch and bound approach / N. Christofides, R. Alvarez-Valdes, J. M. Tamarit // European J. Oper. Res. – 1987. – Vol. 29. – P. 262–273.
13. Scheduling using continuous-time formulations: technical report / J. Kallrath, A. Eremeev, P. Borisovsky, J. Kovalenko. – Ludwigshafen : BASF SE, Scientifc Computing, 2010. – 337 p.
14. Pritsker A. A. B. Multiproject scheduling with limited resources: a zero-one programming approach // A. A. B. Pritsker, L. J. Watters, P. M. Wolfe // Management Sci. – 1969. – Vol. 16. – P. 93–107.
15. Servakh V. V. A fully polynomial time approximation scheme for two project scheduling problems / V. V. Servakh, T. A. Shcherbinina // Inform. Control Problems in Manufact.: A Proc. of 12th IFAC Intern. Symp. / ed. by Dolgui A., G. Morel, C. E. Pereira. – Saint-Etienne : Elsevier Science, 2006. – Vol. 3. – P. 129 – 134.
16. Sotskov Y. N. NP-hardness of shop-scheduling problems with three jobs / Y. N. Sotskov, N. V. Shakhlevich // Discrete Appl. Math. –1995. – Vol. 59, N 3. – P. 237–266.