先進規劃排程中考慮公平性與切單限制之主規劃排程演算法

A Heuristic Master Planning Algorithm for Supply Chain with Fairness and Order Splitting

吳宏祐(Hung-Yu Wu)

指導教授 ： 陳靜枝

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2005年)

https://doi.org/10.6342/NTU.2005.00170

摘要

本研究所欲解決的問題屬於先進規劃排程中的主規劃排程部份，考慮完整的供應鏈網路架構與多個最終產品的產品結構，並考量需求產能分配之公平性議題與切單限制，以間斷時間模式解決多目標下多訂單多期之主規劃排程問題。本研究提出兩個三階段多目標模式，模式一(Model_D_F_T)首先滿足最小化延遲成本、再滿足最大化公平性、最後滿足最小化供應鏈總成本。模式二(Model_F_D_T)首先滿足最大化公平性、再滿足最小化延遲成本、最後滿足最小化供應鏈總成本。
本研究中之公平性議題則是透過最大化於交期時可滿足最小需求數量之訂單數為目標，以期望於交期前能儘量滿足顧客部份需求。本研究中之切單情境包含顧客面與供應鏈內成員面之切單，前者代表顧客於交期起每收到一次貨均發生一固定成本，後者代表供應鏈內成員於該期有收到某上游節點的物品時，則將發生一固定成本。上述兩項固定切單成本將包含於供應鏈總成本中，並予以最小化。
本研究若以混合整數規劃模式進行求解時，會存在變數相當多且複雜、解題時間過長、無法保證一定有解且無解時無法得知原因等問題，但為了解決此類主規劃排程問題，本研究提出一啟發式演算法進行求解，此演算法能有效率地求出近似最佳解，並且在某些情形下求得之解甚至是最佳解本身。
本研究的啟發式演算法步驟包含前置作業，目的是將原始供應鏈網路拆解為單一功能節點、各最終產品之子網路搜尋、成本轉換與網路成本設定等，之後進行初始訂單排序演算法及第一階段規劃排程，目的為指定各訂單在考量各期產能狀況與共用料的使用下所預先試排出的數量，若第一階段規劃排程執行後仍有未滿足的訂單，需再執行二次訂單排序演算法並逐單進行第二階段規劃排程，以滿足所有剩餘需求，最後再使用微調演算法檢視是否有減少切單成本的機會並進行排程結果修正。
本演算法於無延遲訂單之8個情境中的表現與求解線性規劃軟體CPLEX結果相同，而於32個有延遲訂單的情境中，本演算法在公平性與切單成本的表現上於大部分的情境中均優於未考量公平性與切單限制之啟發式演算法。而在時間效能上，本演算法能有效地處理規模龐大的問題，如可在165分鐘內解出3個最終產品之2000張訂單的問題。

關鍵字

供應鏈管理 ； 主規劃排程 ； 啟發式演算法 ； 先進規劃排程 ； 多目標最佳化 ； 公平性 ； 切單

並列摘要

This study focuses on solving the problem related to the master planning of “Advanced planning and scheduling”. Given a supply chain network providing multiple final products, the fairness of treating different customers by splitting demands and the effectiveness of choosing the right vendors at the right time are all major issues considered in this study under the capacitated assumption.
Two multiple-goal MIP models are proposed: Model_D_F_T, which minimizes the delay cost first, followed by maximizing the fairness among different orders, and finally minimizes the total cost; and Model_F_D_T, which maximizes fairness among different orders first, followed by maximizing the delay cost, and finally minimizes the total cost.
The fairness goal in this study is defined as the number of orders whose minimum requirement is fulfilled at or before their corresponding due days. In additions, two kinds of order splitting situations are considered in the study: customer-side and supply members of supply chain as well as two kinds of fixed splitting cost included in the total cost of supply chain which are simultaneously optimized.
It may take a lot of computing resource to solve the problems formulated as a MIP model if feasible solutions exist. However, the causes of infeasibility cannot be identified when the problems have no feasible solution. In order to improve the efficiency and effectiveness of the solution process, a heuristic algorithm, called Heuristic Order Splitting and Fairness Algorithm or HOSFA, is proposed.
HOSFA first prepares the needed information for transforming all nodes in the network to the single function, searching all the sub-networks for different final products, and setting up the cost on each nodes of the supply chain network. It then sorts the orders by an initial order sorting algorithm proposed in this study, assigns the quota to all orders by considering the constraints of capacity, and finally plans the orders according to the allocated quota. If some orders are not fulfilled completely after the first phase planning, the second phase planning is evoked. It sorts the unfulfilled orders and plans them one-by-one by using the unused capacities or delaying orders if necessary. When all the orders are finally fulfilled, an adjustment algorithm is applied to find a better combination of vendors’ capacity usage.
HOSFA results in the same optimal solution as the one provided by CPLEX of ILOG in 8 scenarios with no delay orders. In 32 scenarios with delayed orders, HOSFA outperforms Lin’s algorithm in terms of fairness and splitting cost for most of the scenarios. HOSFA is very efficient in solving the large scale master planning problem. It takes only 165 minutes to solve a large scale master planning problem with 3 final product and 2000 orders.

並列關鍵字

Supply Chain Management ； Master Planning ； Heuristic Algorithm ； Advanced planning and scheduling ； Multiple-goal Optimization ； fairness ； order splitting

參考文獻

[1] 李和璞，「考量替代路徑下，上下游多廠整合生產規劃問題之研究」，台灣大學商學研究所碩士論文，民國93年。

[2] 林仲輝，「考慮共用料之供應鏈網路主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國93年。

[8] Bazaraa, M. S., H. D. Sherali, and C. M. Shetty, “Nonlinear Programming: Theory and Algorithms, 2nd Ed,” Wiley, 1993.

[9] Chopra S and P. Meindl, “Supply Chain Management: Strategy, Planning, and Operation,” Prentice-Hall,Inc , New Jersey, 2001.

[10] Eglese, R. W. “Simulated Annealing: A Tool for Operational Research,” European Journal of Operational Research, Vol. 46, Iss. 3, Jun 15, 1990, pp.271—281.