消除二次资源冲突的鲁棒性双目标关键链项目调度优化

Robust and bi-objective critical chain project scheduling optimization with a second resource conflicts eliminating policy

传统关键链方法无法解决插入输入缓冲引起的二次资源冲突困境,更不能表述和建模调度方案的鲁棒性,这极大地限制了它在项目进度管理中的广泛应用。本文从鲁棒调度和双目标优化两个角度拓展和创新了传统关键链方法。首先,针对最棘手的二次资源冲突困境,从鲁棒优化视角提出基于局部重调度的二次资源冲突消除策略,进而设计基于消除策略的鲁棒性测度指标;其次,构建同时优化项目工期和调度方案鲁棒性的双目标关键链项目调度模型,并设计混合差分进化算法求解。在获取基准调度计划阶段为克服现有的关键链识别方法的不足,设计基于鲁棒性资源流网络的关键链识别算法并将其嵌入差分进化主算法中。最后,设计并运行大规模数值测试实验,输出数据的统计结果验证了关键链识别算法和二次资源冲突消除策略的有效性,同时也表明了本文设计混合差分进化算法的优越性。

In the context of economic globalization and the rapid development of information technology,the progression of a project is more complex and unpredictable.Therefore,project management under uncertainty arises.As an efficient project scheduling method,Critical Chain Method(CCM)could reduce the impact of uncertain activity duration on projects by inserting buffers.Specifically,the principle of CCM is to insert feeding buffers wherever the non-critical chain joins the critical chain and to insert the project buffer at the end of the critical chain.However,the existing studies on CCM mostly focused on makespan minimization and the robustness which reflects the ability to cope with the uncertainty was ignored.Meanwhile,to avoid the second resource conflicts dilemma caused by inserting feeding buffers,most previous studies assumed that the feeding buffer does not consume resources.This assumption is inconsistent with the nature of the buffer and greatly limited the application of the CCM in project management.In order to solve the aforementioned problems effectively,this paper focuses on the robust optimization for critical chain project scheduling.The present study unfolds as follows.First,a local rescheduling strategy to solve the second resource conflicts dilemma is proposed,and a robustness index according to the rescheduling strategy is designed to measure the robustness of the project schedule.Then,a formulation of Robust and Bi-objective Critical Chain Project Scheduling Problem(RB-CCPSP)is proposed to minimize project duration and maximize robustness simultaneously.Finally,a hybrid differential evolution(HDE)algorithm is put forward to solve the formulation.This paper consists of the following four sections.In the first section,application steps of the classical CCM are introduced and the formation mechanism of the second resource conflicts dilemma is qualitatively analyzed.Meanwhile,a robust resource flow network is constructed on the basis of heuristic rules,and critical chain and non-critical chains are identified based on this network.In the second section,a quantitative analysis of the second resource conflicts dilemma is conducted,and the conflicts are classified according to the interference relationship between the feeding buffers and the critical activities.Furthermore,on the basis of above analysis,a two-stage heuristic second resource conflicts eliminating strategy based on local rescheduling is designed,and the robustness measurement of the second scheduling plan is put forward.By taking both the makespan minimization and robustness maximization as objectives,a robust critical chain project scheduling model considering the second resource conflicts dilemma is proposed.In the third section,to cope with the NP-hardness and bi-objective characteristics of the problem,a hybrid differential evolution algorithm is designed by integrating the differential evolution algorithm and variable neighborhood search(VNS)approach.In the global search,considering the bi-objective characteristics,the selection operator and the non-dominant set updating operator are proposed.Then in the local search,the Insert and Swap operators are put forward.In the fourth section,the validity of the model and the algorithm proposed in this study are verified through large scale numerical experiments.As for model effectiveness,compared with the classical critical chain project scheduling problem(CCPSP)and the robust critical chain project scheduling problem(rCCPSP),the robust critical chain project scheduling model considering second resource conflicts dilemma is more conducive to the smooth progression of the project and increase the probability of the project being completed on time.As for algorithm effectiveness,compared with NSGA-Ⅱand the classical differential evolution algorithm,the HDE algorithm could solve the bi-objective critical chain project scheduling model with better solution quality.In addition,the VNS could improve the solution significantly.To sum up,the method taking the secondary resource conflicts dilemma into consideration put forward in the present study significantly improves the utility of CCM.Moreover,the robust and bi-objective critical chain project scheduling optimization model proposed in this study could generate different project schedules according to the specific uncertainty conditions.The present study could provide insights into decision-making about project management under uncertainty.