Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1175.90199
Wang, Ling; Pan, Quan-Ke; Suganthan, P.N.; Wang, Wen-Hong; Wang, Ya-Min
A novel hybrid discrete differential evolution algorithm for blocking flow shop scheduling problems. (English)
[J] Comput. Oper. Res. 37, No. 3, 509-520 (2010). ISSN 0305-0548

Summary: This paper proposes a novel hybrid discrete differential evolution (HDDE) algorithm for solving blocking flow shop scheduling problems to minimize the maximum completion time (i.e., makespan). Firstly, in the algorithm, the individuals are represented as discrete job permutations, and new mutation and crossover operators are developed for this representation, so that the algorithm can directly work in the discrete domain. Secondly, a local search algorithm based on insert neighborhood structure is embedded in the algorithm to balance the exploration and exploitation by enhancing the local searching ability. In addition, a speed-up method to evaluate insert neighborhood is developed to improve the efficiency of the whole algorithm. Computational simulations and comparisons based on the well-known benchmark instances of {\it E. Taillard} [Eur. J. Oper. Res. 64, No.~2, 278--285 (1993; Zbl 0769.90052)], by treating them as blocking flow shop problem instances with makespan criterion, are provided. It is shown that the proposed HDDE algorithm not only generates better results than the existing tabu search (TS) and TS with multi-moves (TS+M) approaches proposed by {\it J. Grabowski} and {\it J. Pempera} [Omega 35, No.~3, 302--311 (2007)], but also outperforms the hybrid differential evolution (HDE) algorithm developed by {\it B. Qian} et al. [Comput. Oper. Res. 36, No.~1, 209--233 (2009; Zbl 1163.90507)] in terms of solution quality, robustness and search efficiency. Ultimately, 112 out of 120 best known solutions provided by Grabowski and Pempera [loc. cit.] and {\it D. P. Ronconi} [Ann. Oper. Res. 138, 53--65 (2005; Zbl 1091.90075)] are further improved by the proposed HDDE algorithm.

MSC 2000:: *90B35 Scheduling theory
90C39 Dynamic programming

Keywords: blocking flow shop; differential evolution; discrete differential evolution; hybrid algorithm; local search; speed-up

Citations: Zbl 0769.90052; Zbl 1163.90507; Zbl 1091.90075

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]