Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution

作者：Qian Bin^*; Wang Ling; Huang De Xian; Wang Xiong

来源：Soft Computing, 2009, 13(8-9): 847-869.

DOI：10.1007/s00500-008-0350-8

• Multi-objective no-wait flow-shop scheduling
• Differential evolution
• Memetic algorithm
• Local search
• Exploration and exploitation

In this paper, a memetic algorithm (MA) based on differential evolution (DE), namely MADE, is proposed for the multi-objective no-wait flow-shop scheduling problems (MNFSSPs). Firstly, a largest-order-value rule is presented to convert individuals in DE from real vectors to job permutations so that the DE can be applied for solving flow-shop scheduling problems (FSSPs). Secondly, the DE-based parallel evolution mechanism is applied to perform effective exploration, and several local searchers developed according to the landscape of multi-objective FSSPs are applied to emphasize local exploitation. Thirdly, a speed-up computing method is developed based on the property of the no-wait FSSPs. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Due to the well balance between DE-based global search and problem-dependent local search as well as the utilization of the speed-up evaluation, the MNFSSPs can be solved effectively and efficiently. Simulation results and comparisons demonstrate the effectiveness and efficiency of the proposed MADE.

• 出版日期2009-7
• 单位清华大学; 昆明理工大学