Москва, г. Москва и Московская область, Россия
Проблема оптимизации проекта с ограниченными возобновляемыми ресурсами является одной из самых важных в теории управления расписанием, так как позволяет существенно сократить продолжительность выполнения проекта и повысить эффективность использования его ресурсов. В советское время были разработаны и использовались на практике ряд методов решения этой проблемы. К сожалению, до сих пор не было исследовано, насколько эффективно эти методы работают в сравнении с методами, развиваемыми в других странах. В этой работе приведены результаты исследования эффективности этих методов, полученные при компьютерном моделировании на основе международно признанной методики и с использованием базы данных проектов PSPLIB.
расписание проекта, ограниченные ресурсы, оптимизация расписания множества проектов, советские методы оптимизации ресурсов.
Введение
Метод критического пути (МКП) произвел революцию в подходах к управлению проектами, позволив выявлять работы, своевременное выполнение которых напрямую влияет на выполнение всего проекта в установленные сроки. Однако этот метод обладает существенным недостатком — им можно пользоваться, только если в проекте нет конфликтов возобновляемых1 ресурсов. Но такое на практике встречается достаточно редко: практически в каждой отрасли есть специалисты, машины или оборудование, которые загружены почти на 100% и спрос на которых которые значительно превышает предложение. В результате, если есть, например, 5 буровых установок, а нужно пробурить 30 скважин, то время выполнения этих работ будет минимум в 6 раз (!) выше по сравнению с ситуацией параллельного выполнения всех работ. Именно поэтому ограничения на ресурсы входят в так называемый «железный треугольник» управления проектом наряду со сроками выполнения.
Однако не в каждой ситуации можно быстро рассчитать новое расписание проекта и определить его новую продолжительность, если необходимо разрешить ресурсный конфликт. Рассмотрим пример. На рис. 1 представлена сетевая диаграмма «вершина — работа» проекта, каждая работа которого изображена прямоугольником, содержащим название работы (лат. буква), продолжительность (указана в скобках) и количество ресурса, необходимое для выполнения (после запятой). Например, работа А выполняется первой, длится два дня и требует 1 ед. ресурса.
Конфликт ресурсов возникает между выполнением работ B и C, когда проекту доступно одновременное использование не более 2 единиц ресурсов. Другими словами, эти работы не могут выполняться одновременно. Разрешить такой конфликт мы можем двумя способами: 1) после завершения работы A начать выполнение работы B, а работу C начать выполнять одновременно с работой D; 2) после завершения работы A выполнять работу C и на два дня задержать выполнение работы B. Оба решения приведут к допустимому расписанию (лишенному ресурсных конфликтов), но с разной продолжительностью проекта: в первом случае — это 9 дней, во втором — 11 дней (более чем на 20% больше).
________________
1 Обычно возобновляемые ресурсы отличают от невозобновляемых тем, что последние ограничены для всего проекта в целом, а возобновляемые — в каждом периоде его выполнения.
1. Гельруд Я.Д. Модели и методы управления проектами в условиях риска и неопределенности: Монография. Челябинск: Изд-во ЮУрГУ, 2006.
2. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. М.: Наука, 1965.
3. Коренблюм Б.И., Рыбальский В.И., Хацей Б.И. Об одной экстремальной задаче, связанной с сетевым графиком проекта // Тезисы новосибирской конференции, 1965.
4. Келли Дж. Календарное планирование: Сб. Экономические модели в управлении производством. М., 1967.
5. Многоуровневая модель управления проектами со стохастическими параметрами / С.М. Любкин [и др.]. М.: ВИНИТИ. 1999. № 6. С. 34--38.
6. Математические основы управления проектами: Учеб. пособие / С.А. Баркалов [и др.] // Под ред. В.Н. Буркова. М.: Высшая школа, 2005.
7. Садовский В.И. Алгоритм оперативного планирования с использованием многоцелевых сетевых графиков в условиях ограниченных ресурсов («калибровка») // Вычислительная и организационная техника в строительстве. Вып. 5. Гипротис, 1965.
8. Скрыдлов Н.В. Автоматизированные системы оперативного управления в строительстве. М.: Стройиздат, 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/
