Москва, г. Москва и Московская область, Россия
Задача сокращения продолжительности проекта в условиях ограниченных возобновляемых ресурсов (RCPSP) уже более 50 лет является одной из самых популярных тем исследований в области математических моделей управления проектами. На сегодняшний день применение точных оптимизационных методов на практике оказывается невозможным, поэтому для решения этой задачи используют эвристические методы. Среди множества эвристических методов значительную долю занимают так называемые многопроходные методы формирования расписания, основанные на последовательном применении разных эвристических правил разрешения ресурсных конфликтов к одному и тому же проекту. Если при этом каждое новое расписание получается с использованием случайных чисел, то говорят о сэмплировании. В этой статье будет сделан обзор существующих методов сэмплирования и проведено исследование их эффективности на базе проектов PSPLIB. Кроме того, получено подтверждение, что при большом количестве итераций в методе сэмплирования параллельные схемы превосходят последовательные, и построен новый метод сэмплирования, комбинирующий различные схемы и правила приоритета.
расписание проекта, ограниченные ресурсы, сэмплирование, продолжительность проекта.
1. Введение
Практически в каждом проекте есть ограничения на использование возобновляемых ресурсов. Такими ресурсами обычно являются: труд отдельных специалистов и исполнителей, выполняющх работы проекта; машино-часы дорогостоящего или редкого оборудования (например, суперкомпьютеров) и другие ресурсы, которых можно потратить только ограниченное количество в каждый период выполнения проекта. При использовании подобных ресурсов нередко возникают ресурсные конфликты, заставляющие либо задержать выполнение некоторых работ проекта до того момента времени, когда освободится нужный ресурс, либо тратить дополнительные деньги на привлечение еще одной единицы занятого ресурса. Здесь и далее мы будем считать, что второй вариант недоступен. Также будем предполагать, что нет возможности прерывать выполнение работ. В этих условиях будем решать задачу нахождения такой последовательности выполнения работ, при которой продолжительность проекта будет минимальна.
Задача сокращения продолжительности проекта в условиях ограниченных возобновляемых ресурсов (RCPSP) уже более 50 лет является одной из самых популярных тем исследований в области математических моделей управления проектами. Одна из самых первых попыток решения этой проблемы связана с методом критического пути [9]. Было предложено для разрешения ресурсных конфликтов задерживать выполнение той работы, у которой полный резерв, рассчитанный по методу критического пути (МКП) без учета ограничений на ресурсы, оказывался больше. Как показали многочисленные исследования [2; 3; 12; 6], такое правило SLK (с небольшими уточнениями) оказалось одним из самых лучших эвристических правил. Только в 1996 г. профессором Р. Колишем [12] было предложено правило WCS (Worst Case Slack), которое превзошло по эффективности SLK.
1. Царьков И.Н. Исследование эффективности методов оптимизации проекта с ограниченными ресурсами. Ч. 1 // Научные исследования и разработки. Российский журнал управления проектами. 2013. Т. 2. № 3. С. 13-25. DOI:https://doi.org/10.12737/1240.
2. Царьков И.Н. Исследование эффективности методов оптимизации проекта с ограниченными ресурсами. Ч. 2 // Научные исследования и разработки. Российский журнал управления проектами. 2013. Т. 2. № 4. С. 3-13. DOI:https://doi.org/10.12737/1958.
3. Alvarez-Valdés, Tamarit. Chapter 5 - Heuristic Algorithms for Resource-Constrained Project Scheduling: A Review and an Empirical Analysis // Advances in Project Scheduling Studies in Production and Engineering Economics / Под ред. R. Sowiski, J. Wglarz. Oxford: Elsevier, 1989. P. 113-134.
4. Blazewicz J. Scheduling Subject to Resource Constraints: Classification and Complexity. Brussels: European Institute for Advanced Studies in Management, 1980.
5. Cooper D.F. Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation // Manag. Sci. 1976. Т. 22. № 11. P. 1186-1194.
6. Davis E.W., Patterson J.H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling // Manag. Sci. 1975. Т. 21. № 8. P. 944-955.
7. Drexl A. и др. ProGen/πx - An instance generator for resourceconstrained project scheduling problems with partially renewable resources and further extensions // Eur. J. Oper. Res. 2000. Т. 125. № 1. P. 59-72.
8. Drexl A. Scheduling of Project Networks by Job Assignment // Manag. Sci. 1991. Т. 37. № 12. С. 1590-1602.
9. Kelley J.E. Jr, Walker M.R. Critical-path Planning and Scheduling // Papers Presented at the December 1-3, 1959, Eastern Joint IRE-AIEE-ACM Computer Conference IREAIEE-ACM ’59 (Eastern). New York, NY, USA: ACM, 1959. С. 160-173.
10. King G.W. The Monte Carlo Method as a Natural Mode of Expression in Operations Research // J. Oper. Res. Soc. Am. 1953. Т. 1. № 2. P. 46-51.
11. Kolisch R., Drexl A. Adaptive search for solving hard project scheduling problems // Nav. Res. Logist. NRL. 1996. Т. 43. № 1. P. 23-40.
12. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem // J. Oper. Manag. 1996a. Т. 14. № 3. P. 179-192.
13. Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation // Eur. J. Oper. Res. 1996b. Т. 90. № 2. P. 320-333.
14. Kolisch R., Sprecher A., Drexl A. Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems // Instituten fur Betriebswirtschaftslehre der Universit at Kiel, 1992.
15. Kolisch R., Sprecher A. PSPLIB - A project scheduling problem library: OR Software - ORSEP Operations Research Software Exchange Program // Eur. J. Oper. Res. 1996. Т. 96. № 1. P. 205-216.
16. Pritsker A.A.B., Watters L.J. A zero-one programming approach to scheduling with limited resources. Santa Monica, Calif.: Rand Corp., 1968.
17. Schirmer A. Case-Based Reasoning and Improved Adaptive Search for Project Scheduling. University of Kiel, Germany, 1998. Вып. Manuskripte aus den Instituten far Betriebswirtschaftslehre der Universitat Kiel.
18. Schirmer A. Resource-constrained project scheduling: An evaluation of adaptive control schemes for parameterized sampling heuristics // Int. J. Prod. Res. 2001. Т. 39. № 7. С. 1343-1365.
19. Schirmer A., Riesenberg S. Parameterized Heuristics for Project Scheduling - Biased Random Sampling Methods. University of Kiel, Germany, 1997. Вып. Manuskripte aus den Instituten fur Betriebswirtschaftslehre der Universitat Kiel.
20. Tormos P., Lova A. An efficient multi-pass heuristic for project scheduling with constrained resources // Int. J. Prod. Res. 2003. Т. 41. № 5. С. 1071-1086.
