混合贪心策略人工蜂群的两阶段算法针对资源受限项目调度问题的研究

Research on a Two-Phase Hybrid Greedy Artificial Bee Colony Algorithm for Resource-Constrained Project Scheduling Problem

摘要: 资源受限项目调度问题(Resource-Constrained Project Scheduling Problem, RCPSP)是最具代表性的一类项目调度问题，由于问题包含多个约束，因此当任务规模较大时难以求得全局最优解。本文提出了混合贪心策略人工蜂群的两阶段算法，在第一阶段采用混合初始解生成方式，在雇佣蜂阶段引入差分进化策略，并将观察蜂划分为精英开采与随机开采两种模式，设计自适应阈值生成机制；将第一阶段生成解决方案作为第二阶段的初始解，第二阶段开发了基于贪心策略的解优化机制。在PSPLIB基准数据集上，将该算法与人工蜂群算法、差分进化算法以及分支定价算法在数据集上的最优解覆盖率进行对比，分别优于经典算法5.93%，6.72%和11.32%。并用该算法求解了工程项目实例，得出了项目调度方案。

Abstract: The Resource-Constrained Project Scheduling Problem (RCPSP) is one of the most representative types of project scheduling problems. Due to the multiple constraints involved, it is difficult to obtain a globally optimal solution when the task scale is large. A two-phase hybrid greedy artificial bee colony algorithm is proposed. In the first stage, a hybrid initial solution generation method is adopted. A differential evolution strategy is introduced during the employed bee phase, and the onlooker bees are divided into two modes: elite exploitation and random exploitation, with an adaptive threshold generation mechanism designed. The solutions generated in the first stage serve as the initial solutions for the second stage, where a solution optimization mechanism based on a greedy strategy is developed. On the PSPLIB benchmark dataset, the proposed algorithm is compared with the artificial bee colony algorithm, differential evolution algorithm, and branch-and-price algorithm in terms of optimal solution coverage rates. The results show that it outperforms the classical algorithms by 5.93%, 6.72%, and 11.32%, respectively. Furthermore, the algorithm is applied to a project case example, yielding a feasible project scheduling plan.