基于改进关键链方法的MRCPSP的鲁棒性优化
|
摘要
针对鲁棒性项目调度理论研究集中在单模式领域这一现状,通过对关键链方法的改进,构建了多模式资源受限项目调度鲁棒性优化模型.其中,对关键链方法的两个核心问题进行了改进:提出了非关键链识别的准则,采用不同的影响系数对缓冲区间的设置进行了修正.同时,在综合考虑了关键链方法特点,任务的多种模式以及资源消耗稳定性需求基础上设计了鲁棒性指标,并构建了基于鲁棒性目标的关键链多模式资源受限项目调度模型.通过多组算例验证显示调度计划的鲁棒性显著提高,证明了模型的有效性.
Different from the current theoretical research of robust project schedule which focuses on the single-mode filed, this paper uses an improved critical chain method to construct a robust optimization model of the multi-mode resource-constrained project scheduling problem(MRCPSP). Two core problems of the critical chain method are improved. A criteria for non-critical chain recognition is proposed, and the buffer settings are corrected by using different influence coefficients. Meanwhile, this paper designs a robust measure based on the comprehensive consideration of the characteristics of the critical chain method, the task's multimodes and resource consumption stability. A critical chain multi-mode resource-constrained project scheduling model based on the robust objective is constructed then. The robustness of the scheduling plan is improved significantly in multiple test cases, which proves the validity of the model.
Different from the current theoretical research of robust project schedule which focuses on the single-mode filed, this paper uses an improved critical chain method to construct a robust optimization model of the multi-mode resource-constrained project scheduling problem(MRCPSP). Two core problems of the critical chain method are improved. A criteria for non-critical chain recognition is proposed, and the buffer settings are corrected by using different influence coefficients. Meanwhile, this paper designs a robust measure based on the comprehensive consideration of the characteristics of the critical chain method, the task's multimodes and resource consumption stability. A critical chain multi-mode resource-constrained project scheduling model based on the robust objective is constructed then. The robustness of the scheduling plan is improved significantly in multiple test cases, which proves the validity of the model.
引文
[1]张静文,乔传卓,刘耕涛.基于鲁棒性的关键链二次资源冲突消除策略.管理科学学报.2017,20(3):105-118.Zhang J W,Qiao C Z,Liu G T.Strategy to eliminate the second resource conflicts in critical chain method.Journal of Management Sciences in China,2017,20(3):105-118.(in Chinese)
[2]Zhang J,Elmaghraby S E.The relevance of the“alphorn of uncertainty”to the financial management of projects under uncertainty.European Journal of Operational Research,2014,238(1):65-76.
[3]Herroelen W,Leus R.Robust and reactive project scheduling:A review and classification of procedures.International Journal of Production Research,2004,42(8):1599-1620.
[4]Vonder S V D,Demeulemeester E,Herroelen W.Proactive heuristic procedures for robust project scheduling:An experimental analysis.European Journal of Operational Research,2008,189(3):723-733.
[5]Haz?O,Haouari M,Erel E.Robust scheduling and robustness measures for the discrete time/cost trade-off problem.European Journal of Operational Research,2010,207(2):633-643.
[6]张静文,刘耕涛.基于鲁棒性目标的关键链项目调度优化.系统工程学报,2015,30(1):136-144.Zhang J W,Liu G T.Critical chain project scheduling problem with the robust objective.Journal of Systems Engineering,2015,30(1):136-144.(in Chinese)
[7]田文迪,胡慕海,崔南方.不确定性环境下鲁棒性项目调度研究综述.系统工程学报,2014,29(1):135-144.Tian W D,Hu M H,Cui N F.Review of studies on robust project scheduling under uncertainty.Journal of Systems Engineering,2014,29(1):135-144.(in Chinese)
[8]Goldratt E M.Critical Chain.Great Barrington,Massachusetts:North River Press,1997.
[9]Herroelen W,Leus R.Project scheduling under uncertainty:Survey and research potentials.European Journal of Operational Research,2005,165(2):289-306.
[10]Leach L P.Critical chain project management improves project performance.Project Management Journal,1999,30(2):39-51.
[11]Peng W,Huang M.A critical chain project scheduling method based on a differential evolution algorithm.International Journal of Production Research,2014,52(13):3940-3949.
[12]Tukel O I,Rom W O,Eksioglu S D.An investigation of buffer sizing techniques in critical chain scheduling.European Journal of Operational Research,2006,172(2):401-416.
[13]Newbold R C.Project Management in the Fast Lane:Applying the Theory of Constraints.Boca Raton,Florida:St.Lucie Press,1998.
[14]徐小峰,郝俊,邓忆瑞.考虑多因素扰动的项目关键链缓冲区间设置及控制模型.系统工程理论与实践,2017,37(6):1593-1601.Xu X F,Hao J,Deng Y R.Project critical chain buffer setting and control model considered multiple factors disturbance.Systems Engineering:Theory&Practice,2017,37(6):1593-1601.(in Chinese)
[15]Zhang J,Song X,Chen H,et al.Determination of critical chain project buffer based on information flow interactions.Journal of the Operational Research Society,2016,67(9):1146-1157.
[16]Zhang J,Song X,Diaz E.Project buffer sizing of a critical chain based on comprehensive resource tightness.European Journal of Operational Research,2016,248(1):174-182.
[17]莫巨华.基于关键链的项目调度模型与算法.沈阳:东北大学,2005.Mo J H.Critical Chain Based Models and Algorithms for Project Scheduling.Shenyang:Northeastern University,2005.(in Chinese)
[18]彭武良,王成恩.关键链项目调度模型及遗传算法求解.系统工程学报,2010,25(1):125-133.Peng W L,Wang C E.Critical chain method project scheduling based model and its GA solution.Journal of Systems Engineering,2010,25(1):125-133.(in Chinese)
[19]Herroelen W,Leus R.The construction of stable project baseline schedules.European Journal of Operational Research,2004,156(3):550-565.
[20]Herroelen W,Leus R.On the merits and pitfalls of critical chain scheduling.Journal of Operations Management,2001,19(5):559-577.
[21]崔南方,赵雁,田文迪.基于智能算法的双目标鲁棒性项目调度.系统管理学报,2015,24(3):379-388.Cui N F,Zhao Y,Tian W D.Bi-objective robust project scheduling based on intelligent algorithms.Journal of Systems&Management,2015,24(3):379-388.(in Chinese)
[22]Mahallen M K K,Ashjari B,Yousefi F,et al.A robust solution to resource-constraint project scheduling problem.International Journal of Fuzzy Logic&Intelligent Systems,2017,17(3):221-227.
[23]Ghoddousi P,Ansari R,Makui A.An improved robust buffer allocation method for the project scheduling problem.Engineering Optimization,2016,49(4):718-731.
[24]Zheng W B,He Y K.Resource constrained project scheduling optimization with robust objective under stochastic duration of activities//Proceedings of the 23rd International Conference on Industrial Engineering and Engineering Management.Atlantis Press,Paris,2017:239-243.
[25]丁雪枫,尤建新.多模式资源受限项目调度问题的混合优化算法研究.中国管理科学,2012,20(1):154-159.Ding X F,You J X.Studies on a hybrid optimal algorithm for multi-mode resource-constrained project scheduling problem.Chinese Journal of Management Science.2012,20(1):154-159.
[26]Roghanian E,Alipour M,Rezaei M.An improved fuzzy critical chain approach in order to face uncertainty in project scheduling.International Journal of Construction Management,2018,18(1):1-13.
[27]何正文,刘人境,徐渝.基于现金流均衡目标的多模式项目调度问题研究.管理工程学报,2011,25(2):124-130.Heng Z W,Liu R J,Xu Y.Multi-mode project scheduling problems with cash flow balanced objectives.Journal of Industrial Engineering and Engineering Management,2011,25(2):124-130.(in Chinese)
[28]Kadri R L,Boctor F F.An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times:The single mode case.European Journal of Operational Research,2018,265(2):454-462.
[29]王伟鑫,葛显龙,王旭,等.基于关键链的非抢占式多项目调度多属性优化.系统工程学报,2016,31(5):689-699.Wang W X,Ge X L,Wang Xu,et al.Multi-attribute optimization for non-preemptive multi-project scheduling based on critical chain.Journal of Systems Engineering,2016,31(5):689-699.(in Chinese)
[30]王宏,林丹,李敏强.求解模糊资源受限项目调度问题的遗传算法.系统工程学报,2006,21(3):323-327.Wang H,Lin D,Li M Q.Application of genetic algorithm in solving fuzzy resource-constrained project scheduling problem.Journal of Systems Engineering,2006,21(3):323-327.(in Chinese)
[2]Zhang J,Elmaghraby S E.The relevance of the“alphorn of uncertainty”to the financial management of projects under uncertainty.European Journal of Operational Research,2014,238(1):65-76.
[3]Herroelen W,Leus R.Robust and reactive project scheduling:A review and classification of procedures.International Journal of Production Research,2004,42(8):1599-1620.
[4]Vonder S V D,Demeulemeester E,Herroelen W.Proactive heuristic procedures for robust project scheduling:An experimental analysis.European Journal of Operational Research,2008,189(3):723-733.
[5]Haz?O,Haouari M,Erel E.Robust scheduling and robustness measures for the discrete time/cost trade-off problem.European Journal of Operational Research,2010,207(2):633-643.
[6]张静文,刘耕涛.基于鲁棒性目标的关键链项目调度优化.系统工程学报,2015,30(1):136-144.Zhang J W,Liu G T.Critical chain project scheduling problem with the robust objective.Journal of Systems Engineering,2015,30(1):136-144.(in Chinese)
[7]田文迪,胡慕海,崔南方.不确定性环境下鲁棒性项目调度研究综述.系统工程学报,2014,29(1):135-144.Tian W D,Hu M H,Cui N F.Review of studies on robust project scheduling under uncertainty.Journal of Systems Engineering,2014,29(1):135-144.(in Chinese)
[8]Goldratt E M.Critical Chain.Great Barrington,Massachusetts:North River Press,1997.
[9]Herroelen W,Leus R.Project scheduling under uncertainty:Survey and research potentials.European Journal of Operational Research,2005,165(2):289-306.
[10]Leach L P.Critical chain project management improves project performance.Project Management Journal,1999,30(2):39-51.
[11]Peng W,Huang M.A critical chain project scheduling method based on a differential evolution algorithm.International Journal of Production Research,2014,52(13):3940-3949.
[12]Tukel O I,Rom W O,Eksioglu S D.An investigation of buffer sizing techniques in critical chain scheduling.European Journal of Operational Research,2006,172(2):401-416.
[13]Newbold R C.Project Management in the Fast Lane:Applying the Theory of Constraints.Boca Raton,Florida:St.Lucie Press,1998.
[14]徐小峰,郝俊,邓忆瑞.考虑多因素扰动的项目关键链缓冲区间设置及控制模型.系统工程理论与实践,2017,37(6):1593-1601.Xu X F,Hao J,Deng Y R.Project critical chain buffer setting and control model considered multiple factors disturbance.Systems Engineering:Theory&Practice,2017,37(6):1593-1601.(in Chinese)
[15]Zhang J,Song X,Chen H,et al.Determination of critical chain project buffer based on information flow interactions.Journal of the Operational Research Society,2016,67(9):1146-1157.
[16]Zhang J,Song X,Diaz E.Project buffer sizing of a critical chain based on comprehensive resource tightness.European Journal of Operational Research,2016,248(1):174-182.
[17]莫巨华.基于关键链的项目调度模型与算法.沈阳:东北大学,2005.Mo J H.Critical Chain Based Models and Algorithms for Project Scheduling.Shenyang:Northeastern University,2005.(in Chinese)
[18]彭武良,王成恩.关键链项目调度模型及遗传算法求解.系统工程学报,2010,25(1):125-133.Peng W L,Wang C E.Critical chain method project scheduling based model and its GA solution.Journal of Systems Engineering,2010,25(1):125-133.(in Chinese)
[19]Herroelen W,Leus R.The construction of stable project baseline schedules.European Journal of Operational Research,2004,156(3):550-565.
[20]Herroelen W,Leus R.On the merits and pitfalls of critical chain scheduling.Journal of Operations Management,2001,19(5):559-577.
[21]崔南方,赵雁,田文迪.基于智能算法的双目标鲁棒性项目调度.系统管理学报,2015,24(3):379-388.Cui N F,Zhao Y,Tian W D.Bi-objective robust project scheduling based on intelligent algorithms.Journal of Systems&Management,2015,24(3):379-388.(in Chinese)
[22]Mahallen M K K,Ashjari B,Yousefi F,et al.A robust solution to resource-constraint project scheduling problem.International Journal of Fuzzy Logic&Intelligent Systems,2017,17(3):221-227.
[23]Ghoddousi P,Ansari R,Makui A.An improved robust buffer allocation method for the project scheduling problem.Engineering Optimization,2016,49(4):718-731.
[24]Zheng W B,He Y K.Resource constrained project scheduling optimization with robust objective under stochastic duration of activities//Proceedings of the 23rd International Conference on Industrial Engineering and Engineering Management.Atlantis Press,Paris,2017:239-243.
[25]丁雪枫,尤建新.多模式资源受限项目调度问题的混合优化算法研究.中国管理科学,2012,20(1):154-159.Ding X F,You J X.Studies on a hybrid optimal algorithm for multi-mode resource-constrained project scheduling problem.Chinese Journal of Management Science.2012,20(1):154-159.
[26]Roghanian E,Alipour M,Rezaei M.An improved fuzzy critical chain approach in order to face uncertainty in project scheduling.International Journal of Construction Management,2018,18(1):1-13.
[27]何正文,刘人境,徐渝.基于现金流均衡目标的多模式项目调度问题研究.管理工程学报,2011,25(2):124-130.Heng Z W,Liu R J,Xu Y.Multi-mode project scheduling problems with cash flow balanced objectives.Journal of Industrial Engineering and Engineering Management,2011,25(2):124-130.(in Chinese)
[28]Kadri R L,Boctor F F.An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times:The single mode case.European Journal of Operational Research,2018,265(2):454-462.
[29]王伟鑫,葛显龙,王旭,等.基于关键链的非抢占式多项目调度多属性优化.系统工程学报,2016,31(5):689-699.Wang W X,Ge X L,Wang Xu,et al.Multi-attribute optimization for non-preemptive multi-project scheduling based on critical chain.Journal of Systems Engineering,2016,31(5):689-699.(in Chinese)
[30]王宏,林丹,李敏强.求解模糊资源受限项目调度问题的遗传算法.系统工程学报,2006,21(3):323-327.Wang H,Lin D,Li M Q.Application of genetic algorithm in solving fuzzy resource-constrained project scheduling problem.Journal of Systems Engineering,2006,21(3):323-327.(in Chinese)