Moskva, Moscow, Russian Federation
Optimizing projects with constrained renewable resources is one of the most important issues in the theory of project schedule management, as such optimization allows to substantially reduce project completion period and to enhance project resource efficiency. Certain methods for solving this problem had been developed and practiced in the Soviet times, but regrettably their effectiveness still have not been compared to that of methods developed in the other countries. The author’s findings concerning the effectiveness of those Soviet-time optimization methods are presented in this paper. The results are obtained through internationally-recognized computer simulation technique and with the use of The Project Scheduling Problem Library (PSPLIB) databases.
project schedule, constrained resources, multi-project schedule optimization, Soviet-time resource optimization methods.
Введение
Метод критического пути (МКП) произвел революцию в подходах к управлению проектами, позволив выявлять работы, своевременное выполнение которых напрямую влияет на выполнение всего проекта в установленные сроки. Однако этот метод обладает существенным недостатком — им можно пользоваться, только если в проекте нет конфликтов возобновляемых1 ресурсов. Но такое на практике встречается достаточно редко: практически в каждой отрасли есть специалисты, машины или оборудование, которые загружены почти на 100% и спрос на которых которые значительно превышает предложение. В результате, если есть, например, 5 буровых установок, а нужно пробурить 30 скважин, то время выполнения этих работ будет минимум в 6 раз (!) выше по сравнению с ситуацией параллельного выполнения всех работ. Именно поэтому ограничения на ресурсы входят в так называемый «железный треугольник» управления проектом наряду со сроками выполнения.
Однако не в каждой ситуации можно быстро рассчитать новое расписание проекта и определить его новую продолжительность, если необходимо разрешить ресурсный конфликт. Рассмотрим пример. На рис. 1 представлена сетевая диаграмма «вершина — работа» проекта, каждая работа которого изображена прямоугольником, содержащим название работы (лат. буква), продолжительность (указана в скобках) и количество ресурса, необходимое для выполнения (после запятой). Например, работа А выполняется первой, длится два дня и требует 1 ед. ресурса.
Конфликт ресурсов возникает между выполнением работ B и C, когда проекту доступно одновременное использование не более 2 единиц ресурсов. Другими словами, эти работы не могут выполняться одновременно. Разрешить такой конфликт мы можем двумя способами: 1) после завершения работы A начать выполнение работы B, а работу C начать выполнять одновременно с работой D; 2) после завершения работы A выполнять работу C и на два дня задержать выполнение работы B. Оба решения приведут к допустимому расписанию (лишенному ресурсных конфликтов), но с разной продолжительностью проекта: в первом случае — это 9 дней, во втором — 11 дней (более чем на 20% больше).
________________
1 Обычно возобновляемые ресурсы отличают от невозобновляемых тем, что последние ограничены для всего проекта в целом, а возобновляемые — в каждом периоде его выполнения.
1. Gelrud Ya.D. Modeli i metody upravleniya proektami v usloviyakh riska i neopredelennosti: Monografiya. Chelyabinsk: Izd-vo YuUrGU, 2006.
2. Zukhovitskiy S.I., Radchik I.A. Matematicheskie metody setevogo planirovaniya. M.: Nauka, 1965.
3. Korenblyum B.I., Rybalskiy V.I., Khatsey B.I. Ob odnoy ekstremal´noy zadache, svyazannoy s setevym grafikom proekta. Tezisy novosibirskoy konferentsii, 1965.
4. Kelli J. Kalendarnoe planirovanie: Sb. Ekonomicheskie modeli v upravlenii proizvodstvom. M., 1967.
5. Mnogourovnevaya model' upravleniya proektami so stokhasticheskimi parametrami / S.M. Lyubkin [i dr.]. M.: VINITI. 1999. № 6. S. 34-–38.
6. Matematicheskie osnovy upravleniya proektami: Ucheb. posobie / S.A. Barkalov [i dr.]. Pod red. V.N. Burkova. M.: Vysshaya shkola, 2005.
7. Sadovskiy V.I. Algoritm operativnogo planirovaniya s ispol'zovaniem mnogotselevykh setevykh grafikov v usloviyakh ogranichennykh resursov («kalibrovka»). Vychislitel'naya i organizatsionnaya tekhnika v stroitel'stve. Vyp. 5. Giprotis, 1965.
8. Skrydlov N.V. Avtomatizirovannye sistemy operativnogo upravleniya v stroitel'stve. M.: Stroyizdat, 1974.
9. Alvarez-Valdés R., Tamarit J.M. The Project Scheduling Polyhedron: Dimension, Facts and Lifting Theorems. European Journal of Operational Research. 1993. № 67. P. 204–220.
10. Blazewicz J., Lenstra J., Rinnooy K.A. Scheduling subject to resource constraints: Classification and complexity. Discrete Applied Mathematics. 1983. № 5 (1983). P. 11–24.
11. Boctor F.F. Some efficient multi-heuristic procedures for resource-constrained project scheduling. European Journal of Operational Research. 1990. № 49. P. 3–13.
12. Hartmann S., Kolisch R. Experimental evaluation of stateof-the-art heuristics for resource constrained project scheduling. European Journal for Operational Research. 2000. Vol. 127. № 2. P. 394–407.
13. Kaplan L.A. Resource-Constrained Project Scheduling with Preemption of Jobs. Unpublished Ph.D. Thesis, University of Michigan. 1988.
14. Kolisch R., Sprecher A., Drexl A. Characterization and Generation of a General Class of Resource-Constrained Project Scheduling Problems. Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität. Kiel. 1992. № 301.
15. Kolisch R., Sprecher A. PSPLIB — A project scheduling library. European Journal of Operational Research. 1996. Vol. 96. P. 205–216.
16. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems. Management Science. 1995. № 41. P. 1693–1703.
17. Lawrence S. Resource constrained project scheduling: A computational comparison of heuristic scheduling techniques. Technical report. Graduate School of industrial administration. Pittsburg: Carnegie-Mellon University, 1985.
18. Pritsker A.A.B., Watters L.J. A Zero-One Programming Approach to Scheduling with Limited Resources. The RAND Corporation, RM-5561-PR. 1968.
19. PSPLIB. URL: http://129.187.106.231/psplib/library.html/
