Multi-mode Resource-constrained Repetitive Scheduling Model Based on Constraint Programming
The multi-mode resource-constrained project scheduling problem(MRCPSP)is a classical optimization problem in the field of project management.The objective is to identify a schedule with the shortest possible project duration by assigning an execution mode and a start time to each activity.When dealing with the MRCP-SP of repetitive projects(MRCPSP-RP),it is necessary to consider logic relations between units,as well as the continuity requirement and scheduling strategy of each activity.If an activity requires work continuity,all sub-activities of the activity must be executed continuously without interruption.Otherwise,allowing work interrup-tions can increase scheduling flexibility.Three scheduling strategies are available for activities in the MRCPSP-RP:1)the invariant mode strategy,which requires that all sub-activities in the same activity use the same execution mode;2)the disordered mode strategy,which allows all sub-activities in the same activity to choose their execution modes at their own discretion;and 3)the ordered mode strategy,which allows an activity to gradually select faster or slower execution modes during the execution.A number of models and algorithms have been proposed for solving the MRCPSP-RP,yet they still have the following shortcomings.Firstly,the assumption is made that all activities must satisfy the continuity requirement,which cannot deal with the situation in which activities can be interrupted.Secondly,the scheduling strategy of each activity is assumed to be known in advance,with the optimization of this scheduling strategy for the activi-ties themselves overlooked.The aim of this paper is to develop a constraint programming(CP)model for solving MRCPSP-RP that fully considers the continuity requirements of different activities and the optimization of activity scheduling strategies.The CP model defines each sub-activity in terms of interval variables and describes the objective function and constraints using CP expressions.The implementation of CP involves two main steps:problem specification and solving.The first step aims to reformulate the problem as an equivalent constraint satis-faction problem(CSP),while the second step aims to solve the CSP using a search algorithm and constraint propagation mechanism.In comparison with the MILP model,the CP model exhibits a notable reduction in the size of variables and constraints.This paper validates the effectiveness of the CP model using a residential construction project.The case study involves four scenarios,where Scenarios 1 to 3 require all activities to adopt an invariant mode strategy,an ordered mode strategy,and an unordered mode strategy,respectively,and maintain work continuity.Scenario 4 requires all activities to adopt a disordered mode strategy and allows for work interruptions.The results demon-strate that,for a given level of resource availability,the use of the ordered or disordered mode strategy can signif-icantly reduce the total project duration in comparison with the invariant mode strategy.The average reduction in the project duration is 10.31%and 11.91%,respectively.Furthermore,if work interruption is further consid-ered on the basis of the disordered mode strategy,the project duration can be reduced by 10.99%to 23.01%.Moreover,the computational performance of the CP model is evaluated through numerical experiments,in which the test problems are classified into seven categories based on their size,from small to large:A,B,C,D,E,F,and G.The results demonstrate that the CP model is capable of finding feasible solutions to all the cases within a limited time.All cases in the problem sets,A,B,and C,and some in the problem sets,D,E,F,and G,can be solved accurately.In contrast,the MILP model can only handle the smaller problem sets,A,B and C,with only 56.7%of cases solved exactly.As the problem size increases,the computational performance of the MILP model deteriorates significantly,with the average and maximum deviations corresponding to the problem set C reaching 22.96%and 50%,respectively.For the larger problem sets,D,E,F,and G,the MILP model is unable to provide a feasible solution to any of the instances within one hour.
国家科技期刊平台
NSTL
万方数据
