An effective shuffled frog-leaping algorithm for resource-constrained project scheduling problem

作者：Fang, Chen; Wang, Ling^*

来源：Computers & Operations Research, 2012, 39(5): 890-901.

DOI：10.1016/j.cor.2011.07.010

• Resource-constrained project scheduling
• Shuffled frog-leaping algorithm
• Resource-based crossover
• Combined local search
• Speed-up evaluation
• Design-of-experiment

In this paper, we propose an effective heuristic based on the framework of the shuffled frog-leaping algorithm (SFLA) for solving the resource-constrained project scheduling problem (RCPSP). We encode the virtual frog as the extended activity list (EAL) and decode it by the SFLA-specific serial schedule generation scheme (SSSGS). The initial population is generated by the regret-based sampling method and the priority rule. Then, virtual frogs are partitioned into several memeplexes, and each memeplex evolves by adopting the effective resource-based crossover (RBCO). To enhance the exploitation ability, a combined local search including permutation-based local search (PBLS) and forward-backward improvement (FBI) is performed in each memeplex. To maintain the diversity of each memeplex, virtual frogs are periodically shuffled and reorganized into new memeplexes. Basing on some theoretical analysis, speed-up evaluation methods are proposed to improve the efficiency of the SFLA, which are also suitable for other heuristics designed for RCPSP. In addition, we make use of a design-of-experiment method to determine the set of suitable parameters for the SFLA. Computational results and comparisons with some typical existing algorithms demonstrate the effectiveness of the proposed SFLA.

• 出版日期2012-5
• 单位清华大学