Advanced Search

Query:

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

Format:

Display: entries per page entries

Zbl 1144.90393
Pan, Quan-Ke; Tasgetiren, M.Fatih; Liang, Yun-Chia
A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem. (English)
[J] Comput. Oper. Res. 35, No. 9, 2807-2839 (2008). ISSN 0305-0548

Summary: A discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of {\it E. Taillard} [Eur. J. Oper. Res. 64, No. 2, 278--285 (1993; Zbl 0769.90052)] by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by {\it J. Carlier} [RAIRO, Rech. Opér. 12, 333--350 (1978; Zbl 0401.90052)], {\it J. Heller} [Oper. Res. 8, 178--184 (1960; Zbl 0092.27910)], and {\it C. R. Reeves} [Comput. Oper. Res. 22, No. 1, 5--13 (1995; Zbl 0815.90097)] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by {\it Ch. Rajendran} [J. Oper. Res. Soc. 45, No. 4, 472--478 (1994; bl 0799.90060)] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by {\it A. Fink} and {\it St. Voss} [Eur. J. Oper. Res. 151, No. 2, 400--414 (2003; Zbl 1052.90030)]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and Voss [loc. cit.] were improved by the VND version of the DPSO algorithm.

MSC 2000:: *90B35 Scheduling theory
90C59 Approximation methods and heuristics

Keywords: no-wait flowshop; makespan; total flowtime; particle swarm optimization; variable neighborhood descent

Citations: Zbl 0769.90052; Zbl 0401.90052; Zbl 0092.27910; Zbl 0815.90097; Zbl 1052.90030

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]