Abstract: With fierce competition in the market, multiple projects are gradually decentralized both geographically and organizationally. Enterprises need to ensure that each project is performed and the limited shared resources are appropriately allocated to each project. Therefore, for this problem of multi-project management, the distributed resource-constrained multi-project scheduling problem (DRCMPSP) is proposed. However, the current research on the DRCMPSP mainly considers the case where the resource requirement and completion time are for a single activity mode, ignoring the reality that project activities often have multiple execution modes. Therefore, based on the multi-agent system (MAS), this study considers different execution modes of activities and realizes the systematic coordination of distributed multi-project scheduling using a two-layer algorithm. The DRCMPSP is not only closer to the actual situation of distributed multi-project scheduling but also can effectively reduce makespan tardiness, resource idleness and project interruptions,and thus improve the efficiency of distributed multi-project management in enterprises.
The DRCMPSP consists of multiple single projects, each with a different arrival time. First, the project agent (PA) makes project scheduling decisions independently to minimize the project makespan, essentially the multi-mode resource-constrained project scheduling problem (MRCPSP). Therefore, this paper proposes an improved variable neighborhood search (MVNS) algorithm to solve the local scheduling problem. Second, based on the local scheduling results, each PA submits the global resource requirements and the mode information of the corresponding activities to the coordinate agent (CA). Due to the limited global resources and the self-interested tendency of the agent, in order to minimize the makespan, it will prioritize scheduling the activities according to the mode with the shortest activity duration to obtain more global resources earlier. Therefore, the negotiation mechanism based on mode adjustment is proposed in this paper. CA minimizes project disruption and improves resource utilization by mode adjustment of some activities in the original schedule. Finally, PA makes corresponding adjustments to the original scheduling plan and thus obtains the final distributed multi-project scheduling plan.
To verify the effectiveness of the MVNS algorithm for localized scheduling and the global negotiated scheduling algorithm based on mode adjustment, we test the algorithms based on the MRCPSP set of instances in the PSPLIB library. The results show that the MVNS algorithm is computationally faster and has better scale adaptation, and the computational results are better than most of the algorithms published in PSPLIB. The mode-adjustment-based negotiation mechanism results in an average saving of 38% and 23% in the total cost of deferral (TTC) compared to the two cases of randomly determining a mode and mode-adjustment only. The average project delay (APD) is reduced by an average of 18% for the mode adjustment-based negotiation mechanism compared to the randomized mode case. In contrast, the APD is not reduced on average compared to the mode adjustment-only case. As the size of the arithmetic example increases, the competition for global resources among projects intensifies, and the total project extension cost gradually increases. However, the total project extension cost increase can be effectively reduced by model adjustment and prioritizing project activities with high extension costs.
Adjusting multiple modes of activities also contributes to improving project robustness under unstable resource supply. Future research will establish multi-project robustness measurements and construct an integrated optimization model for global resource allocation and robust scheduling of distributed multi-projects under resource uncertainty. In addition, resources between distributed multi-projects need to be transferred several times, and some corresponding costs are often incurred. Therefore, decentralized multi-project scheduling considering resource transfer cost, multi-project extension cost, and robust multi-objective optimization is the next research direction for this paper.

Key words: multi-mode, multi-project scheduling, variable neighborhood search, negotiate mechanism

摘要： 针对实践中分布式多项目的活动往往具有多种执行模式,提出多模式分布式资源约束多项目调度问题。在项目动态到达环境下,考虑活动不同的执行模式,以工期最短和多项目延期成本最小为目标分别构建局部单项目调度模型和全局多项目决策模型,采用改进变邻域搜索算法求解初始局部调度计划,并设计基于模式调整的全局协商调度算法求解全局决策模型,通过双层算法实现分布式多项目调度中局部单项目调度与全局多项目调度系统性协调,减少项目中断和多项目延期成本。基于构建的多模式测试集进行的多项目数值实验表明:本文设计的双层算法可有效求解多模式分布式多项目调度问题,并且对不同规模问题求解具有良好的适应性。

关键词: 多模式, 多项目调度, 变邻域搜索, 协商机制