针对资源调度问题的局部优化算法  

Local optimization algorithm for resource scheduling problem

作　　者：尹红健[1] 崔凌云[2] 

机构地区：[1]湖南化工职业技术学院信息工程系,湖南株洲412004 [2]河北工程技术高等专科学校计算机系,河北沧州061001

出　　处：《计算机工程与设计》2010年第22期4893-4896,4900,共5页Computer Engineering and Design

摘　　要：由于现有局部搜索算法在处理数据量较大的受限资源工程调度问题时效果欠佳,提出了一种与FBI优化相结合的局部搜索方案——FBLS。FBLS利用问题的对称性,以局部搜索的解集为单位,在原问题与对称问题上交替进行优化。通过分析领域中解的合法性以及可能出现的重复情况,削减领域中解的数量,提高搜索效率。在PSPLIB的数据测试中,经FBLS优化所得到的结果已经优于所有非智能甚至大部分智能演化算法。作为一种通过局部搜索进行优化的方法,FBLS可以被灵活诮用于各种已有的智能算法框架求解RCPSP问题。Resource-constrained project scheduling problem （RCPSP） is a well studied classical problem in operational research. A large body of literature exists, and dozens of approaches are developed. RCPSP is a NP-hard problem in strong sense. Due to its complexity, the most effective algorithms to date are evolutionary algorithms such as genetic algorithms, improved by local search or local optimization. Inspired by the well known forward-backward improvement （FBI） algorithm, a new local search heuristic is developed, namely, forward backward local search （FBLS）. Computational experiments based on 1560 standard benchmark test cases from PSPLIB, shows FBLS outperform FBI given the similar computational resources. Computational experiments also show FBLS outperforms all heuristics, local search and most ofmeta-heuristics described in the literature to date. Due to the nature of local search, FBLS operates on a given sequence of activities and iteratively improve the solutions. That fact that this heuristics operates on sequences of activities, it is well suited as a building block to form more sophisticated meta-heuristics, genetic algorithm, simulated annealing, to name a few.

关 键 词：资源受限工程调度问题 局部搜索 领域优化 搜索效率 对称问题 

分 类 号：TP384[自动化与计算机技术—计算机系统结构]