Э.Х. Гимади, Е.Н. Гончаров, А.А. Штепа. Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB... С. 22-36

УДК 519.8

MSC: 90C10, 90B35

DOI: 10.21538/0134-4889-2021-27-1-22-36

Полный текст статьи (Full text)

Работа выполнена при поддержке программы фундаментальных исследований СО РАН I.5.1 (проект 0314-2019-0014) и РФФИ (проект 20-31-90091).

В статье рассматривается труднорешаемая задача ресурсно-календарного планирования (ЗРКП). Предполагается, что функции интенсивности выделения и потребления ресурсов постоянны в заданных временн$\acute{\mbox{ы}}$х  интервалах, а директивные сроки отсутствуют. Построена процедура вычисления нижней оценки длины расписания ЗРКП на основе релаксации задачи (посредством замены нескладируемых ресурсов на складируемые). Временн$\acute{\mbox{а}}$я сложность этой процедуры зависит от числа работ $n$ как функция $\mathcal O(n \log{n})$. Из анализа численных расчетов (проведенных на примерах задач из электронной библиотеки PSPLIB) следует  высокая конкурентоспособность предлагаемой процедуры, дающей в некоторых сериях задач результаты, близкие к лучшим значениям нижних оценок, опубликованных в библиотеке PSPLIB, при чрезвычайно малом процессорном времени (миллисекунды).

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

СПИСОК ЛИТЕРАТУРЫ

1.   Baptiste P., Pape C.L. Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems // Constraints. 2000. Vol. 5. P. 119–139. doi: 10.1023/A:1009822502231 

2.   Blazewicz J., Lenstra J.K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity // Discrete Applied Math. Vol. 5, no. 1. 1983. P. 11–24. doi: 10.1016/0166-218X(83)90012-4 

3.   Bottcher J., Drexl A., Salewski F. Project scheduling under partially renewable resource constraints // Management Science. 1999. Vol. 45, no. 4. P. 543–559. doi: 10.1007/s10732-006-5224-6 

4.   Brucker P., Drexl A., M$\ddot{\mathrm{o}}$hring R., et al. Resource-Constrained Project Scheduling: Notation, classification, models, and methods // Eur. J. Oper. Res. 1999. Vol. 112, no. 1. P. 3–41.

5.   Gafarov E., Lazarev A., Werner F. On lower and upper bounds for the Resource-Constrained Project Scheduling Problem. Technical report. Magdeburg: Otto-von-Guericke Universitaet, 2010. 27 p.

6.   Hartmann S., Kolisch R. Experimental evaluation of state-of-the-art heuristics for the Resource-Constrained Project Scheduling Problem // Eur. J. Oper. Res. 2000. Vol. 127, no. 2. P. 394–407.

7.   Herroelen W., Demeulemeester E., De Reyck B.A. Classification scheme for project scheduling // Project Scheduling-Recent Models, Algorithms and Applications. Dordrecht: Kluwer Acad. Pub., 1998. P. 77–106. (International Ser. Oper. Research and Management Sci.; vol. 14.) doi: 10.1007/978-1-4615-5533-9_1 

8.   Knust S. Lower bounds on the minimum project duration // Handbook on project management and scheduling. Cham: Springer, 2015. Vol. 1, chap. 3. P. 43–56. doi: 10.1007/978-3-319-05443-8_3 

9.   Kolisch R., Sprecher A. PSPLIB — a Project Scheduling Problem Library // Eur. J. Oper. Res. 1996. Vol. 96. P. 205–216. doi: 10.1016/S0377-2217(96)00170-1 

10.   Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of Resource-Constrained Project Scheduling Problems // Manage Science. 1995. Vol. 41. P. 1693–1703. doi: 10.1287/mnsc.41.10.1693 

11.   Neron E., Artigues C., Baptiste P., Carlier J., Damay J., Demassey S., Laborie P. Lower bounds for Resource Constrained Project Scheduling Problem // Perspectives in modern project scheduling. Chap. 7. Cham: Springer, 2006. P. 167–204. doi: 10.1007/978-0-387-33768-5_7 

12.   Neumann K., Schwindt C., Trautmann N. Scheduling of continuous and discontinuous material flows with intermediate storage restrictions // European J. Oper. Research. 2005. Vol. 165, no. 2. P. 495–509.

13.   Shirzadeh Chaleshtarti A., Shadrokh S., Fathi Y. Branch and bound algorithms for Resource Constrained Project Scheduling Problem subject to nonrenewable resources with prescheduled procurement // Mathematical Problems in Engineering. Hindawi Publishing Corporation. 2014. Vol. 2014. doi: 10.1155/2014/634649 

14.   Valls, V., Ballestin, F., Quintanilla, S. A hybrid genetic algorithm for the Resource-Consrtained Project Scheduling Problem // Eur. J. Oper. Res. 2008. Vol. 185, no. 2. P. 495–508.

15.   Weglarz, J. Project scheduling. Recent models, algorithms and applications. Boston: Kluwer Acad. Publ, 1999. 535 p. doi: 10.1007/978-1-4615-5533-9 

16.   Алексеев А.М., Гимади Э.Х., Перепелица В.А. Математические модели календарного планирования и управления долгосрочными проектами (на примере БАМ) // Проблемы строительства магистрали и развития строительной базы для хозяйственного освоения зоны БАМ, Новосибирск, 1977: Тр. II Всесоюзной конференции по проблемам хозяйственного освоения зоны БАМ. Благовещенск, 1977. С. 118–126.

17.   Гимади Э.Х., Пузынина Н.М. Задача календарного планирования крупномасштабного проекта в условиях ограниченных ресурсов: опыт построения математического обеспечения // Управляемые системы. Новосибирск,1983. Вып. 23. С. 24–32.

18.   Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации: тр. / АН СССР. Сиб. Отд-ние. Ин-т математики. Новосибирск: Наука, 1988. Т. 10. С. 89–115.

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

20.   Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. М.: Наука, 1965. 296 с.

21.   Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. Классика Computers Science / пер. с англ. Е. Матвеева. СПб.: Питер, 2016. 800 с.

22.   Козлов М.К., Шафранский В.В. Календарное планирование выполнения комплексов работ при заданной динамике поступления складируемых ресурсов // Изв. АН СССР. Техническая кибернетика. 1977. № 4. С. 75–81.

Поступила 25.09.2020

После доработки 20.02.2021

Принята к публикации 26.02.2021

Гимади Эдуард Хайрутдинович
д-р физ.-мат. наук, профессор
главный научный сотрудник
Институт математики им. С. Л. Соболева СО РАН
г. Новосибирск
e-mail: gimadi@math.nsc.ru

Гончаров Евгений Николаевич
канд. физ.-мат. наук
старший научный сотрудник
Институт математики им. С. Л. Соболева СО РАН
г. Новосибирск
e-mail: gon@math.nsc.ru

Штепа Александр Александрович
аспирант
Новосибирский национальный исследовательский государственный университет (НГУ)
г. Новосибирск
e-mail: shoomath@gmail.com

Ссылка на статью: Э.Х. Гимади, Е.Н. Гончаров, А.А. Штепа. Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB // Тр. Ин-та математики и механики УрО РАН. 2021. Т 27, № 1. С. 22-36.

English

E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances

We consider the intractable Resource-Constrained Project Scheduling Problem (RCPSP). It is assumed that the intensity functions of resource allocation and consumption are constant on specified time intervals and there are no deadlines. The procedure for calculating the lower bound for the RCPSP is constructed on the basis of the relaxation of the problem by replacing renewable resources with cumulative ones. The time complexity of this procedure depends on the number of activities $n$ as a function of $\mathcal O(n\log{n})$. From the analysis of numerical experiments (which are carried out on examples of problems from the electronic library PSPLIB), it follows that the proposed procedure is highly competitive, and in some series of instances gives results close to the best lower bounds published in the PSPLIB with dramatically small CPU time (milliseconds).

Keywords: project management, Resource-Constrained Project Scheduling Problem, renewable resources, cumulative resources, PSPLIB, lower bound

Received September 25, 2020

Revised February 20, 2021

Accepted February 26, 2021

Funding Agency: This work was supported by the Program for Fundamental Research of the Siberian Branch of the Russian Academy of Sciences (project no. 0314-2019-0014) and by the Russian Foundation for Basic Research (project no. 20-31-90091).

Edward Khairutdinovich Gimadi, Dr. Phys.-Math. Sci., Prof., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gimadi@math.nsc.ru

Evgenii Nikolaevich Goncharov, Cand. Phys.-Math. Sci., Sobolev Institute of Mathematics of the Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090 Russia, e-mail: gon@math.nsc.ru

Alexandr Alexandrovich Shtepa, doctoral student, Novosibirsk State University (NSU), Novosibirsk, 630090 Russia, e-mail: shoomath@gmail.com

Cite this article as: E.Kh. Gimadi, E.N. Goncharov, A.A. Shtepa. A fast algorithm for finding a lower bound of the solution of the Resource-Constrained Project Scheduling Problem tested on PSPLIB instances, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 1, pp. 22–36.

[References -> on the "English" button bottom right]