Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2007.08.007 Byline: Bin Qian (a)(b), Ling Wang (a), De-xian Huang (a), Wan-liang Wang (c), Xiong Wang (a) Abstract: This paper proposes an effective hybrid algorithm based on differential evolution (DE), namely HDE, to solve multi-objective permutation flow shop scheduling problem (MPFSSP) with limited buffers between consecutive machines, which is a typical NP-hard combinatorial optimization problem with strong engineering background. Firstly, to make DE suitable for solving scheduling problems, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Secondly, after the DE-based exploration, an efficient local search, which is designed based on the landscape of MPFSSP with limited buffers, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search) in the whole solution space, but it also adopts problem-dependent local search to perform thorough exploitation (local search) in the promising sub-regions. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Moreover, the convergence property of HDE is analyzed by using the theory of finite Markov chain. Finally, simulations and comparisons based on benchmarks demonstrate the effectiveness and efficiency of the proposed HDE. Author Affiliation: (a) Department of Automation, Tsinghua University, Beijing 100084, China (b) Department of Automation, Kunming University of Science and Technology, Kunming 650051, China (c) Software College, Zhejiang University of Technology, Hangzhou 310032, China