Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19103
標題: 以基因區域搜尋演算法解決流程型工廠排程問題
A Genetic Local Search Algorithm for Flowshop Scheduling Problems
作者: 林亞泰 
Lin, Ya-Tai 
關鍵字: Genetic algorithm;基因演算法;local search;genetic local search;flowshop scheduling;no-wait flowshop scheduling;makespan;total flowtime;區域搜尋演算法;基因區域搜尋演算法;流程型工廠排程問題
出版社: 資訊科學與工程學系
摘要: 
流程型工廠排程問題(Flowshop Scheduling Problem, FSSP)是一個著名的排程問題。一直以來,有關流程型工廠排程問題的研究,大多以最小化makespan為目標。近年來,以最小化total flowtime為目標的流程型工廠排程問題愈來愈受到學者的重視並加以研究。此外,對映到一些特殊製程,例如:鋼鐵、食品加工與化學工業的no-wait流程型工廠排程問題(No-wait Flowshop Scheduling Problem)之研究也日益增加。
本研究提出基因區域搜尋演算法(Genetic Local Search Algorithm, GLS)來解決這些問題,此演算法以基因演算法做為全域搜尋並且依據基因演算法的收斂程度,採用兩種強弱不同的區域搜尋演算法:Insertion Search(IS)與Insertion Search with Cut-and-Repair (ISCR),不但改進了解的品質更增加了搜尋的效率。實驗的結果顯示,本研究所提出的基因區域搜尋演算法的效能很好。在以最小化makespan為目標的流程型工廠排程問題上,與近幾年發表的三種方法相較,在相同的測試題組(benckmark problem)上,所提出的GLS得到較好的效能與解的品質。應用在以最小化total flowtime為目標的流程型工廠排程問題上,在短時間的測試(short-term test)中,與近幾年發表的期刊論文相比,在相同的90個效能測試題目中,所提出的GLS更新了66個目前已知的最佳解。而在長時間的測試(long-term)中,則是更新了全部共20題的效能測試題目。另外,在以最小化makespan為目標的no-wait流程型工廠排程問題上,本研究所提出的GLS表現也相當優秀。在短時間的測試(short-term test)中,實驗於Carlier所提出的8個測試題目時,所提出的GLS可以找到全部的最佳解,實驗於Reeves所提出的21個效能測試題目時,與最近發表的期刊論文相比,我們的方法更新了5個目前最佳解而其餘的16個題目中也有14題找到目前最佳解。

The flowshop scheduling problem (FSSP) is a very well-known scheduling problem. Over the past years, the researches on FSSP were aiming at the criterion of makespan minimization. Recently, the FSSP to total flowtime minimization has drawn more researchers' attention. Besides, researches on no-wait flowshop scheduling problem reflecting to many industries like steel production, food processing, and chemical industry have been increased.
In this dissertation, a genetic local search algorithm is proposed to solve the FSSP with both makespan and total flowtime criterion, and also the no-wait FSSP with makespan criterion. 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 IS is for searching a small neighborhood while the ISCR is for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the genetic algorithm(GA)'s capability of intensification. The experiment results show a great advantage of combining two local search methods. The performance of the proposed genetic local search algorithm is very competitive. For the FSSP with the total flowtime criterion, it improved 66 solutions out of the 90 current best solutions reported in the literature for short-term search, and it also improved all the 20 current best solutions reported in the literature for long-term search. For the FSSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature. When applying the proposed genetic local search algorithm to the no-wait FSSP with makespan criterion, in short-term search, the proposed algorithm found the optimal solutions for all eight Carlier's benchmark problems. Also, for Reeves' benchmark problems, the proposed algorithm improved five out of the twenty-one current best solutions reported in the literature and achieved the current best solutions for fourteen of the remaining sixteen problems.
URI: http://hdl.handle.net/11455/19103
Appears in Collections:資訊科學與工程學系所

Show full item record
 

Google ScholarTM

Check


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