Том 21, номер 3, 2014 г., Стр. 11–24

УДК 519.8
Гончаров Е. Н.
Стохастический жадный алгоритм для задачи календарного планирования с ограниченными ресурсами

Аннотация:
Рассматривается многономенклатурная одномодальная задача календарного сетевого планирования в условиях ограниченных ресурсов по критерию минимизации срока выполнения проекта. Ресурсы предполагаются возобновимыми (нескладируемыми). В работе предлагается быстрый стохастический алгоритм, разработанный на основе малотрудоёмкого детерминированного жадного алгоритма решения данной задачи. Качество алгоритма исследовано в серии вычислительных экспериментов, тестовые примеры для которых были взяты из библиотеки тестовых задач PSPLIB. Среди жадных алгоритмов предложенный алгоритм занимает одни из лучших позиций, а на тестовых примерах J60 из PSPLIB по 50000 испытаний он показал лучший результат. Среди всех алгоритмов он оказался конкурентоспособным, уступив лишь генетическим алгоритмам и комбинированным на их основе.
Ил. 1, табл. 4, библиогр. 33.

Ключевые слова: задача календарного планирования, ограниченный ресурс, нескладируемый ресурс, эвристический алгоритм.

Гончаров Евгений Николаевич ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gon@math.nsc.ru

Статья поступила 30 августа 2013 г.
Исправленный вариант — 29 января 2014 г.

Литература

[1] Гимади Э. Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. T. 10. - Новосибирск: Наука, 1988. - C. 89–115.

[2] Гимади Э. Х., Гончаров Е. Н., Залюбовский В. В.,Пляскина Н. И., Харитонова В. Н. О программно-математическом обеспечении для задачи ресурсно-календарного планирования Восточно-Сибирского нефтегазового комплекса // Вестн. НГУ. Сер. Математика, механика,
информатика. - 2010. - Т. 10, вып. 4. - C. 51–67.

[3] Гимади Э. Х., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискрет. анализ и исслед. операций. Сер. 2. - 2000. - Т. 7, №1. - С. 9–34.

[4] Гимади Э. X., Пузынина Н. М., Севастьянов С. В. О некоторых экстремальных задачах реализации крупных проектов типа БАМ // Экономика и мат. методы. - 1979. - Т. 15, вып. 5. – С. 1017–1021.

[5] Кочетов Ю. А., Столяр А. А. Использование чередующихся окрестностей для приближённого решения задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. Сер. 2. - 2003. - Т. 10, №2. - С. 29–55.

[6] Кочетов Ю. А., Столяр А. А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. Сер. 2. - 2005. - Т. 12, №1. - С. 12–6.

[7] Blazewicz J., Lenstra J. K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: classification and complexity // Discrete Appl. Math. - 1983. - Vol. 5, N1. - P. 11–24.

[8] Bouleimen K., Lecocq H. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version // Eur. J. Oper. Res. - 2003. - Vol. 149, N2. - P. 268–281.

[9] Brucker P., Drexl A., Möhring R., Neumann K., Pesch E. Resource-constrained project scheduling: notation, classification, models, and methods // Eur. J. Oper. Res. - 1999. - Vol. 112, N1. - P. 3–41.

[10] Coelho J., Tavares L. Competitive analysis of metaheuristics for the resource constrained project scheduling problem // Tech. Report, Department of Civil Engineering, Instituto Superior Tecnico, Portugal, 2003.

[11] Debels D., De Reyck Leus B. R., Vanhoucke M. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling // Eur. J. Oper. Res. - 2006. - Vol. 169. - P. 638–653.

[12] Debels D., Vanhoucke M. Decomposition-based genetic algorithm for the resource-consrtained project scheduling problem // Oper. Res. - 2007. - Vol. 55. - P. 457–469.

[13] Gimadi E. Kh., Sevastianov S. V. On solvability of the project scheduling problem with accumulative resources of an arbitrary sign // Proc. Oper. Res., 2002. - Berlin; Heidelberg; New York: Springer-Verl., 2003. - P. 241–246.

[14] Goncharov E. N. A greedy heuristic approach for the resource-constrained project scheduling problem // Stud. Informatica Universalis. - 2012. - Vol. 9, N3. - P. 79–90.

[15] Hartmann S. A competitive genetic algorithm for resource-constrained project scheduling // Naval Res. Logist. - 1998. - Vol. 45. - P. 733–750.

[16] Hartmann S. A self-adapting genetic algorithm for project scheduling under resource constraints // Naval Res. Logist. - 2002. - V. 49. - P. 433–448.

[17] Hartmann S., Briskorn D. A survey of variants and extentions of the resource-constrained project scheduling problem // Eur. J. Oper. Res. - 2010. - Vol. 207. - P. 1–14.

[18] Kolisch R. Efficient priority rules for the resource constrained project scheduling problem // J. Oper. Manage. - 1996. - Vol. 14. - P. 179–192.

[19] Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: theory and computation // Eur. J. Oper. Res. - 1996. - Vol. 90. - P. 320–333.

[20] Kolisch R., Drexl A. Adaptive search for solving hard project scheduling problems // Naval Res. Logist. - 1996. - Vol. 43, N1. - P. 23–40.

[21] Kolisch R., Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: an update // Eur. J. Oper. Res. - 2006. - Vol. 174. - P. 23–37.

[22] Kolisch R., Hartmann S. Heuristic algorithms for solving the resource- constrained project scheduling problem: classification and computational analysis // Project scheduling: recent models, algorithms and applications. - Berlin: Kluwer Acad. Publ., 1999. - P. 147–178.

[23] Kolisch R., Sprecher A. PSPLIB - a project scheduling problem library // Eur. J. Oper. Res. - 1996. - Vol. 96, N1. - P. 205–216.

[24] LiR. Y., Willis J. An iterative scheduling technique for resource-constrained project scheduling // Eur. J. Oper. Res. - 1992. - Vol. 56. - P. 370–379.

[25] Nonobe K., Ibaraki T. Formulation and tabu search algorithm for the resource constrained project scheduling problem // Essays and surveys in metaheuristics. - Boston: Kluwer Acad. Publ., 2002. - P. 557–588.

[26] Ozdamar L., Ulusoy G. A note on an iterative forward/backward scheduling technique with reference to a procedure by Li and Willis // Eur. J. Oper. Res. - 1996. - Vol. 89. - P. 400–407.

[27] Proon S., Jin M. A genetic algorithm with neighborhood search for the resource-constrained project scheduling problem // Naval Res. Logist. - 2011. - Vol. 58. - P. 73–82.

[28] Schirmer A. Case-based reasoning and improved adaptive search for project scheduling // Naval Res. Logist. - 2000. - Vol. 47, N3. - P. 201–222.

[29] Tormos P., Lova A. Integrating heuristics for resource-constrained project scheduling: One step forward // Tech. Report, Department of Statistics and Operations Research, Universidad Politecnica de Valencia, 2003.

[30] Tormos P., Lova A. An efficient multi-pass heuristic for project scheduling with constrained resources // Int. J. Production Res. - 2003. - Vol. 41, N 5. - P. 1071–1086.

[31] Tormos P., Lova A. A competitive heuristic solution techniques for resource-constrained project scheduling // Ann. Oper. Res. - 2001. - Vol. 102. - P. 65–81.

[32] Valls V., Ballestin F., Quintanilla S. Justification and RCPSP: a technique that pays // Eur. J. Oper. Res. - 2005. - Vol. 165, N2. - P. 375–386.

[33] Valls V., Ballestin F., Quintanilla S. A hybrid genetic algorithm for the resource-constrained project scheduling problem // Eur. J. Oper. Res. - 2008. - Vol. 185, N2. - P. 495–508.