標題: 應用混合式禁忌搜尋法於整合生產與配送之排程問題
Tabu Search Heuristic Based on Simulated Annealing for an Integrated Production and Distribution Scheduling Problem
作者: 薛理維
Li-Wei Hsueh
張永佳
Yung-Chia Chang
工業工程與管理學系
關鍵字: 非等效平行機台;車輛途程問題;禁忌搜尋法;模擬退火法;unrelated parallel machine scheduling;vehicle routing problem;tabu search;simulated annealing
公開日期: 2007
摘要: 企業為了提昇競爭力而縮短訂單送達顧客的前置時間,以及顧客對於產品的多樣化需求下,企業的生產型態由存貨生產(make to stock)轉為接單式生產(make to order),使得原本作為生產與配送階段間緩衝的存貨逐漸的減少,造成了生產與配送作業間的互動更加密切,同時也增加了研究如何整合此兩階段問題的必要性。本研究所探討整合生產與配送的排程問題,以非等效平行機台(unrelated parallel machine)模擬生產階段,以具有車容限制的車輛途程問題(vehicle routing problem)模擬配送階段,並且以最佳化顧客服務水準與配送成本為此問題的目標。本研究提出一混合式禁忌搜尋法求解此問題。此演算法以禁忌搜尋法為基礎,在其中利用模擬退火法的機制收集解品質較好的精英名單,作為強化禁忌搜尋法的策略,當禁忌搜尋法所找到的解無法改進系統最佳解時,即將精英名單的解作為新迭代的起始解,使得演算法能從品質較佳的解重新搜尋,以提昇禁忌搜尋法的效率與求解品質。經過測試問題顯示本研究的演算法能在合理的時間內求得品質不錯的最佳近似解,最後並驗證了整合生產與配送方式的求解品質是優於分開考量的順序式方式,平均相對差距為43.26%,因此本研究的結果也可以作為相關產業在整合生產與配送排程上的參考,以達到最大化整體利潤的目的。
Enterprises enhance their competition strength by shortening the delivery time to customers. However, since customers’ demand changes rapidly, many enterprises have change their business model from make-to-stock to make-to-order. Consequently, the stocks which are used to buffer between production and distribution is reduced which results in a closer interaction between production and distribution and increases the essentiality of integrating the production and distribution stages. This search studies an integrated production and distribution scheduling problem. The production stage is modeled by an unrelated parallel machines scheduling problem and the distribution stage is modeled by a capacitated vehicle routing problem. The objective is to optimize customer service level and distribution cost simultaneously. A hybrid tabu search heuristic is developed to find near-optimal solutions to this problem. The proposed heuristic is based on tabu search heuristic in which simulated annealing heuristic is used as an intensification strategy to collect a list of elite solutions. When a current solution cannot improve the optimal solution of the system in one generation, the best solution in the elite list is drawn to be used as a new initial solution of the next generation. Computational analysis based on computer generated problems shows the proposed approach can find the near-optimal solutions in reasonable computational time. This study also compares the performance between solving the production and distribution stages integratedly and solving them sequentially. The results of the computational experiments show that the integrated approach can significantly reduce the total cost of the two stages than the sequential approach and the average gap is 43.26%.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009533523
http://hdl.handle.net/11536/39153
Appears in Collections:Thesis