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

Decomposition algorithm for resource-constrained multi-project scheduling problem

作　　者：王军强[1,2] 张松飞[1,2] 陈剑[1,2] 张映锋[1,2] 孙树栋[1,2] 

机构地区：[1]西北工业大学系统集成与工程管理研究所,陕西西安710072 [2]西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072

出　　处：《计算机集成制造系统》2013年第1期83-96,共14页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(51275421;51175435);西北工业大学基础研究基金资助项目(JC20120227)~~

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

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

分 类 号：TH166[机械工程—机械制造及自动化]