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

Local optimization algorithm for resource scheduling problem

由于现有局部搜索算法在处理数据量较大的受限资源工程调度问题时效果欠佳,提出了一种与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.