優加劣減式仿頻寬限制資料傳輸優化演算法

本研究承襲一創新的萬用啟發式演算法「仿頻寬限制資料傳輸優化演算法」(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亦有不錯的表現。

關鍵字

啟發式演算法；仿頻寬限制資料傳輸優化演算法；排程；旅行銷售員問題；裝箱問題

並列摘要

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.

並列關鍵字

heuristic algorithm ； bandwidth restricted transmission-simulated optimization algorithm ； scheduling ； traveling salesman problems ； bin packing problems

參考文獻

李仁富(2011)，「仿頻寬限制資料傳輸之離散優化演算法」，臺灣大學工業工程學研究所學位論文2011年版，第1到60頁。

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.

Holland, J.H. (1975), “Adaptation in Natural and Artificial System,” The University of Michigan Press.

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.

國際替代計量

優加劣減式仿頻寬限制資料傳輸優化演算法

全文下載

主題瀏覽