一种求解资源受限多项目调度问题的分解算法

摘要

In order to address the multi-objective optimization of resource-constrained multi-project scheduling problem (RCMPSP), a two-stage decomposition algorithm based on hierarchical decomposing strategy was proposed to orderly tackle their precedence constraints and resource constraints in an integrated framework. Furthermore, the solving procedure of RCMPSP was presented, structured by two stages. In the first stage of precedence constraints satisfactory optimization stage, a revised ant colony optimization (ACO) was presented to obtain the feasible activity sequence. In order to accelerate the convergence efficiency and quality, a revised pheromone increment updating operator of ACO with combination of parallel schedule generation scheme (PSGS) were used During the process constructing feasible precedence activity sequence, a sequencing indicator was presented to solve the constraint conflict resolution problem when some parallel activities competed some resources simultaneously. Specifically, the TOPSIS based on entropy weight and multi-attribute decision making based on ordered weighted averaging (OWA) operator was used to obtain the integrated importance measure of activity as the indicator. At the second stage of resource-constraints satisfactory optimization stage, the obtained optimum precedence activity sequence was taken as the stage's input, and the resource capacity was examined and adjusted one by one until the optimal scheduling solution was obtained. The results illustrated the effectiveness of the proposed two-stage decomposition algorithm for RC-MPSP.%针对资源受限多项目调度的多目标优化问题,采用约束逐层分解策略,提出了依次处理项目时序约束和资源约束的两阶段分解算法.第一阶段为时序约束优化阶段,采用蚁群算法进行任务列表的优化求解.通过改进信息素增量规则并采用并联进度生成机制,提高蚁群算法的求解效率和质量.其中,在构建任务合成链表的过程中遇到并联活动抢夺资源情形,采用基于熵权的逼近理想解排序法和基于有序加权平均算子的多属性决策方法来确定活动的综合权重,并依据权重对冲突活动进行排序,实现资源的冲突消解.第二阶段为资源约束优化阶段,以获得的优化任务合成链表为输入,逐项进行资源能力约束的核查与调整,最终生成项目调度的优化方案.通过多项目算例仿真结果验证了所提方法的有效性.