Moskva, Moscow, Russian Federation
Shortening project expected makespan in the case of resource constraints is the most popular problem in project scheduling. But in practice activity durations is not determined. So the problem is to find a policy which could define which activity should be started at decision points to minimize expected project makespan. This problem usually called SRCPSP. In this paper we define key research tasks of such a problem and propose extended activity-based policy XABP. Computational results show us the high efficiency of this policy.
project scheduling, scheduling policy, ABP, resource constraints, stochastic activity durations, SRCPSP.
1. Формирование расписания проекта в условиях неопределенной продолжительности его работ
Одной из самых популярных тем в математических моделях управления проектами является проблема нахождения эффективных расписаний в условиях ограниченных возобновляемых ресурсов, имеющая акроним RCPSP. Такой интерес обусловлен, с одной стороны, практической востребованностью решения такой задачи, с другой стороны,бесперспективностью нахождения оптимального решения в общем случае для реальных проектов, состоящих из сотен и тысяч работ. Однако в модели проекта RCPSP предполагается, что продолжительность всех его работ заранее известна и не может быть увеличена или уменьшена в процессе его выполнения. Ясно, что это условие слишком жесткое, редко выполняемое на практике. Поэтому следующим этапом развития можно считать аналогичную проблему, в которой продолжительности работ считаются случайными величинами. В литературе такая задача получила обозначение SRCPSP (Stochastic RCPSP), основной целевой функцией оптимизации которой является ожидаемая продолжительность проекта. Можно считать, что если RCPSP основана на модели проекта, используемой в методе критического пути CPM/PDM, то SRCPSP основана на модели PERT.
1. Godratt E. Kriticheskaya tsep' [The Critical Chain]. Moscow, TOS Tsentr Publ., 2006.
2. Tsar'kov I.N. Issledovanie effektivnosti metodov optimizatsii proekta s ogranichennymi resursami [Investigation of the effectiveness of project optimization methods with limited resources]. Rossiyskiy zhurnal upravleniya proektami [Russian Journal of Project Management]. 2013, V. 4, I. 5, pp. 3–13.
3. Ballestín F. When it is worthwhile to work with the stochastic RCPSP? // Journal of Scheduling. 2007. Vol. 10. I. 3. P. 153–166.
4. Demeulemeester E. Herroelen W. Project Scheduling. A Research handbook. KLUWER, 2002.
5. Golenko-Ginzburg D., Gonik A. Stochastic network project scheduling with non-consumable limited resources // International Journal of Production Economics. 1997. Vol. 48. No 1. pp. 29–37.
6. Golenko-Ginzburg D., Gonik A. A heuristic for network project scheduling with random activity durations depending on the resource allocation // International Journal of Production Economics. 1998. Vol. 55. No 2. pp. 149–162.
7. Graham R.L. Bounds on Multiprocessing Timing Anomalies // Bell System Technical Journal. 1966. 45, 1563–1581.
8. Herroelen W., Leus R. Project scheduling under uncertainty: Survey and research potentials.// European Journal of Operational Research. 2005. Vol. 165. No 2. Pp. 289–306.
9. Kolisch R. Efficient priority rules for the resource-constrained project scheduling problem. // Journal of Operations Management 14 (1996). Pp. 179–192.
10. Kolisch R., Schwindt C. und Sprecher A. (1999): Benchmark instances for project scheduling problems; Kluwer; Weglarz J. (Hrsg.): Handbook on recent advances in project scheduling, pp. 197–212.
11. Leus R., Rostami S., Creemers S. New benchmark results for the stochastic resource-constrained project scheduling problem // Singapore, 2015, pp. 204–208.
12. Möhring R.H., Radermacher F.J. and Weiss G. 1984, Stochastic Scheduling Problems I — General Strategies, ZOR — Zeitschrift für Operations Research, 28, pp. 193–260.
13. Möhring R.H., Radermacher F.J. and Weiss G. 1985, Stochastic Scheduling Problems II — Set Strategies, ZOR — Zeitschrift für Operations Research, 29, 65–104.
14. Möhring R.H. and Stork F. 2000, Linear Preselective Policies for Stochastic Project Scheduling // Mathematical Methods of Operations Research, 52, 501–515.
15. Van De Vonder S. et al. The trade-off between stability and makespan in resource-constrained project scheduling // International Journal of Production Research. 2006. Vol. 44. I. 2. Pp. 215–236.
16. Van de Vonder S., Demeulemeester E., Herroelen W. Proactive heuristic procedures for robust project scheduling: An experimental analysis // European Journal of Operational Research. 2008. Vol. 189. I. 3. Pp. 723–733.
