| dc.contributor | 資管系 | |
| dc.creator (作者) | 陳春龍 | zh_TW |
| dc.date (日期) | 2015 | |
| dc.date.accessioned | 18-May-2017 10:58:58 (UTC+8) | - |
| dc.date.available | 18-May-2017 10:58:58 (UTC+8) | - |
| dc.date.issued (上傳時間) | 18-May-2017 10:58:58 (UTC+8) | - |
| dc.identifier.uri (URI) | http://nccur.lib.nccu.edu.tw/handle/140.119/109771 | - |
| dc.description.abstract (摘要) | 流程式排程問題（PFSP）是製造現場常見的問題。因為它在實務上的價值以及計算的複雜度，流程式排程問題長久以來都是學術界和產業界非常重視的問題。以總完成時間為目標的流程式排程問題（PFSP- makespan）是研究者最有興趣的問題之一。我從1993就開始該問題的研究，我的兩篇主要的論文分別刊登在EJOR (1995，在WOS資料庫中被引用118次) 和 C&IE (1996，在WOS資料庫中被引用66次)。2011年和2012年國科會計畫的研究成果也以分別刊登在IJAMT (2012), Soft Computing和Applied Soft Computing。2014年的國科會研究計畫則已開發一個比IGRIS 和 DDERLS（兩個到目前為止最好的演算法）為佳的啟發式演算法(BBLS)，因此求解PFSP-makespan，研究的成果最近已經被Soft Computing所接受（DOI10.1007/s00500-013-1199-z）。本研究計畫利用PFSPmakespan問題之解的區塊特性（Block）開發一個新的演算法（block-based local search, BBLS）。BBLS先利用NEHT產生一個起使解，設定其為起使期之週期最佳解(local best solution)。然後在每一週期（iteration），利用週期最佳解的區塊特性，產生有效的鄰近解(neighbor solutions)，再應用一個新的篩選方法（filtered local search）在這些鄰近解上，以產生新的週期最佳解，再重複下一週期的搜尋；篩選機制的主要目的是希望將搜尋的方向導引向尚未搜尋的區域。此外，如果搜尋陷入區域最佳解中（local optimum），我們也計畫開發一個逃離策略（jumpstrategy），幫助搜尋跳出區域最佳解。最後，我們會利用IGRIS和 DDERLS（兩個到目前為止最好的演算法）來評價BBLS的效能。 | |
| dc.description.abstract (摘要) | Permutation flow shop scheduling problem (PFSP) is a common problem in the manufacturing shop floor. Due to its value in the real-world and its computational complexity, it has received considerable attention in academia and in practitioners for years. PFSP with minimum makespan as the objective (PFSP-makespan) is one of the most studied NPhard scheduling problems; more than 1000 technical papers for solving PFSP-makespan can be found in Web of Science (WOS). I started conducting research in this field in 1994, and two of my notable works were published in European Journal of Operational Research (1995, cited 109 times in WOS) and Computers and Industrial Engineering (1996, cited 66 times in WOS). This proposal is a follow-up research of my NSC projects in 2011 and 2012 (100-2221-E-004-004 and 101-2221-E-004-004). The project in 2011 developed a novel metaheuristic (EDAACS) to solve PFSP-makespan, and the result of the project was published in International Journal of Advanced Manufacturing Technology (2012). The project in 2012 developed another metaheuristic (RDPSO) to solve PFSPmakespan, and the result of the project has recently beenaccepted for publication by Soft Computing(DOI10.1007/s00500-013-1199-z). This research utilizes the block property of the solution of PFSP-makespan to develop a new metaheuristic (block-based local search, BBLS) for solving PFSP-makespan. BBLS applies NEHT to generate an initial solution and set the solution be the local best solution. Then, in each iteration, BBLS utilizes the block property of the local best solution to efficiently generate promising neighbor solutions and applies a new filteredlocal search method to the generated neighbor solutions to update the local best solution. The purpose of the filtered local search is to filter the solution regions that have been reviewed and guides the search to new solution regions in order to keep the search from trapping into local optima. In addition, a new jump strategy will be developed to help the search escape if the search does become trappedat a local optimum. Computational experiments on the wellknown Taillard‘s benchmark data sets will be conducted to compare the performance of BBLS with that of IGRLS and DDERLS, the two most effective heuristics for PFSP-makespan up to now. | |
| dc.format.extent | 623632 bytes | - |
| dc.format.mimetype | application/pdf | - |
| dc.relation (關聯) | MOST 103-2221-E-004-002 | |
| dc.subject (關鍵詞) | 區塊特性; 流程式排程問題; 總完成時間; 啟發式演算法 | |
| dc.subject (關鍵詞) | Block; Metaheuristic; Permutation Flow Shop Scheduling; Makespan | |
| dc.title (題名) | 開發一個以區塊特性為基礎的啟發式演算法求解流程式排程問題 | zh_TW |
| dc.type (資料類型) | report | |
