- 學位論文
供應鏈網路中考量替代料之主規劃排程演算法
A Heuristic Master Planning Algorithm for Supply Chain Network with Substitutionality
摘要
在競爭激烈、變動快速的企業環境下，整合供應鏈成員之進貨、生產、配送時程，發揮整體效益之最大化，為重要之供應鏈管理議題。由於未來環境之變動性，產品結構不再是固定不可變動之設計，而是可以根據實際生產情形、產能限制、存貨狀況等，以替代料取代原始物料而動態改變、具彈性之產品結構。規劃具替代料性質生產排程為重要但複雜之議題，本研究即為考量替代料之主規劃排程研究，屬先進規劃排程中，整合一個月以上至一年內之採購、生產與配銷計畫，並考量物料供給與產能限制，作最佳化之研究。 本研究考量多個最終產品之產品結構，具有替代料及共同料之特性，並考量其替代優先次序與替代成本；期望在有限產能之供應鏈網路架構環境下，規劃訂單需求，選擇適當的期間交由適當的廠商生產處理，以達到最小化訂單延遲成本、最小化替代料使用情形與最小化生產處理、運輸及存貨成本。 供應鏈網路問題一般採用線性規劃與混合整數規劃建立模型並求取最佳解，本研究亦提出一混合整數規劃模型以描述問題，然而當供應鏈網路或訂單規模增大導致問題複雜度增加時，混合整數規劃模型之限制式與變數將快速成長，使模型需要花費大量時間求解或完全無法求得解答；因此本研究提出動態搜尋替代產品結構之啟發性規劃排程演算法，可有效率的完成規劃，並隨時反映訂單處理狀態與產能使用情形。 在啟發性演算法中，首先進行訂單排序，找出最佳分配產能之訂單執行順序後，再一一對訂單進行規劃排程。在對每一張訂單規劃排程時，先尋找原始產品結構下之最小成本廠商組合，若無法滿足需求，則進行調整網路架構以尋找次佳廠商組合；當原始產品結構之產能無法滿足需求時，則依照存貨、產能情形，動態決定替代產品結構。動態決定替代產品結構之方法有二：(1)產品結構分層加入替代料法，此法可保留大部分原產品結構之特性；(2)瓶頸物料填補替代料法，此法則偵測產能不足之物料，有效率的填補產品結構缺漏。最後，本研究建立一規劃排程系統，並進行情境分析之實例討論，以驗證本演算法之效能與效率。
並列摘要
In competitive and dynamic business environment, it is significant to integrate and coordinate procurement, production and distribution of members in the supply chain. Owing to the variation of the future, product structure can not be fixed or unchangeable but a flexible bill-of-materials (BOM) which can change dynamically using substitutions according to the actual capacity and inventory condition. Planning with substitutions is an important, however complex, issue in supply chain management. Considering substitutionality, this study focuses on “Master Planning” of “Advanced Planning and Scheduling”, which is to synchronize the materials along the complete supply chain and to support the decisions during one month to one year on effective utilization of production, transportation and capacity. This study considers the product structures for multiple final products with substitutionality and commonality. Substitute priority and cost are also taken into consideration. With limited capacity in supply chain, this study plans all demand and minimizes the delay cost, penalty of using substitutions and sum of the production cost, holding cost, transportation cost, and inventory cost. In previous study, “Mixed Integer Programming” is a popular way to solve the supply chain problem. In this study, a MIP model is also proposed. However, while the problem gets more complex, MIP model becomes unacceptable in time or unsolved due to the time and resource required. Therefore, this study proposes a heuristic algorithm named “Dynamically Searching Substitute BOM Algorithm, DSSBA” to solve the problem efficiently and satisfy the real business environment needs. In DSSBA, demand orders are sorted based on the requirement of final product, due date, capacity, etc. Then, orders are planned in sequence one by one. The production plan for each order is to find the minimum cost production tree and the available capacity using original BOM. If the demand is not fulfilled completely, the supply chain network structure is modified and then a new minimum cost production tree will be found. If the demand can not be fulfilled using original BOM, substitute BOMs will be used. There are two algorithms to search substitute BOMs: one is “Adding Substitutions by Level”, which retains most of materials of original BOM; the other is “Filling Bottlenecks with Substitutions”, which detects insufficient materials and then complements them. To show the effectiveness and efficiency of DSSBA, a prototype is constructed and scenario analysis is illustrated.