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

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