仿頻寬限制資料傳輸之離散優化演算法應用於零工式生產排程問題

Abstract

本研究承襲一創新的萬用啟發式演算法「仿頻寬限制資料傳輸優化演算法」(Bandwidth Restricted Transmission-Simulated Optimization Algorithm, BRT-S) ，提出「仿頻寬限制資料傳輸之離散優化演算法應用於零工式生產排程問題」(Bandwidth Restricted Transmission-Simulated Discrete Optimization Algorithm for Job Shop Scheduling Problem, BRT-S4JSP)。BRT-S模仿網際網路資料傳輸的特性，模擬訊息傳輸者傳輸訊息。訊息傳輸者在頻寬資源有限狀況下，逐步選擇傳輸線段，建構一條完整的傳輸路徑。BRT-S模擬自然環境的劣化，使傳輸線段在演化過程中老化損毀，並執行頻寬添加及扣減作業。在BRT-S的演算規劃下，規劃符合零工式生產排程問題(Job Shop Scheduling Problems, JSP)的演算流程。研究內容針對物件排序優化問題中的零工式生產排程問題建立BRT-S4JSP求解模式，開發BRT-S4JSP求解系統求解OR-library中的JSP標竿問題，並和其他萬用啟發式演算法比較求解結果。在求解JSP標竿問題中，BRT-S4JSP能在諸多問題中求得最佳解，且求得最小完工天數時的平均目標函數評估次數較其他萬用啟發式演算法少。BRT-S4JSP在相同的停止條件下求得品質比其他萬用啟發式演算法來的佳，也在目標函數評估次數花費上較為精簡，證明本研究所提出的BRT-S4JSP法是一個適合求解零工式生產排程問題的演算法。

This research presents a meta-heuristic algorithm called “Bandwidth Restricted Transmission-Simulated Discrete Optimization Algorithm for Job Shop Scheduling Problem” (BRT-S4JSP) for solving Job Shop Scheduling Problem (JSP). BRT-S imitates the behavior of data transmission in the network and simulates messengers transmit messages. Messengers select the communication links and constructive a complete route under the restriction of resources. BRT-S simulates that links are subject to operations of natural deterioration and enhancement/deduction/modulation. Based on the original BRT-S computational flow, BRT-S4JSP conducts the computational flow of JSP. BRT-S is designed for solving discrete optimization problems. We develop BRTSOS4JSP solving system for Job Shop Scheduling Problem through programming language. By using the benchmark of JSP from OR-library, we compare results with other meta-heuristic algorithm then verify the feasibility of BRT-S4JSP. In the example for JSP, BRT-S can obtain optimal solutions and use less objective function evolution than others. BRT-S4JSP can obtain better solutions under the same stop criteria. This research proves BRT-S4JSP is a good meta-heuristic algorithm for Job Shop Scheduling Problems.