Modeling and Solving the Stochastic Multi-mode Resource Leveling Problem

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

Abstract

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

CLC Number:

N945

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.

References

[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.