Abstract: 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 MRCPSP 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 interruptions 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 activities 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 satisfaction 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 demonstrate that, for a given level of resource availability, the use of the ordered or disordered mode strategy can significantly 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 considered 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.

Key words: repetitive scheduling, resource availability, scheduling strategy, constraint programming

摘要： 多模式资源受限项目调度问题(MRCPSP)是一类经典的优化问题,旨在满足工序间优先关系和资源约束条件下最小化项目总工期。重复性项目是指部分或全部工序需要在多个单元上重复执行的项目,针对此类项目的MRCPSP(简称MRCPSP-RP)需要进一步满足单元间的逻辑关系,并考虑工序的连续性要求和可能的调度策略。本文从约束规划(CP)角度构建了求解MRCPSP-RP的CP模型,以区间变量定义每个子工序并利用CP表达式描述目标函数和约束条件,与MILP模型相比,大幅减少了变量和约束的规模。本文利用一个住宅建筑项目验证了CP模型的有效性。基于大量随机算例的数值实验表明,CP模型的计算性能优于MILP模型和已有的启发式算法,能在较短时间内给出较大规模问题的最优或高质量解。

关键词: 重复性项目调度, 资源可用性, 调度策略, 约束规划