Decomposition algorithm for resource-constrained multi-project scheduling problem

• Article •

Decomposition algorithm for resource-constrained multi-project scheduling problem

WANG Jun-qiang1,2, ZHANG Song-fei1,2, CHEN Jian1,2, ZHANG Ying-feng1,2, SUN Shu-dong1,2

1.Institute of System Integrated & Engineering Management, Northwestern Polytechnical University, Xi'an 710072, China;2.Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Ministry of Education, Northwestern Polytechnical University, Xi'an 710072, China

Received:2013-01-25 Revised:2013-01-25 Online:2013-01-25 Published:2013-01-25

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

王军强1,2，张松飞1,2，陈剑1,2，张映锋1,2，孙树栋1,2

1.西北工业大学系统集成与工程管理研究所，陕西西安710072；2.西北工业大学现代设计与集成制造技术教育部重点实验室，陕西西安710072

Abstract

Abstract: 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 RCMPSP.

Key words: resource-constrained multi-project scheduling problem, multi-objective optimization, ant colony optimization, conflict resolution, multi-attribute decision making

摘要： 针对资源受限多项目调度的多目标优化问题，采用约束逐层分解策略，提出了依次处理项目时序约束和资源约束的两阶段分解算法。第一阶段为时序约束优化阶段，采用蚁群算法进行任务列表的优化求解。通过改进信息素增量规则并采用并联进度生成机制，提高蚁群算法的求解效率和质量。其中，在构建任务合成链表的过程中遇到并联活动抢夺资源情形，采用基于熵权的逼近理想解排序法和基于有序加权平均算子的多属性决策方法来确定活动的综合权重，并依据权重对冲突活动进行排序，实现资源的冲突消解。第二阶段为资源约束优化阶段，以获得的优化任务合成链表为输入，逐项进行资源能力约束的核查与调整，最终生成项目调度的优化方案。通过多项目算例仿真结果验证了所提方法的有效性。

关键词: 资源受限多项目调度问题, 多目标优化, 蚁群算法, 冲突消解, 多属性决策

CLC Number:

TH166

WANG Jun-qiang1,2, ZHANG Song-fei1,2, CHEN Jian1,2, ZHANG Ying-feng1,2, SUN Shu-dong1,2. Decomposition algorithm for resource-constrained multi-project scheduling problem[J]. .

王军强1,2，张松飞1,2，陈剑1,2，张映锋1,2，孙树栋1,2. 一种求解资源受限多项目调度问题的分解算法[J]. .

[1]	. Multi-objective optimization for production scheduling of precast components considering resource constraints [J]. , 2021, 27(8): 2248-2259.
[2]	. Multi-objective optimization of blockchain based on industrial internet of things [J]. , 2021, 27(8): 2382-2392.
[3]	. Improved wolf pack algorithm for multi-objective disassembly line balancing problem under space constraints [J]. , 2021, 27(6): 1569-1581.
[4]	. Green manufacturing-oriented multi-objective scheduling optimization for half built-up marine crank shaft component workshop [J]. , 2021, 27(6): 1714-1727.
[5]	. Multi-objective scheduling algorithm for one worker job shop considering learning effect [J]. , 2021, 27(5): 1361-1370.
[6]	. Optimal solution selection and multi-objective optimization of ship dredging scheduling problem based on flexible berthing [J]. , 2021, 27(5): 1531-1540.
[7]	. Optimization formedium-term schedule planning of marine engineering production subsection construction [J]. , 2021, 27(3): 770-786.
[8]	. Optimization of automatic stacker picking sequence under the mixed picking strategy [J]. , 2021, 27(3): 933-942.
[9]	. Game models andprofit-sharing contract of green supply chain based on multi-objective optimization [J]. , 2021, 27(3): 943-953.
[10]	. Dynamic multi-objective optimization strategy of milling parameters based on digital twin [J]. , 2021, 27(2): 478-486.
[11]	. Integrated optimization of cutting parameters and flexible job shop scheduling based on improved discrete gravity search algorithm [J]. , 2021, 27(12): 3519-3535.
[12]	. Ant colony labor division algorithm for position selection in circle packing problem [J]. , 2021, 27(12): 3578-3590.
[13]	. Collaborative optimization of robotic spraying trajectory based on dual-population chaotic search particle swarm optimization algorithm [J]. , 2021, 27(11): 3148-3158.
[14]	. Two-stage dynamic differential agent cellular automata algorithm [J]. , 2020, 26(第4): 989-1000.
[15]	. Dynamic multi-objective optimization model and algorithm for logistics network [J]. , 2020, 26(第4): 1142-1150.