A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

0.00 Avg rating0 Votes
Article ID: iaor20084396
Country: Netherlands
Volume: 177
Issue: 3
Start Page Number: 1930
End Page Number: 1947
Publication Date: Mar 2007
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics
Abstract:

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard, and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves, and Rajendran and Ziegler. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.

Reviews

Required fields are marked *. Your email address will not be published.