應用禁忌搜尋法求解供應鏈中在具車容限制下整合產品製造與成品配送兩階段問題

Abstract

由於及時化(just-in-time)觀念的普及，使得越來越多供應鏈中的企業採用接單式生產(make-to-order)的方式滿足顧客需求，同時專注於降低存貨水準以提升其競爭力。此種現象造成了產品製造與成品配送作業的密切互動，同時增加了研究此類問題的必要性。傳統方法分別最佳化產品製造與成品配送階段的作業並無法最佳化供應鏈的整體利益。因此本研究探討一整合供應鏈中產品製造與成品配送之訂單排程問題，以非等效平行機台(unrelated parallel machine)模擬產品製造階段，並將成品配送階段以考慮車容限制的車輛途程問題(vehicle routing problem, VRP)模擬。訂單之完成時間定義為產品從開始製造至送達顧客手上所花費的時間，以總加權後訂單完成時間為系統的績效指標。在此類績效指標之下，整合產品製造與成品配送兩階段之問題的複雜度為未定多項式難度(NP-Hard)，故本研究設計一禁忌搜尋法(tabu search algorithm)求解整合產品製造與成品配送之兩階段問題，並以電腦模擬方式產生一系列測試問題，由測試結果得知，本研究所設計之演算法可在合理的時間內求得品質佳的近似解，可供相關研究與產業參考。

Due to widespread just-in-time concept, more and more enterprises have chosen make-to-order business model to satisfy customers’ demand and focus on reducing their inventory level in order to be competitive. This phenomenon has not only increased the interaction between production and distribution but also raised the practicability of integrating these two stages. Traditional approaches consider production and distribution separately and sequentially may not maximize the total profits in supply chains. Therefore, this research studies an integrated production and distribution scheduling problems at the individual job level. The production stage is modeled by an unrelated parallel machines scheduling problem and distribution stage is modeled by a capacitated vehicle routing problem. The job completion time is defined as the time when it is delivered to its customer. The objective is to minimize total job weighted completion times. The complexity of this problem is NP-hard. We designed a tabu search algorithm to find near-optimal solutions to this problem. Computational analysis based on computer generated problems shows the stability and effectiveness of the proposed approach.