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

Abstract: 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 (F&F) 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.

Key words: scheduling, resource-constrained project, iterated local search, double-justification, filter-and-fan search, path relinking