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

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

来源：Information Sciences, 2011, 181(20): 4804-4822.

DOI：10.1016/j.ins.2011.06.014

• Multi-mode resource-constrained project scheduling
• Shuffled frog-leaping algorithm
• Multi-mode serial schedule generation scheme
• Multi-mode permutation based local search
• Multi-mode forward-backward improvement
• Combined local search

In this paper, an effective shuffled frog-leaping algorithm (SFLA) is proposed for solving the multi-mode resource-constrained project scheduling problem (MRCPSP). In the SFLA, the virtual frogs are encoded as the extended multi-mode activity list (EMAL) and decoded by the multi-mode serial schedule generation scheme (MSSGS). Initially, the mode assignment lists of the population are generated randomly, and the activity lists of the population are generated by the regret-based sampling method and the latest finish time (LFT) priority rule. Then, virtual frogs are partitioned into several memeplexes that evolve simultaneously by performing the simplified two-point crossover (STPC). To enhance the exploitation ability, the combined local search including the multi-mode permutation based local search (MPBLS) and the multi-mode forward-backward improvement (MFBI) is further performed in each memeplex. To maintain the diversity of each memeplex, virtual frogs are periodically shuffled and reorganized into new memeplexes. Computational results based on the well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed SFLA.

• 出版日期2011-10-15
• 单位清华大学