應用變數產生法於求解整合生產與配送之排程問題

Abstract

現今顧客需求的多元化且喜好變動快速，而接單式生產(make to order)為企業為了滿足需求不確定的客製化市場而採用的模式，以減少存貨並快速反應需求。而存貨的減少與前置時間的縮短使得產品製造與成品配送間的作業必須密切配合才能有效率地提供讓顧客滿意的服務，進而增加了整合探討此兩階段作業的必要性。因此本研究探討整合生產與配送兩階段的排程問題，以等效平行機台(identical parallel machine)模擬產品製造階段，以車輛途程問題(vehicle routing problem, VRP)模擬成品配送階段，並將此問題視為一個以整體最佳化為目標的系統問題，以加權後訂單完成時間所轉換而成的成本加上運送成本之總和為系統績效指標。本研究先將整合生產與配送兩階段排程問題以整數規劃的方式表現，再以變數產生法搭配分枝界限法來求解此問題，以找到系統的最佳解為目的，並提供此類問題的下限值(lower bound)以供後續研究之參考。經由測試結果顯示，本研究所提出的演算法其下限值與最佳解的平均差距約為1.29%，顯示此演算法可以成功的提供品質還不錯的下限值，以做為啟發式演算法或其它求解方法在衡量求解品質時的一個參考和比較依據。

More and more enterprises have chosen to adopt make-to-order business model in order to satisfy diversified and rapidly-changing customer demand. In such a business model, enterprises have to focus on reducing their inventory level in order to be competitive. The reduction of inventory level and short lead time forces the operation between production and distribution to cooperate closely thus increases the practicability of integrating the production and distribution stages. This research studies an integrated production and distribution scheduling problem in which the production stage is modeled by an identical parallel machine scheduling problem and the distribution stage is modeled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a joint production and distribution schedule such that the weighted summation of total job weighted completion time and total job delivering cost is minimized. The studied problem was first formulated as an integer program, and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve most of the test problems to optimality. Besides, the average gap between the optimal solutions and the lower bounds are no more than 1.29% for these test problems.