AN DE-BASED MEMETIC ALGORITHM FOR RE-ENTRANT PERMUTATION FLOWSHOP SCHEDULING PROBLEMS
This paper proposed an effective differential evolution (DE)-based memetic algorithm (MA) for the reentrant permutation flowshop scheduling problem (RPFSP), which is an extension of classical permutation flowshop problem (CPFSP). In the RPFSP, the jobs must be processed in the order M1,M2…Mm,M1,M2,Mm…，M1,M2,Mm and no passing is allowed in the process, that is, the job can be decomposed into several layer and the job order is the same on any machine at each layer. In this paper, the makespan criterion is considered. In the proposed DE-based MA (DEMA), the DE-based operators cooperate with several local search operators to balance the exploration and exploitation abilities. In particular, the evolutionary searching mechanism of DE, which is characterized by difference based mutation, discrete crossover and greedy knockout selection, is applied to effectively perform exploration. Furthermore, several local search operators are utilized to perform exploitation. First of all, the rand-order value (ROV) rule based on the random key representation is adopted to convert the continuous vectors into job permutation, which make DE suitable for the RPFSP. Secondly, the modified NEH, CDS and ITB heuristics are incorporated into the initialization of DE to generate an initial population with certain quality and diversity. Thirdly, five local searches are imbedded into the proposed algorithm to make reasonable balance between the global exploration and local exploitation. The adaptive meta-Lamarckian learning strategy is employed to decide which local search to be used adaptively at running time in the spirit of Lamarckian learning. Simulations and comparisons are conducted against the best performing heuristic and metaheuristic algorithms from the literature based on random generated instances. It is shown that the proposed algorithm is more effective and efficient in finding better solutions than other algorithms when applied to RPFSP for the makespan criterion.
Differential Evolution Memetic Algorithms Re-entrant Permutation Flowshop Scheduling Problem
Ling-Po Li Ling Wang
Tsinghua University, Beijing, 100084, China Tsinghua National Laboratory for Information Science and Tsinghua University, Beijing, 100084, ChinaTsinghua National Laboratory for Information Science and
国际会议
上海
英文
1-6
2009-08-02（万方平台首次上网日期，不代表论文的发表时间）