Moskva, Moscow, Russian Federation
Developing this subject, the author evaluates efficiency of various straight-through priority rules, used in constructive heuristic methods meant for reducing completion periods of projects with constrained renewable resources. Special attention is given to the so-called hybrid algorithms and dependence between efficiency of priority rules and network capacity. Efficiency of rules is analyzed based on sets of 480 PSPLIB projects: J30, J60, J90.
heuristic methods, project schedule, constrained resources, to reduce completion period, constructive methods, hybrid methods, WCS, IRSM, SLK, PSPLIB.
1. Введение
По словам профессора школы менеджмента технического университета Мюнхена (TUM) Р. Колиша, ядром системы планирования проекта является механизм нахождения такого расписания, которое позволит выполнить проект в кратчайшие сроки в условиях ограниченных возобновляемых ресурсов. Действительно, в большинстве проектов не хватает или недостаточно много людей и машин, которым предстоит выполнять работы проекта, и неэффективное распределение этих ресурсов может существенно (на 20-30% и более) увеличить продолжительность такого проекта (см. приложения А, В, С). При этом классический метод критического пути ), являющийся на сегодня основным методом (CPM1 формирования расписаний проектов, не работает в условиях ограниченных ресурсов и поэтому не может обеспечить решение такой задачи.
В первой части статьи [1] были рассмотрены методы, позволяющие найти расписания с минимально возможной продолжительностью при ограниченных ресурсах, основным недостатком которых является практическая невозможность применения даже для небольших проектов (порядка 200 работ). В этой работе будут рассмотрены методы, которыекоторые, скорее всего, не позволят получить оптимальное расписание, но которые могут быть реализованы в современных системах автоматизации и применяться на практике. Такие методы принято называть эвристическими.
Эвристические методы обычно делят на три класса: конструктивные, улучшающие и метаэвристические. К конструктивным относят те методы, которые позволяютщие «с нуля» построить расписание, в котором все ресурсные конфликты будут разрешены. Такие расписания мы будем называть допустимыми. Улучшающие методы нацелены на изменения уже существующего допустимого расписания, которые позволят сократить продолжительность проекта. Метаэвристические методы позволяют выстроить процесс, который позволит последовательно улучшать расписание, объединяя в себе и конструктивные, и улучшающие методы.
Основная задача конструктивных эвристических методов состоит в определении величинывеличины, на которую нужно задержать выполнение каждой работы проекта, чтобы разрешить все ресурсные конфликты (получить допустимое расписание).
_________
1 От англ. Critical Path Method.
1. Tsar´kov I.N. Issledovanie effektivnosti metodov optimizatsii proekta s ogranichennymi resursami. Ch. 1. Nauchnye issledovaniya i razrabotki: Rossiyskiy zhurnal upravleniya proektami. 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, . R. 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. R. 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. R. 944-955.
7. Herroelen W.S. Resource-constrained Project Scheduling - State of the Art. Operational Research Quarterly. Vol. 23. 1972. № 3. Sept. R. 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. R. 179-192.
11. Kolisch R. Serial and Parallel Resource-Constrained Project Scheduling Methods Revisited: Theory and computation. European Journal of Operational Research. 1996a. № 90. R. 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. R. 1693-1703.
13. Kolisch R., Sprecher A. PSPLIB - A Project Scheduling Library. European Journal of Operational Research. 1996c. Vol. 96. R. 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. R. 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. R. 261-268.
17. PSPLIB. URL: http://129.187.106.231/psplib/library.html/
