請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68308
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 楊烽正 | |
dc.contributor.author | Zih-Jian Lin | en |
dc.contributor.author | 林子鑑 | zh_TW |
dc.date.accessioned | 2021-06-17T02:17:14Z | - |
dc.date.available | 2020-01-04 | |
dc.date.copyright | 2018-01-04 | |
dc.date.issued | 2017 | |
dc.date.submitted | 2017-09-11 | |
dc.identifier.citation | Bullnheimer, B., Hartl, R. F., and Strauss, C. (1997), “A new rank based version of the ant system: Acomputational study,” Working paper, University of Vienna, Austria.
Dorigo, M., and Gambardella, L. M. (1997), “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66. Garey, M., Graham, R., Johnson, D., and Yao, A. (1976), “Resource Constrained Scheduling as Generalized Bin Packing,” J. Comb. Theory, Ser. A 21. Goldberg, D. E., and Lingle, J. R. (1985), “Alleles, Loci and the TSP.” Proceedings of the First International Conference on Genetic Algorithms and Their Applications, 154–159. Holland, J.H. (1975), “Adaptation in Natural and Artificial System,” The University of Michigan Press. Stutzle, T., and Hoos, H. (1997), “The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,” In Proceedings of the Fourth International Conference on Evolutionary Computation. , IEEE Press, 308-313. Stutzle, T., and Hoos, H. (2000), “MAX-MIN Ant System,” Journal of Future Generation Computer Systems, 889-914. Scholl, A., Klein, R., and Jurgens, C. (1997), “ BISON: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem,” Computers & Operations Research 24, 627-645. Ugur, A., and Aydim, D. (2009), “An interactive simulation and analysis software for solving TSP using Ant Colony Optimization algorithms,” Advances in Engineering Software, Volume 40, Issue 5, May 2009, Pages 341-349 Yang, F., and Chou, Y. (2009), “Superior/Inferior Segment-Discriminated Ant System for combinatorial optimization problems,” Computers & Industrial Engineering, Volume 57, Issue 2, September 2009, Pages 475-495. 李仁富(2011),「仿頻寬限制資料傳輸之離散優化演算法」,臺灣大學工業工程學研究所學位論文2011年版,第1到60頁。 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/68308 | - |
dc.description.abstract | 本研究承襲一創新的萬用啟發式演算法「仿頻寬限制資料傳輸優化演算法」(Bandwidth Restricted Transmission-Simulated Optimization Algorithm, BRT),提出「優加劣減式仿頻寬限制資料傳輸優化演算法」(Segment-Discriminated Bandwidth Restricted Transmission-Simulated Optimization Algorithm, SD-BRT)。BRT模仿網路資料傳輸的特性,模擬訊息傳輸者傳輸訊息。傳輸者在頻寬資源有限的情況下,逐步選擇傳輸纜線建構一條完整的傳輸路徑。BRT模擬自然環境的劣化,使傳輸纜線在演化過程中老化毀損,並依照解代理人目標函數值的改善量決定添加或扣減各纜線的頻寬量。SD-BRT改良頻寬更新機制,比起原BRT能更精確地增添頻寬給較優的纜線且縮減較差的纜線。並以裝箱問題(Bin Packing Problem, BPP)與旅行推銷員問題(Traveling Salesman Problem, TSP)的標竿問題比較SD-BRT與原BRT性能的差異。此外本研究定義一個資源共享工作排程問題(Resource Shared Scheduling Problem, RSSP)。RSSP是實務上遇到的工廠生產排程問題。RSSP中,一個「工作」(Job)需透過一個可行的「機台」(Machine)執行一次加工。每一個工作加工時須在機台上安裝特定的「資源」(Resource),且需要有安裝時間。若後續的工作與前接的工作資源類型相同,則「資源共享」(Resource Shared),不須重覆安裝資源。本研究完備地定義RSSP,,並研擬RSSP的標竿問題產生器及標竿問題文字檔格式。最後規劃RSSP的SD-BRT求解模式。研究結果顯示,SD-BRT在求解BPP及TSP均可求得比原BRT更優或相同品質的解,且在求解更複雜的RSSP亦有不錯的表現。 | zh_TW |
dc.description.abstract | This research presents an innovative heuristic algorithm called “Segment-Discriminated Bandwidth Restricted Transmission-Simulated Optimization Algorithm” (SD-BRT) for solving discrete optimization problems. SD-BRT improves “Bandwidth Restricted Transmission-Simulated Optimization Algorithm”(original BRT).Like original BRT, SD-BRT imitates the behavior of data transmission over the network and simulates messengers transmit messages. Messengers select the communication links and constructive a complete route under the restriction of resources. The communication links are subject to operations of natural deterioration and enhancement/deduction bandwidth. SD-BRT improves original BRT in operations of enhancement/deduction bandwidth with Segment-Discriminated way. We develop SD-BRT solving system for Bin Packing Problem(BPP) and Traveling Salesman Problem(TSP) and compare results with original BRT.
Also, this research defines a scheduling problem called “Resource Shared Scheduling Problem”(RSSP). In RSSP, one “job” should be processed once by one “machine”. Before processes a job, the machine should setup a “resource” for the job. Every job has a “resource type”. If there are two jobs sequentially processed by the same machine and the two jobs has the same resource type. Then we call the two jobs “Resource Shared”, and the second job do not need to setup the resource. This research defines RSSP completely, and develop a SD-BRT solving system to solve RSSP. In solving BPP and JSP, the results prove that SD-BRT is better than original BRT. Also the results indicate that SD-BRT is capable for solving RSSP. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T02:17:14Z (GMT). No. of bitstreams: 1 ntu-106-R04546019-1.pdf: 2525777 bytes, checksum: 29b67986e0547d2c890cecd0b3718886 (MD5) Previous issue date: 2017 | en |
dc.description.tableofcontents | 口試委員審定書 i
致謝 ii 摘要 iii Abstract iv 目錄 vi 圖目錄 viii 表目錄 ix 第一章 緒論 1 1.1 研究動機 1 1.2 研究目的 2 1.3 研究流程 3 1.4 章節概要 4 第二章 文獻回顧 5 2.1 啟發式演算法 5 2.1.1 仿頻寬限制資料傳輸之離散優化演算法 5 2.1.2 蟻拓優化演算法 6 2.2 離散優化問題 7 2.2.1 旅行銷售員問題 8 2.2.2 裝箱問題 8 第三章 優加劣減式仿頻寬限制資料傳輸優化演算法 10 3.1 原始的仿頻寬限制資料傳輸優化演算法 10 3.2 仿頻寬限制資料傳輸優化演算法之改良 20 3.3 改良式仿頻寬限制資料傳輸優化演算法 21 3.3.1 傳輸者優劣判定作業 21 3.3.2 纜線優加劣減頻寬更新作業 23 3.3.3 頻寬重置作業 27 3.3.4 SD-BRT改良的演算程序 28 3.4 旅行推銷員問題的SD-BRT求解模式 32 3.5 裝箱問題的SD-BRT求解模式 34 3.6 小結 36 第四章 資源共享工作排程問題及SD-BRT求解模式 37 4.1 資源共享工作排程問題 37 4.2 RSSP標竿問題 43 4.3 RSSP標竿問題產生器 44 4.4 RSSP的SD-BRT求解模式 46 4.5 小結 62 第五章 數值範例測試與結果分析 63 5.1 SD-BRT求解軟體 63 5.2 SD-BRT求解旅行銷售員問題測試 65 5.3 SD-BRT求解裝箱問題測試 70 5.4 SD-BRT求解資源共享工作排程問題測試 74 第六章 結論與建議 80 6.1 結論 80 6.2 後續研究建議 81 參考文獻 82 附錄 RSSP標竿問題 84 | |
dc.language.iso | zh-TW | |
dc.title | 優加劣減式仿頻寬限制資料傳輸優化演算法 | zh_TW |
dc.title | Segment-Discriminated Bandwidth Restricted Transmission-Simulated Optimization Algorithm | en |
dc.type | Thesis | |
dc.date.schoolyear | 106-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 黃奎隆,蔡瑞煌,歐陽超 | |
dc.subject.keyword | 啟發式演算法,仿頻寬限制資料傳輸優化演算法,排程,旅行銷售員問題,裝箱問題, | zh_TW |
dc.subject.keyword | heuristic algorithm,bandwidth restricted transmission-simulated optimization algorithm,scheduling,traveling salesman problems,bin packing problems, | en |
dc.relation.page | 96 | |
dc.identifier.doi | 10.6342/NTU201704203 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2017-09-12 | |
dc.contributor.author-college | 工學院 | zh_TW |
dc.contributor.author-dept | 工業工程學研究所 | zh_TW |
顯示於系所單位: | 工業工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-106-1.pdf 目前未授權公開取用 | 2.47 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。