Journal
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY
Volume 39, Issue 7-8, Pages 796-807Publisher
SPRINGER LONDON LTD
DOI: 10.1007/s00170-007-1252-0
Keywords
No-idle flow shop; Makespan; Discrete particle swarm optimization; Insert neighborhood; Speed-up method; Local search
Funding
- National Science Foundation of China [60774082]
- National 863 Hi-Tech RD Plan [2007AA04Z155]
- SRF
- Postdoctoral Science Foundation of China [20070410791]
Ask authors/readers for more resources
A novel hybrid discrete particle swarm optimization (HDPSO) algorithm is proposed in this paper to solve the no-idle permutation flow shop scheduling problems with the criterion to minimize the maximum completion time (makespan). Firstly, two simple approaches are presented to calculate the makespan of a job permutation. Secondly, a speed-up method is proposed to evaluate the whole insert neighborhood of a job permutation with (n-1)(2) neighbors in time O(mn(2)), where n and m denote the number of jobs and machines, respectively. Thirdly, a discrete particle swarm optimization (DPSO) algorithm based on permutation representation and a local search algorithm based on the insert neighborhood are fused to enhance the searching ability and to balance the exploration and exploitation. Then, computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is concluded that the proposed HDPSO algorithm is not only superior to two recently published heuristics, the improved greedy (IG) heuristic and Kalczynski-Kamburowski (KK) heuristic, in terms of searching quality, but also superior to the single DPSO algorithm and the PSO algorithm with variable neighborhood search (PSOvns) in terms of searching quality, robustness and efficiency.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available