Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19246
DC FieldValueLanguage
dc.contributor.advisor曾怜玉zh_TW
dc.contributor.advisorLin Yu Tsengen_US
dc.contributor.author張瑞炎zh_TW
dc.contributor.authorChang, Jui Yenen_US
dc.date2004zh_TW
dc.date.accessioned2014-06-06T07:06:24Z-
dc.date.available2014-06-06T07:06:24Z-
dc.identifier.urihttp://hdl.handle.net/11455/19246-
dc.description.abstract開放式工廠排程問題(open shop scheduling problem)為作業研究中典型的組合最佳化問題,此問題是NP-hard,本研究將在排程作業不可中斷(non-preemptive)的情況下,求總時程(makespan)最小化的解。 本研究整合基因演算法(Genetic Algorithms, GA)與區域搜尋法(Local Search)為基因區域搜尋法(Genetic Local Search Algorithm),並導入兩層式基因區域搜尋法(Two Layered Genetic Local Search Algorithm),先作全域性的搜尋,再作區域性搜尋,來解開放式工廠排程問題,並以Taillard與Brucker共一百一十二題的標準實例為本研究的測試標準,透過實驗証明兩層式基因區域搜尋法在解決開放式工廠排程問題上有很顯著的成效,以Taillard的標準實例而言,除了有一題解到目前已知最好的解之外,其餘全都達到目標最佳解,在Brucker的標準實例中,平均求解品質也不錯,其中更有一題突破上限值(Upper Bound),亦即比目前最好的解還好。 關鍵字:開放式工廠排程問題,基因演算法,區域搜尋法,兩層式基因區域搜尋法。zh_TW
dc.description.abstractThe open shop scheduling problem is an NP-hard combinational problem and has long attracted much attention. In this thesis, we propose a two layered genetic local search algorithm for this problem. The first layer acts as the global search and the second layer acts as the local search. We also study the neighborhood structure of a solution and design two kinds of effective local search methods. Combining the genetic algorithm with these local search methods results in our genetic local search algorithm. We test our method on Taillard's instances and Brucker's instances. On Taillard's instances, our method had found the optimal solutions for all instances except one of them. And for this exception, the solution found by our method is the same as the best solution found thus far. On Brucker's instances, the quality of solutions found is also good and our method had improved the upper bound of one instance. Key words: Open Shop Scheduling Problem; Genetic Algorithm; Local Search; Two Layered Genetic Local Search Algorithmen_US
dc.description.tableofcontents中文摘要 iii Abstract iv 目 錄 v 圖表目錄 vii 第一章 諸論 1 1.1研究背景與動機 1 1.1.1單程工件處理的排程問題 2 1.1.2多程工件處理的排程問題 2 1.1.3排程問題評估準則 3 1.1.4排程問題的解決方法 4 1.2研究目的 5 1.3研究步驟 5 1.4研究範圍與限制 6 1.4.1問題定義 6 1.4.2分離圖模型的數學表示法 6 1.5論文架構 7 第二章 文獻探討 8 2.1開放式工廠問題 8 2.2基因演算法 10 第三章 研究方法 13 3.1問題表示法 13 3.2基因演算法之基本元件 16 3.2.1基因編碼 16 3.2.2評估函數 19 3.2.3繁殖交配機制 20 3.2.4突變機制 24 3.2.5選擇機制 25 3.3區域搜尋法模型 26 3.3.1鄰域結構 26 3.3.1.1關鍵路徑結構 26 3.3.1.2平行部份排程結構 35 3.3.2區域搜尋演算法 36 3.3.2.1以關鍵路徑為基底之區域搜尋演算法 36 3.3.2.2以部份排程為基底之區域搜尋法 37 3.4兩層式基因區域搜尋法模型 38 3.4.1兩層式基因區域搜尋法的概念 38 3.4.2兩層式基因區域搜尋演算法 40 第四章 實例驗證 42 第五章 結論與未來研究方向 48 參考文獻 49zh_TW
dc.language.isozh_TWzh_TW
dc.publisher資訊科學研究所zh_TW
dc.subjectOpen Shop Scheduling Problemen_US
dc.subject開放式工廠排程問題zh_TW
dc.subjectGenetic Algorithmen_US
dc.subjectLocal Searchen_US
dc.subjectTwo Layered Genetic Local Search Algorithmen_US
dc.subject基因演算法zh_TW
dc.subject區域搜尋法zh_TW
dc.subject兩層式基因區域搜尋法zh_TW
dc.title解開放式工廠排程問題之兩層式基因區域搜尋法zh_TW
dc.typeThesis and Dissertationzh_TW
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.languageiso639-1zh_TW-
item.grantfulltextnone-
item.cerifentitytypePublications-
item.openairetypeThesis and Dissertation-
item.fulltextno fulltext-
Appears in Collections:資訊科學與工程學系所
Show simple item record
 

Google ScholarTM

Check


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