考慮共用料之供應鏈網路主規劃排程演算法

A Heuristic Master Planning Algorithm for Supply Chain Network

林仲輝(Zhong-Hui Lin)

指導教授 ： 陳靜枝

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

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

摘要

本研究針對包含多個最終成品的供應鏈網路圖形，且多個最終產品之間有共用性物料的使用。本演算法具有兩個主要目標(1).在考慮成品之產品架構、以及有限產能限制下，規劃與安排未來所有的訂單，選擇適當時間交由適當的廠商生產，希望達到最小生產與運送成本，以及最少訂單的延遲交貨時間，達到供應鏈最佳化的效果。(2).在考慮共用性物料的使用下，針對共用性資源的分配提出考慮公平性的做法。
本研究的方法主要分為五大步驟，首先將具有不同生產程序之節點分離，執行產能初始化，第二步驟則是將所有產能轉換為以最終產品為產能單位。第三步驟，根據使用者需求選擇適合訂單排序方式與參數，第四步驟，根據訂單所要求之最終產品從網路結構中取出有效的子網路，第五步驟,再經過訂單排序後便可執行核心的三大演算法，貪婪演算法、平均分配演算法、以及比例分配演算法，每筆訂單依序規劃排程。
在對每一張訂單規劃排程時，找出最小成本之廠商組合，然後尋找與安排適當生產量，當此廠商組合無法滿足需求時，調整供應鏈網路圖形以尋找次佳之廠商組合，不斷重複上述步驟直到訂單需求滿足或供應鏈已無任何產能幫助生產為止。當交貨時距限制下需求仍未滿足，延遲一個交貨時距，重複上述之方法，直到訂單需求完全滿足為止。至於產能分配的方式，貪婪演算法會依序將每一張訂單的需求滿足為止；平均分配演算法會將所有會使用同一期同一資源的訂單需求作一個平均的產能分配。最後，比例分配演算法會將所有會使用同一期同一資源的訂單需求依據需求比例分配。

關鍵字

供應鏈 ； 規劃排程 ； 共用料 ； 產品結構 ； 主規劃排程演算法

並列摘要

This study proposes a heuristic algorithm to solve a
general master-planning problem of a supply chain network with
multiple final products. The objective of this planning algorithm
is (1)To minimize the processing, transportation , and inventory
costs under the constraints of the capacity limits of all the
nodes in a given supply chain network graph and the quantity and
due day requirements of all the orders. (2)To lower the impact of
fairness problem of greedy capacity allocation.

This study assumed that multi-finished items are made and shipped
on the given supply chain which results in common parts on common
nodes for different finished items. Three different ways are
proposed to solve the sharing capacity problem caused by common
components: greedy, average capacity, and proportional capacity.

All the three algorithms are basically composed of five steps.
(1). They split nodes in the supply chain network graph by
different functions the nodes perform, and set the initial
capacities of all nodes. (2).They transform the capacity units
shown on the graph, based on the unit of the final finished
product. (3).They sort all the orders by adopting a rule-based
sorting method to decide the scheduling sequence.(4).They extract
sub-networks from original networks according to final product
structure of orders. (5).Finally, for each order, the algorithms
find a minimum cost production tree under the constraints of the
order's due day. They then compute the maximum available capacity
of this combination and arranges the suitable quantities of
production and transportation. If the demand cannot be fulfilled
before the due day, the order will have to be postponed. Repeating
the process above until the demand is completely fulfilled. The
difference is average capacity and proportional capacity are under
constraints of capacity using quota.

The three algorithms result in the same optimal solution as the
one by "Linear Programming" in eight different dimensions of
scenarios when no delayed orders present. In the four cases with
delayed orders, the three orders will still work out a
near-optimum solution in a shorter time.

並列關鍵字

master planning ； common components ； heuristic algorithm ； advanced planning and scheduling ； supply chain management

參考文獻

[1] Arntzen, B. C., G. G. Brown, T. P. Harrison, and L. L. Trafton,“Global Supply Chain Management at DEC,” Interface, Vol. 25, No. 1, 1995, pp.69—92 .

[2] Baker, K.R., M.J. Magazine, and H.L.W. Nuttle, “The Effect of Commonality on Safety Stocks in a Simple Inventory Model,” Management Science, Vol. 32, 1986, pp.982—988 .

[3] Christopher, M.,“Logistics and Supply Chain Management：strategies for reducing cost and improving service, 2nd ed,” London et al, Inc., 1998, pp.7.

[4] Cohen, M. A. and H. L. Lee,“ Strategic Analysis of Integrated Production-Distribution Systems：Models and Methods,” Operations Research, Vol. 36, No.2, 1988, pp.216—228 .

[5] Collier, D.A., “The Measurement and Operating Benefits of Component Part Commonality,” Decision Science, Vol. 16, 1981, pp.85—96 .