Scientific Research and Development. Russian Journal of Project Management Scientific Research and Development. Russian Journal of Project Management Научные исследования и разработки. Российский журнал управления проектами 2587-6279 3553 10.12737/5782 Методы и инструменты управления проектом Methods and instruments of project management Методы и инструменты управления проектом Sampling Methods’ Evolution in Problem of Duration Reduction of Project with Limited Resources Развитие методов сэмплирования в задаче сокращения продолжительности проекта с ограниченными ресурсами Царьков И. Н. Tsarkov Igor Nikolaevich igor_tsarkov@live.ru

кандидат экономических наук;

candidate of economic sciences;

 Национальный исследовательский университет «Высшая школа экономики» National Research University Higher School of Economics 17 09 2014 17 09 2014 3 3 14 24 https://naukaru.ru/en/nauka/article/3553/view

Задача сокращения продолжительности проекта в условиях ограниченных возобновляемых ресурсов (RCPSP) уже более 50 лет является одной из самых популярных тем исследований в области математических моделей управления проектами. На сегодняшний день применение точных оптимизационных методов на практике оказывается невозможным, поэтому для решения этой задачи используют эвристические методы. Среди множества эвристических методов значительную долю занимают так называемые многопроходные методы формирования расписания, основанные на последовательном применении разных эвристических правил разрешения ресурсных конфликтов к одному и тому же проекту. Если при этом каждое новое расписание получается с использованием случайных чисел, то говорят о сэмплировании. В этой статье будет сделан обзор существующих методов сэмплирования и проведено исследование их эффективности на базе проектов PSPLIB. Кроме того, получено подтверждение, что при большом количестве итераций в методе сэмплирования параллельные схемы превосходят последовательные, и построен новый метод сэмплирования, комбинирующий различные схемы и правила приоритета.

The project duration reduction problem in the conditions of limited renewable resources is one of the most popular themes within researches in area of project management’s mathematical models during more than 50 years. Nowadays applying of exact optimization methods in real practice is impossible, so heuristic methods are used in this problem resolution. Among a set of heuristic methods there is a considerable share of so-called multipass scheduling methods based on consecutive application of different heuristic rules of resource conflicts resolution to the same project. If at this each new schedule turns out with use of random numbers, they speak about sampling. In this paper a review of existing sampling methods will be made, and their efficiency research on the basis of PSPLIB projects will be conducted. Besides, has been received a confirmation that at a large number of iterations in a sampling method the parallel schemes surpass consecutive ones, and a new method of sampling combining various schemes and rules of priority has been constructed.

 расписание проекта ограниченные ресурсы сэмплирование продолжительность проекта. project schedule limited resources sampling project duration.

1. ВведениеПрактически в каждом проекте есть ограничения на использование возобновляемых ресурсов. Такими ресурсами обычно являются: труд отдельных специалистов и исполнителей, выполняющх работы проекта; машино-часы дорогостоящего или редкого оборудования (например, суперкомпьютеров) и другие ресурсы, которых можно потратить только ограниченное количество в каждый период выполнения проекта. При использовании подобных ресурсов нередко возникают ресурсные конфликты, заставляющие либо задержать выполнение некоторых работ проекта до того момента времени, когда освободится нужный ресурс, либо тратить дополнительные деньги на привлечение еще одной единицы занятого ресурса. Здесь и далее мы будем считать, что второй вариант недоступен. Также будем предполагать, что нет возможности прерывать выполнение работ. В этих условиях будем решать задачу нахождения такой последовательности выполнения работ, при которой продолжительность проекта будет минимальна.Задача сокращения продолжительности проекта в условиях ограниченных возобновляемых ресурсов (RCPSP) уже более 50 лет является одной из самых популярных тем исследований в области математических моделей управления проектами. Одна из самых первых попыток решения этой проблемы связана с методом критического пути [9]. Было предложено для разрешения ресурсных конфликтов задерживать выполнение той работы, у которой полный резерв, рассчитанный по методу критического пути (МКП) без учета ограничений на ресурсы, оказывался больше. Как показали многочисленные исследования [2; 3; 12; 6], такое правило SLK (с небольшими уточнениями) оказалось одним из самых лучших эвристических правил. Только в 1996 г. профессором Р. Колишем [12] было предложено правило WCS (Worst Case Slack), которое превзошло по эффективности SLK.

Царьков И.Н. Исследование эффективности методов оптимизации проекта с ограниченными ресурсами. Ч. 1 // Научные исследования и разработки. Российский журнал управления проектами. 2013. Т. 2. № 3. С. 13-25. DOI: 10.12737/1240. Tsar´kov I.N. Issledovanie effektivnosti metodov optimizatsii proekta s ogranichennymi resursami. Chast´ 1 [Evaluation of Methods for Optimizing a Resource-Constrained Project. Part 1]. Nauchnye issledovaniya i razrabotki. Rossiyskiy Zhurnal Upravleniya Proektami [Research and Development. Russian Journal of Project Management]. 2013, V. 2. I. 3, pp. 13-25. DOI: 10.12737/1240 Царьков И.Н. Исследование эффективности методов оптимизации проекта с ограниченными ресурсами. Ч. 2 // Научные исследования и разработки. Российский журнал управления проектами. 2013. Т. 2. № 4. С. 3-13. DOI: 10.12737/1958. Tsar´kov I.N. Issledovanie effektivnosti metodov optimizatsii proekta s ogranichennymi resursami. Chast´ 2 [Evaluation of Methods for Optimizing a Resource-Constrained Project. Part 2]. Nauchnye issledovaniya i razrabotki. Rossiyskiy Zhurnal Upravleniya Proektami [Research and Development. Russian Journal of Project Management]. 2013, V. 2, I. 4, pp. 3-13. DOI: 10.12737/1958. 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. Sowiski, J. Wglarz. Oxford: Elsevier, 1989. P. 113-134. 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. Oxford: Elsevier, 1989, pp. 113-134. Blazewicz J. Scheduling Subject to Resource Constraints: Classification and Complexity. Brussels: European Institute for Advanced Studies in Management, 1980. Blazewicz J. Scheduling Subject to Resource Constraints: Classification and Complexity. Brussels: European Institute for Advanced Studies in Management, 1980. Cooper D.F. Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation // Manag. Sci. 1976. Т. 22. № 11. P. 1186-1194. Cooper D.F. Heuristics for Scheduling Resource-Constrained Projects: An Experimental Investigation // Manag. Sci. 1976. V. 22. I. 11. pp. 1186-1194. 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. Davis E.W., Patterson J.H. A comparison of heuristic and optimum solutions in resource-constrained project scheduling // Manag. Sci. 1975. V. 21. I. 8. pp. 944-955. 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. Drexl A. idr. ProGen/πx - An instance generator for resourceconstrained project scheduling problems with partially renewable resources and further extensions // Eur. J. Oper. Res. 2000. V. 125. I. 1. pp. 59-72. Drexl A. Scheduling of Project Networks by Job Assignment // Manag. Sci. 1991. Т. 37. № 12. С. 1590-1602. Drexl A. Scheduling of Project Networks by Job Assignment // Manag. Sci. 1991. V. 37. I. 12. pp. 1590-1602. 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. 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. pp. 160-173. 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. King G.W. The Monte Carlo Method as a Natural Mode of Expression in Operations Research // J. Oper. Res. Soc. Am. 1953. V. 1. I 2. pp. 46-51. Kolisch R., Drexl A. Adaptive search for solving hard project scheduling problems // Nav. Res. Logist. NRL. 1996. Т. 43. № 1. P. 23-40. Kolisch R., Drexl A. Adaptive search for solving hard project scheduling problems // Nav. Res. Logist. NRL. 1996. V. 43. I. 1. pp. 23-40. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem // J. Oper. Manag. 1996a. Т. 14. № 3. P. 179-192. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem // J. Oper. Manag. 1996a. V. 14. I. 3. pp. 179-192. Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation // Eur. J. Oper. Res. 1996b. Т. 90. № 2. P. 320-333. Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation // Eur. J. Oper. Res. 1996b. V. 90. I. 2. pp. 320-333. 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. Kolisch R., Sprecher A., Drexl A. Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems. Instituten fur Betriebswirtschaftslehre der Universitat Kiel, 1992. 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. Kolisch R., Sprecher A. PSPLIB - A project scheduling problem library: OR Software - ORSEP Operations Research Software Exchange Program // Eur. J. Oper. Res. 1996. V. 96. I. 1. pp. 205-216. Pritsker A.A.B., Watters L.J. A zero-one programming approach to scheduling with limited resources. Santa Monica, Calif.: Rand Corp., 1968. Pritsker A.A.B., Watters L.J. A zero-one programming approach to scheduling with limited resources. Santa Monica, Calif.: Rand Corp., 1968. 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. Schirmer A. Case-Based Reasoning and Improved Adaptive Search for Project Scheduling. University of Kiel, Germany, 1998. I. Manuskripte aus den Instituten fur Betriebswirtschaftslehre der Universitat Kiel. 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. Schirmer A. Resource-constrained project scheduling: An evaluation of adaptive control schemes for parameterized sampling heuristics // Int. J. Prod. Res. 2001. V. 39. I. 7, pp. 1343-1365. 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. Schirmer A., Riesenberg S. Parameterized Heuristics for Project Scheduling - Biased Random Sampling Methods. University of Kiel, Germany, 1997. Vyp. Manuskripte aus den Instituten fur Betriebswirtschaftslehre der Universitat Kiel. Tormos P., Lova A. An efficient multi-pass heuristic for project scheduling with constrained resources // Int. J. Prod. Res. 2003. Т. 41. № 5. С. 1071-1086. Tormos P., Lova A. An efficient multi-pass heuristic for project scheduling with constrained resources // Int. J. Prod. Res. 2003. V. 41. I. 5. pp. 1071-1086.