Об одном методе ранжирования ресурсов для задачи календарного планирования с ограниченными ресурсами

Об одном методе ранжирования ресурсов для задачи календарного планирования с ограниченными ресурсами

Гимади Э. Х., Гончаров Е. Н.
Дискретный анализ и исследование операций, 33, 2, 5-18 (2026)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2026.33.864

Аннотация:

Рассматривается задача календарного планирования с ограниченными ресурсами по критерию минимума длины расписания. Все ресурсы возобновимы, прерывания операций (работ) не допускаются. Эта задача NP-трудна в сильном смысле. Ограниченность ресурсов лежит в основе сложности её решения. К числу перспективных для решения этой задачи относят эвристические алгоритмы. В данной работе предлагается ранжировать ресурсы по степени их критичности (дефицитности). Эвристические алгоритмы могут использовать это ранжирование ресурсов для построения сравнительно лучших эвристических решений. Ранжирование ресурсов получаем из релаксированной задачи, в которой ресурсы складируемы. Предложенный метод ранжирования ресурсов был применён в генетическом алгоритме. Вычислительные эксперименты на примерах из электронной библиотеки PSPLIB показали его эффективность. Для нескольких примеров из PSPLIB найдены новые лучшие (ранее неизвестные) решения. 

Табл. 1, библиогр. 17.

Литература:
  1. Brucker P., Drexl A., Möhring R., Neumann K., Pesch E. Resourceconstrained project scheduling: Notation, classification, models, and methods // Eur. J. Oper. Res. 1999. V. 112, No. 1. P. 3–41.
     
  2. Herroelen W., Demeulemeester E., De Reyck B. A classification scheme for project scheduling // Project scheduling: Recent models, algorithms and applications. Dordrecht: Kluwer Acad. Publ., 1999. P. 1–26.
     
  3. Błażewicz J., Lenstra J. K., Rinnoy Kan A. H. G. Scheduling subject to resource constraints: Classification and complexity // Discrete Appl. Math. 1983. V. 5, No. 1. P. 11–24.
     
  4. Kolisch R., Sprecher A. PSPLIB — A project scheduling problem library // Eur. J. Oper. Res. 1996. V. 96. P. 205–216.
     
  5. Hartmann S., Briskorn D. A survey of variants and extentions of the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2010. V. 207. P. 1–14.
     
  6. Kolisch R., Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: An update // Eur. J. Oper. Res. 2006. V. 174, No. 1. P. 23–37.
     
  7. Herroelen W., Leus R. Robust and reactive project scheduling: A review and classification of procedures // Int. J. Prod. Res. 2004. V. 42, No. 8. P. 1599–1620.
     
  8. Golab A., Sedgh Gooya E., Al Falou A., Cabon M. Review of conventional metaheuristic techniques for resource-constrained project scheduling problem // J. Proj. Manag. 2022. V. 7, No. 2. P. 95–110. DOI: 10.5267/j. jpm.2021.10.002.
     
  9. Pellerin R., Perrier N., Berthaut F. A survey of hybrid metaheuristics for the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2020. V. 280, No. 2. P. 395–416. DOI: 10.1016/j.ejor.2019.01.063.
     
  10. Abdolshah M. A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions // Int. Trans. J. Eng. Manag. Appl. Sci. Technol. 2014. V. 5, No. 4. P. 253–286.
     
  11. Hartmann S., Briskorn D. An updated survey of variants and extensions of the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2022. V. 297, No. 1. P. 1–14. DOI: 10.1016/j.ejor.2021.05.004.
     
  12. Khajesaeedi S., Sadjadi S., Barzinpour F., Tavakkoli-Moghaddam R. Resource-constrained project scheduling problem: Review of recent developments // J. Proj. Manag. 2025. V. 10, No. 1. P. 1–26. DOI: 10.5267/j.jpm. 2024.12.002.
     
  13. Coelho J., Vanhoucke M. Going to the core of hard resource-constrained project scheduling instances // Comput. Oper. Res. 2020. V. 121. Article ID 104976. 13 p. DOI: 10.1016/j.cor.2020.104976.
     
  14. Гончаров Е. Н. Жадный алгоритм для задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 4. С. 27–39. DOI: 10.33048/daio.2024.31.796.
     
  15. Гончаров Е. Н., Леонов В. В. Генетический алгоритм для задачи календарного планирования с ограниченными ресурсами // Автоматика и телемеханика. 2017. № 6. С. 173–189.
     
  16. Гимади Э. Х., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискрет. анализ и исслед. операций. Сер. 2. 2000. Т. 7, № 1. С. 9–34.
     
  17. Гимади Э. Х., Гончаров Е. Н., Штепа А. А. Быстрый алгоритм вычисления нижней оценки для решения задачи ресурсно-календарного планирования с тестированием на примерах библиотеки PSPLIB // Тр. Ин-та математики и механики. 2021. Т. 27, № 1. С. 22–36. DOI: 10.21538/ 0134-4889-2021-27-1-22-36.

Работа выполнена в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2026–0021). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Гимади Эдуард Хайрутдинович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: gimadi@math.nsc.ru 

Гончаров Евгений Николаевич
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: gon@math.nsc.ru 

Статья поступила 8 апреля 2026 г.
После доработки — 15 апреля 2026 г.
Принята к публикации 22 апреля 2026 г.

Abstract:

We consider a resource-constrained project scheduling problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints on activities precedence together with resource constraints. Activities preemptions are not allowed. The problem with renewable resources is NP-hard in the strong sense. Metaheuristics are one of the promising methods for solving this problem. We propose a new method for identifying the most scarce resources, which helps metaheuristics to overcome these resource conflicts and find better solutions. The proposed resource ranking method is applied in a genetic algorithm. Computational experiments with instances from the PSPLIB electronic library showed its effectiveness. New solutions are obtained for several instances, while new best (previously unknown) solutions are found for one instance from j90 and four instances from j120 datasets. 

Tab. 1, bibliogr. 17.

References:
  1. P. Brucker, A. Drexl, R. Möhring, K. Neumann, and E. Pesch, Resource-constrained project scheduling: Notation, classification, models, and methods, Eur. J. Oper. Res. 112 (1), 3–41 (1999).
     
  2. W. Herroelen, E. Demeulemeester, and B. De Reyck, A classification scheme for project scheduling, in Project Scheduling: Recent Models, Algorithms and Applications (Kluwer Acad. Publ., Dordrecht, 1999), pp. 1–26.
     
  3. J. Błażewicz, J. K. Lenstra, and A. H. G. Rinnoy Kan, Scheduling subject to resource constraints: Classification and complexity, Discrete Appl. Math. 5 (1), 11–24 (1983).
     
  4. R. Kolisch and A. Sprecher, PSPLIB — A project scheduling problem library, Eur. J. Oper. Res. 96, 205–216 (1996).
     
  5. S. Hartmann and D. Briskorn, A survey of variants and extentions of the resource-constrained project scheduling problem, Eur. J. Oper. Res. 207, 1–14 (2010).
     
  6. R. Kolisch and S. Hartmann, Experimental investigation of heuristics for resource-constrained project scheduling: An update, Eur. J. Oper. Res. 174 (1), 23–37 (2006).
     
  7. W. Herroelen and R. Leus, Robust and reactive project scheduling: A review and classification of procedures, Int. J. Prod. Res. 42 (8), 1599–1620 (2004).
     
  8. A. Golab, E. Sedgh Gooya, A. Al Falou, and M. Cabon, Review of conventional metaheuristic techniques for resource-constrained project scheduling problem, J. Proj. Manag. 7 (2), 95–110 (2022), DOI: 10.5267/j.jpm.2021.10.002.
     
  9. R. Pellerin, N. Perrier, and F. Berthaut, A survey of hybrid metaheuristics for the resource-constrained project scheduling problem, Eur. J. Oper. Res. 280 (2), 395–416 (2020), DOI: 10.1016/j.ejor.2019.01.063.
     
  10. M. Abdolshah, A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions, Int. Trans. J. Eng. Manag. Appl. Sci. Technol. 5 (4), 253–286 (2014).
     
  11. S. Hartmann and D. Briskorn, An updated survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res. 297 (1), 1–14 (2022), DOI: 10.1016/j.ejor.2021.05.004.
     
  12. S. Khajesaeedi, S. Sadjadi, F. Barzinpour, and R. Tavakkoli-Moghaddam, Resource-constrained project scheduling problem: Review of recent developments, J. Proj. Manag. 10 (1), 1–26 (2025), DOI: 10.5267/j.jpm.2024.12.002.
     
  13. J. Coelho and M. Vanhoucke, Going to the core of hard resource-constrained project scheduling instances, Comput. Oper. Res. 121, ID 104976 (2020), DOI: 10.1016/j.cor.2020.104976.
     
  14. E. N. Goncharov, A greedy algorithm for the resource-constrained project scheduling problem, Diskretn. Anal. Issled. Oper. 31 (4), 27–39 (2024) [Russian], DOI: 10.33048/daio.2024.31.796 [J. Appl. Ind. Math. 18 (4), 679–685 (2024)].
     
  15. E. N. Goncharov and V. V. Leonov, A genetic algorithm for the resourceconstrained project scheduling problem, Avtom. Telemekh., No. 6, 173–189 (2017) [Russian] [Autom. Remote Control 78 (6), 1101–1114 (2017)].
     
  16. É. Kh. Gimadi, V. V. Zalyubovskiy, and S. V. Sevast’yanov, Polynomial solvability of scheduling problems with storable resources and directive deadlines, Diskretn. Anal. Issled. Oper., Ser. 2, 7 (1), 9–34 (2000) [Russian].
     
  17. É. Kh. Gimadi, E. N. Goncharov, and A. A. Shtepa, A fast algorithm for finding a lower bound of the solution to the resource-constrained project scheduling problem tested on PSPLIB instances, Tr. Inst. Mat. Mekh. 27 (1), 22–36 (2021), DOI: 10.21538/0134-4889-2021-27-1-22-36 [Russian].