期刊
INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY
卷 39, 期 7-8, 页码 796-807出版社
SPRINGER LONDON LTD
DOI: 10.1007/s00170-007-1252-0
关键词
No-idle flow shop; Makespan; Discrete particle swarm optimization; Insert neighborhood; Speed-up method; Local search
资金
- National Science Foundation of China [60774082]
- National 863 Hi-Tech RD Plan [2007AA04Z155]
- SRF
- Postdoctoral Science Foundation of China [20070410791]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据