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

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

Гончаров Е. Н.
Дискретный анализ и исследование операций, 31, 4, 27-39 (2024)
Скачать статью

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

Аннотация:

Задача календарного планирования с ограниченными ресурсами — достаточно общая задача теории расписаний, которая включает в себя ограничения предшествования работ и ресурсные ограничения. Все ресурсы возобновимы, прерывания работ запрещены. Эта задача NP-трудна в сильном смысле. Мы предлагаем новый детерминированный жадный алгоритм. Он основан на эвристике, использующей информацию, полученную в результате решения релаксированной задачи с кумулятивными ресурсами. Алгоритм протестирован на стандартных наборах данных j60, j90 и j120, предоставляемых библиотекой PSPLIB; показана его эффективность. 
Табл. 2, библиогр. 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. Blażewicz J., Lenstra J. K., Rinnooy 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., Hartmann S. Heuristic algorithms for solving the resource-constrained project scheduling problem: Classification and computational analysis // Project scheduling: Recent models, algorithms and applications. Dordrecht: Kluwer Acad. Publ., 1999. P. 147–178.
     
  5. 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.
     
  6. Abdolshah M. A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions // Int. Trans. J. Eng. Manage. Appl. Sci. Technol. 2014. V. 5, No. 4. P. 253–286.
     
  7. Vanhoucke M. Resource-constrained project scheduling // Project management with dynamic scheduling. Heidelberg: Springer, 2012. P. 107–137.
     
  8. Hartmann S., Briskorn D. A survey of variants and extensions of the resource-constrained project scheduling problem // Eur. J. Oper. Res. 2010. V. 207, No. 1. P. 1–14.
     
  9. Кочетов Ю. А., Столяр А. А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. Сер. 2. 2005. Т. 12, № 1. С. 12–36.
     
  10. Гончаров Е. Н. Стохастический жадный алгоритм для задачи календарного планирования с ограниченными ресурсами // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 3. C. 10–23.
     
  11. Kolisch R., Sprecher A. PSPLIB — A project scheduling problem library // Eur. J. Oper. Res. 1996. V. 96, No. 1. P. 205–216.
     
  12. Гимади Э. Х., Залюбовский В. В., Севастьянов С. В. Полиномиальная разрешимость задач календарного планирования со складируемыми ресурсами и директивными сроками // Дискрет. анализ и исслед. операций. 2000. Сер. 2. Т. 7, № 1. С. 9–34.
     
  13. Гимади Э. Х. О некоторых математических моделях и методах планирования крупномасштабных проектов // Модели и методы оптимизации. Тр. АН СССР. Сиб. отд-ние. Ин-т математики. Вып. 10. Новосибирск: Наука, 1988. С. 89–115.
     
  14. Gimadi Eh. Kh., Sevastianov S. V. On solvability of the project scheduling problem with accumulative resources of an arbitrary sign // Operations research proceedings 2002. Sel. Pap. Int. Conf. Operations Research (Klagenfurt, Austria, Sept. 2–5, 2002). Heidelberg: Springer, 2003. P. 241–246.
     
  15. Li K. Y., Willis R. J. An iterative scheduling technique for resource-constrained project scheduling // Eur. J. Oper. Res. 1992. V. 56, No. 3. P. 370–379.
     
  16. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems // INFORMS Manage. Sci. 1995. V. 41. P. 1693–1703.
     
  17. Project scheduling: Recent models, algorithms and applications. Dordrecht: Kluwer Acad. Publ., 1999. 546 p.

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

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

E-mail: gon@math.nsc.ru

Статья поступила 21 февраля 2024 г
После доработки — 27 апреля 2024 г.
Принята к публикации 22 июня 2024 г.

Abstract:

The resource-constrained project scheduling problem (briefly RCPSP) is a general scheduling problem that includes precedence and resource constraints. Activities preemptions are not allowed. Resources are renewable and there is a unique way to perform the activities. The problem with renewable resources is NP-hard in the strong sense. We propose a new deterministic greedy algorithm. It is based on heuristics that use information obtained from a relaxing problem. The algorithm is tested with standard data sets given by Kolisch library PSPLIB for j60, j90, and j120 and found to be performing well. 
Tab. 2, 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. Blażewicz, J. K. Lenstra, and A. H. G. Rinnooy Kan, Scheduling subject to resource constraints: Classification and complexity, Discrete Appl. Math. 5 (1), 11–24 (1983).
     
  4. R. Kolisch and S. Hartmann, Heuristic algorithms for solving the resourceconstrained project scheduling problem: Classification and computational analysis, in Project Scheduling: Recent Models, Algorithms and Applications (Kluwer Acad. Publ., Dordrecht, 1999), pp. 147–178.
     
  5. 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).
     
  6. M. Abdolshah, A review of resource-constrained project scheduling problems (RCPSP) approaches and solutions, Int. Trans. J. Eng. Manage. Appl. Sci. Technol. 5 (4), 253–286 (2014).
     
  7. M. Vanhoucke, Resource-constrained project scheduling, in Project Management with Dynamic Scheduling (Springer, Heidelberg, 2012), pp. 107–137.
     
  8. S. Hartmann and D. Briskorn, A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Oper. Res. 207 (1), 1–14 (2010).
     
  9. Yu. A. Kochetov and A. A. Stolyar, New greedy heuristics for the scheduling problem with constrained resources, Diskretn. Anal. Issled. Oper., Ser. 2, 12 (1), 12–36 (2005) [Russian].
     
  10. E. N. Goncharov, A stochastic greedy algorithm for the resource-constrained project scheduling problem, Diskretn. Anal. Issled. Oper. 21 (3), 10–23 (2014) [Russian].
     
  11. R. Kolisch and A. Sprecher, PSPLIB — A project scheduling problem library, Eur. J. Oper. Res. 96 (1), 205–216 (1996).
     
  12. Eh. Kh. Gimadi, V. V. Zalyubovskii, and S. V. Sevastianov, Polynomial solvability of scheduling problems with storable resources and directive deadlines, Diskretn. Anal. Issled. Oper., Ser. 2, 7 (1), 9–34 (2000) [Russian].
     
  13. Eh. Kh. Gimadi, Some mathematical models and methods for scheduling large-scale projects, in Models and Methods of Optimization (Trudy AN SSSR, Sib. Otd., Inst. Mat., Vol. 10) (Nauka, Novosibirsk, 1988), pp. 89–115 [Russian].
     
  14. Eh. Kh. Gimadi and S. V. Sevastianov, On solvability of the project scheduling problem with accumulative resources of an arbitrary sign, in Operations Research Proceedings 2002 (Sel. Pap. Int. Conf. Operations Research, Klagenfurt, Austria, Sept. 2–5, 2002) (Springer, Heidelberg, 2003), pp. 241–246.
     
  15. K. Y. Li and R. J. Willis, An iterative scheduling technique for resourceconstrained project scheduling, Eur. J. Oper. Res. 56 (3), 370–379 (1992).
     
  16. R. Kolisch, A. Sprecher, and A. Drexl, Characterization and generation of a general class of resource-constrained project scheduling problems, INFORMS Manage. Sci. 41, 1693–1703 (1995).
     
  17. Project Scheduling: Recent Models, Algorithms and Applications (Kluwer Acad. Publ., Dordrecht, 1999).