求解资源受限项目调度问题的启发式方法  

Heuristic approach for resource-constrained project scheduling problems

作　　者：卢睿[1] 王成恩[1] 

机构地区：[1]东北大学流程工业综合自动化教育部重点实验室,辽宁沈阳110004

出　　处：《计算机集成制造系统》2009年第12期2439-2444,2466,共7页Computer Integrated Manufacturing Systems

基　　金：教育部新世纪优秀人才支持计划资助项目(NCET-04-0281);总装备部武器装备预研基金资助项目(9140A18010106LN0101);国家自然科学基金资助项目(60604025)~~

摘　　要：为求解资源受限项目的调度问题,将过滤扇出和路径重连两种方法相结合,作为迭代局部搜索的摄动过程,提出一种新的迭代局部搜索方法。设计了与调度方案有唯一对应关系的任务列表,并通过附加信息制约邻域的产生,进一步缩小搜索空间。采用对齐技术提高解的质量,设计并结合使用两个摄动方法,以寻求更大范围内的邻域,加强了跳出局部最优的能力。迭代过程中采用精英解集代替传统的迭代局部搜索方法中的单点初始解,并保存搜索历史中的较好解。最后通过标准问题库中的四种问题验证了算法的求解质量。To solve the problem of resource-constrained project scheduling,a heuristic approach for the Resource Constrained Project Scheduling Problem（RCPSP） was proposed by using Filter-and-Fan（FF） and Path Relinking as perturbation procedure in Iterated Local Search（ILS）.In order to reduce the search space,the task list was designed which was corresponding to the unique scheduling scheme and the neighborhood generation was restricted by additional information.The quality of solution was improved by double-justification technique.And two perturbation methods were designed and combined to explore larger neighborhood,and to overcome optimality.An elite set,other than one solution used in typical ILS,was used to join the iterative process and to preserve better solutions in historical search.Finally the quality of the proposed approach was verified by four project scheduling problem library instance sets in PSPLIB.

关 键 词：调度 资源受限项目 迭代局部搜索 对齐 过滤扇出搜索 路径重连 

分 类 号：C934[经济管理—管理学]