多资源约束下的项目调度邻域搜索算法  

Neighborhood Search Algorithm to Solve Resource Constrained Project Scheduling Problem

作　　者：张凯[1] 

机构地区：[1]浙江工业大学教育科学与技术学院,杭州310023

出　　处：《计算机系统应用》2014年第2期123-127,41,共6页Computer Systems & Applications

基　　金：2013年浙江工业大学大学生创新创业训练计划项目(2013031)

摘　　要：为了解决项目调度过程中不同项目之间的资源冲突问题,提出了一种基于拓扑排序的邻域搜索算法.设计跳动和微动两个操作,实现编码的更新,保证解的多样性与收敛性.用项目调度问题库(Project Scheduling Problen Library-PSPLIB)中不同规模的实例对算法进行检验,结果表明,这种邻域搜索算法能够找到较优的解.用这种邻域搜索算法计算其它算法的案例,结果也显示这种算法具有一定的优越性.对这种邻域搜索算法的不同参数进行实验,分析了参数设置对算法性能的影响.To solve the resource conflicts between different activities, a new neighborhood search algorithm based on topological sorting was proposed. Two operations namely jumping move and micro-move were designed to update code and get better results. Use cases with different scales from Project Scheduling Problem Library to test the performances of the algorithm. The results showed that the algorithm had searched excellent solutions. Use the algorithm proposed to solve the case in the literature, the results showed that the algorithm had its superiority. Test the proposed algorithm with different parameters and analyze the influences of parameter setting on algorithm performance.

关 键 词：拓扑排序 跳动 微动 邻域搜索 

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]