Moskva, Moscow, Russian Federation
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. 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:https://doi.org/10.12737/1240
2. 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: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. Oxford: Elsevier, 1989, pp. 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. V. 22. I. 11. pp. 1186-1194.
6. 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.
7. 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.
8. Drexl A. Scheduling of Project Networks by Job Assignment // Manag. Sci. 1991. V. 37. I. 12. pp. 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. pp. 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. V. 1. I 2. pp. 46-51.
11. Kolisch R., Drexl A. Adaptive search for solving hard project scheduling problems // Nav. Res. Logist. NRL. 1996. V. 43. I. 1. pp. 23-40.
12. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem // J. Oper. Manag. 1996a. V. 14. I. 3. pp. 179-192.
13. 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.
14. 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.
15. 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.
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. I. Manuskripte aus den Instituten fur 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. V. 39. I. 7, pp. 1343-1365.
19. 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.
20. 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.
