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

doi:10.3969/j.issn.1007-7375.e16-1178

工业工程 ›› 2017, Vol. 20 ›› Issue (3): 95-105.doi: 10.3969/j.issn.1007-7375.e16-1178

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

初梓豪¹, 徐哲¹, 李明², 顾坤¹

1. 北京航空航天大学经济管理学院, 北京 100191;
2. 石家庄铁道大学经济管理学院, 河北石家庄 050043

收稿日期:2016-06-21 出版日期:2017-06-30 发布日期:2017-07-12
作者简介:初梓豪(1989-),男,山东省人,博士研究生,研究方向为项目调度
基金资助:
国家自然科学基金资助项目（71571005，71271019）

Modeling and Solving the Stochastic Multi-mode Resource Leveling Problem

CHU Zihao¹, XU Zhe¹, LI Ming², GU Kun¹

1. School of Economics and Management, Beihang University, Beijing 100191, China;
2. School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China

Received:2016-06-21 Online:2017-06-30 Published:2017-07-12

摘要/Abstract

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

关键词: 随机调度, 资源受限, 多模式, 工期不确定, 资源均衡, 近似动态规划

Abstract: 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.

Key words: stochastic scheduling, resource-constrained, multi-mode, uncertain task durations, resource leveling, approximate dynamic programming

中图分类号:

N945

初梓豪, 徐哲, 李明, 顾坤. 随机多模式资源均衡问题建模与求解[J]. 工业工程, 2017, 20(3): 95-105.

CHU Zihao, XU Zhe, LI Ming, GU Kun. Modeling and Solving the Stochastic Multi-mode Resource Leveling Problem[J]. Industrial Engineering Journal , 2017, 20(3): 95-105.

参考文献

[1] 寿涌毅. 资源受限多项目调度的模型与方法[M]. 杭州:浙江大学出版社, 2010.
[2] MOHRING R H, RADERMACHER F J, WEISS G. Stochastic scheduling problems I-General strategies[J]. Zeitschrift für Operations Research, 1984, 28(7):193-260.
[3] MOHRING R H, RADERMACHER F J, WEISS G. Stochastic scheduling problems Ⅱ-Set strategies[J]. Zeitschrift für Operations Research, 1985, 29(3):65-104.
[4] DEMEULEMEESTER E, HERROELEN W. Project scheduling:A research handbook[M], Kluwer Academic Publishers, 2002.
[5] STORK F. Stochastic resource-constrained project scheduling[D]. Ph. D. thesis, Technische Universität Berlin, 2001.
[6] BALLESTIN F, LEUS R. Resource-constrained project scheduling for timely project completion with stochastic activity durations[J]. Production and Operations Management, 2009, 18(4):459-474.
[7] ASHTIANI B, LEUS R, ARYANEZHAD M B. New competitive results for the stochastic resource-constrained project scheduling problem:exploring the benefits of pre-processing[J]. Journal of Scheduling, 2001, 14(2):157-171.
[8] LI Haitao, WOMER N K. Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming[J]. European Journal of Operational Research, 2015, 246(1):20-33.
[9] GUTJAHR W J, STRAUSS C, WAGNER E. A stochastic branch-and-bound approach to activity crashing in project management[J]. ORSA Journal on Computing, 2000, 12(2):125-135.
[10] ELMAGHRABY S E, MORGAN C D. Resource allocation in activity networks under stochastic conditions:A geometric programming-sample path optimization approach[J]. Review of Business and Economics Management, 2007, LⅡ(3):367-390.
[11] GODINHO P, BRANCO F G. Discrete optimization:adaptive policies for multi-mode project scheduling under uncertainty[J]. European Journal of Operational Research, 2012, 216(3):553-563.
[12] 李佳媛, 何正文. 基于资源随机中断的反应性多模式项目调度优化[J]. 运筹与管理, 2015, 24(6):44-50.LI Jiayuan, HE Zhengwen. Optimization of reactive multi-mode project scheduling based on stochastic breakdown of resources[J]. Operations Research and Management Science, 2015, 24(6):44-50.
[13] 廖婷婷, 徐哲, 李明. 软件开发项目多技能人力资源均衡调度模型[J]. 工业工程, 2015, 18(3):69-74.LIAO Tingting, XU Zhe, LI Ming. A research on multi-skill human resource leveling scheduling model of software development project[J]. Industrial Engineering Journal, 2015, 18(3):69-74.
[14] RIECK J, ZIMMERMANN J, GATHER T. Mixed-integer linear programming for resource leveling problems[J]. European Journal of Operational Research, 2012, 221(1):27-37.
[15] 李明, 徐哲. 基于均衡优化的项目多技能人力资源指派与调度方法[J]. 工业工程, 2016, 19(1):108-114.LI Ming, XU Zhe. Methods of assigning multi-skilled human resources and scheduling projects based on resource leveling[J]. Industrial Engineering Journal, 2016, 19(1):108-114.
[16] NEUMANN K, ZIMMERMANN J. Resource levelling for projects with schedule-dependent time windows[J]. European Journal of Operational Research, 1999, 117(3):591-605.
[17] NEUMANN K, SCHWINDT C, ZIMMERMANN J. Project scheduling with time windows and scarce resources:temporal and resource-constrained project scheduling with regular and nonregular objective functions[M]. Springer, 2003.
[18] BERTSEKAS D P, CASTANON D A. Rollout algorithms for stochastic scheduling problems[J]. Journal of Heuristics, 1999, 5(1):89-108.
[19] HARTMANN S. Project scheduling with multiple modes:a genetic algorithm[J]. Annals of Operations Research. 2001, 102(1-4):111-135.
[20] GOLDBERG D E, KORB B, DEB K. Messy genetic algorithms:motivation, analysis, and first results[J]. Complex Systems. 1989, 3(5):493-530.
[21] BADIRU A B. A simulation approach to PERT network analysis[J]. Simulation. 1991, 57(4):245-255.
[22] KOLISCH R, SPRECHER A. PSPLIB-A project scheduling problem library[J]. European Journal of Operational Research. 1997, 96(1):205-216.

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

Modeling and Solving the Stochastic Multi-mode Resource Leveling Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 8

编辑推荐

Metrics

本文评价

[1]	傅惠, 王叶飞, 陈赛飞. 面向宏观基本图的多模式交通路网分区算法[J]. 工业工程, 2020, 23(1): 1-9.
[2]	何立华，马芳丽. 基于混沌差分进化粒子群算法的模糊资源受限项目调度问题[J]. 工业工程, 2016, 19(5): 39-44.
[3]	何利娟1, 李欣2. 基于蚁群算法的资源均衡优化决策及其MATLAB实现[J]. 工业工程, 2015, 18(6): 125-129.
[4]	廖婷婷，徐哲，李明. 软件开发项目多技能人力资源均衡调度模型[J]. 工业工程, 2015, 18(3): 69-74.
[5]	张连营1, 李彦伟1,2, 孙若昕1. 基于优先规则的模糊资源受限多项目调度[J]. 工业工程, 2014, 17(3): 13-17.
[6]	郭云涛，宋红艳，白思俊. 粒子群算法在具有迭代关系资源受限项目调度中的应用[J]. 工业工程, 2013, 16(5): 74-78.
[7]	熊桂武1,2. 具有模糊时间窗的多模式联运建模及优化[J]. 工业工程, 2012, 15(4): 7-11.
[8]	谢阳，叶春明，陈君兰，周蓉. 基于混沌粒子群的资源受限项目调度问题[J]. 工业工程, 2012, 15(3): 57-61.