随机多模式资源均衡问题建模与求解

Modeling and Solving the Stochastic Multi-mode Resource Leveling Problem

在项目调度实践中,活动采用多种执行模式以及活动工期不确定具有一定的普遍性,对于昂贵和稀缺的可更新资源的均衡使用也是项目追求的目标之一。针对具有NP-Hard特性的多模式工期不确定性问题,以可更新资源均衡为目标建立马尔可夫决策过程模型,设计基于Rollout的近似动态规划算法对问题进行求解,针对问题特点采用改进的遗传算法作为基准策略,并在决策阶段引入虚拟资源上界对活动进行评估。以一个小规模算例说明算法的运行过程,通过全因子实验设计,测试相关参数对项目资源均衡程度的影响。研究结果表明,设计的算法能有效解决随机多模式资源均衡问题;网络复杂度的降低、可更新资源量的增加、活动工期分布的对称性以及较低的离散程度,能够改善项目资源利用的均衡程度。

Multi-mode execution as well as uncertain task durations is common in project scheduling area. Reducing the fluctuations in the pattern of expensive renewable resource usage over time is an important goal project pursues. For the stochastic multi-mode resource leveling problem, the Markov decision process model is set up under the objective of minimizing the variation in the renewable resource utilization. An approximate dynamic programming algorithm based on the rollout policy is developed. Meanwhile, a revised genetic algorithm is employed as the base policy to enhance performance of the rollout algorithm. And the virtual upper bound of resource is proposed in the decision stage to assess candidate activities. The model and algorithm are demonstrated using an example project. The effect of related parameters on resource leveling is tested through full factorial design. Computational results show that the algorithm solves the stochastic multi-mode resource leveling problem effectively and the resource usage benefits from a simple network structure, ample resources, small variation coefficient and symmetric distribution of activity duration.