Москва, г. Москва и Московская область, Россия
В работе исследуется эффективность различных однопроходных правил приоритета, используемых в конструктивных эвристических методах сокращения продолжительности проекта в условиях ограниченных возобновляемых ресурсов. Особое внимание уделено так называемым гибридным алгоритмам и зависимости эффективности правил приоритета от параметров сети. Эффективность правил исследуется на множествах из 480 проектов PSPLIB: J30, J60, J90.
эвристические методы, расписание проекта, ограниченные ресурсы, сокращение продолжительности, конструктивные методы, гибридные методы, WCS, IRSM, SLK, PSPLIB.
1. Введение
По словам профессора школы менеджмента технического университета Мюнхена (TUM) Р. Колиша, ядром системы планирования проекта является механизм нахождения такого расписания, которое позволит выполнить проект в кратчайшие сроки в условиях ограниченных возобновляемых ресурсов. Действительно, в большинстве проектов не хватает или недостаточно много людей и машин, которым предстоит выполнять работы проекта, и неэффективное распределение этих ресурсов может существенно (на 20-30% и более) увеличить продолжительность такого проекта (см. приложения А, В, С). При этом классический метод критического пути ), являющийся на сегодня основным методом (CPM1 формирования расписаний проектов, не работает в условиях ограниченных ресурсов и поэтому не может обеспечить решение такой задачи.
В первой части статьи [1] были рассмотрены методы, позволяющие найти расписания с минимально возможной продолжительностью при ограниченных ресурсах, основным недостатком которых является практическая невозможность применения даже для небольших проектов (порядка 200 работ). В этой работе будут рассмотрены методы, которыекоторые, скорее всего, не позволят получить оптимальное расписание, но которые могут быть реализованы в современных системах автоматизации и применяться на практике. Такие методы принято называть эвристическими.
Эвристические методы обычно делят на три класса: конструктивные, улучшающие и метаэвристические. К конструктивным относят те методы, которые позволяютщие «с нуля» построить расписание, в котором все ресурсные конфликты будут разрешены. Такие расписания мы будем называть допустимыми. Улучшающие методы нацелены на изменения уже существующего допустимого расписания, которые позволят сократить продолжительность проекта. Метаэвристические методы позволяют выстроить процесс, который позволит последовательно улучшать расписание, объединяя в себе и конструктивные, и улучшающие методы.
Основная задача конструктивных эвристических методов состоит в определении величинывеличины, на которую нужно задержать выполнение каждой работы проекта, чтобы разрешить все ресурсные конфликты (получить допустимое расписание).
_________
1 От англ. Critical Path Method.
1. Царьков И.Н. Исследование эффективности методов оптимизации проекта с ограниченными ресурсами. Ч. 1 // Научные исследования и разработки: Российский журнал управления проектами. 2013. № 3.
2. Alvarez-Valdes R., Tamarit J.M. Heuristic algorithms for resource-constrained project scheduling: A review and an empirical analysis. In: R. Slowinski and J. Weglarz (Eds.). Advances in Project Scheduling. Elsevier. Amsterdam, 1989. P. 113-134.
3. Boctor F.F. Some Efficient Multi-Heuristic Procedures for Resource-Constrained Project Scheduling // European Journal of Operational Research. 1990,. № 49, . Р. 3-13.
4. Brand J.D., Meyer W.L., Shaffer L.R. The Resource Scheduling Method in Construction [Report]. University of Illinois: Civil Engineering Studies Report. 1964. № 5. 1964.
5. Davis E.W. Project Scheduling under Resource ConstraintsHistorical Review and Categorization of Procedures // IIE Transactions. 1973. 5:4. Р. 297-313.
6. Davis E.W., Patterson J.H. A Comparison of Heuristic and Optimum Solutions in Resource-Constrained Project Scheduling, // Management Science. 1975. № 21. Р. 944-955.
7. Herroelen W.S. Resource-constrained Project Scheduling - State of the Art // Operational Research Quarterly. Vol. 23. 1972. № 3. Sept. Р. 261-275.
8. Kelley J.E. The critical path method: resource planning and scheduling. Chapter 21 of Industrial Scheduling (J.F. Muth and G.L. Thompson, eds.). Prentice-Hall. Englewood Cliffs, 1963.
9. Klein R. Scheduling of Resource-Constrained Projects. Kluwer Academic Publisher, 2000.
10. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem // Journal of Operations Management. 1996b. № 14. Р. 179-192.
11. Kolisch R. Serial and Parallel Resource-Constrained Project Scheduling Methods Revisited: Theory and computation // European Journal of Operational Research. 1996a. № 90. Р. 320-333.
12. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems // Management Science. 1995. № 41. Р. 1693-1703.
13. Kolisch R., Sprecher A. PSPLIB - A Project Scheduling Library // European Journal of Operational Research. 1996c. Vol. 96. Р. 205-216.
14. 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.
15. Ulusoy G., Ozdamar L. Heuristic Performance and Network / Resource Characteristics in Resource-Constrained Project Scheduling // Journal of the Operational Research Society. 1989. № 40. Р. 1145-1152.
16. Whitehouse G.E., Brown J.R. GENRES: An extension of Brooks Algorithm for project scheduling with resource onstraints // Computers&Industrial Engineering. 1979. Vol. 3. Issue 3. Р. 261-268.
17. PSPLIB. URL: http://129.187.106.231/psplib/library.html/
