Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/36589
標題: A hybrid genetic local search algorithm for the permutation flowshop scheduling problem
作者: Tseng, L.Y.
曾怜玉
Lin, Y.T.
關鍵字: Genetic algorithm
Local search
Hybrid genetic algorithm
Flowshop
scheduling
Total flowtime
Makespan
particle swarm optimization
ant-colony algorithms
sequencing problem
heuristic algorithm
m-machine
flowtime minimization
n-job
c-i
makespan
time
期刊/報告no:: European Journal of Operational Research, Volume 198, Issue 1, Page(s) 84-92.
摘要: Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA's capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion. it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature. (C) 2008 Elsevier B.V. All rights reserved.
URI: http://hdl.handle.net/11455/36589
ISSN: 0377-2217
文章連結: http://dx.doi.org/10.1016/j.ejor.2008.08.023
Appears in Collections:資訊網路與多媒體研究所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.