陳靜枝臺灣大學：資訊管理學研究所林仲輝Lin, Zhong-HuiZhong-HuiLin2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/54199本研究針對包含多個最終成品的供應鏈網路圖形，且多個最終產品之間有共用性物料的使用。本演算法具有兩個主要目標(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.1 Introduction 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation and Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Research Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Research Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Literature Review 10 2.1 Reviews on Supply Chain Management . . . . . . . . . . . . . . . . . . . 10 2.1.1 Concept-Oriented Research . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Model-Oriented Research . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Reviews on Advanced Planning and Scheduling . . . . . . . . . . . . . . 11 2.3 Reviews on Component Commonality . . . . . . . . . . . . . . . . . . . . 13 3 Problem Description and Linear Programming Model 16 3.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1.1 Bill of Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.2 Supply Chain Network . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.3 Order Information . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 Linear Programming Model . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.1 Finding Production Tree . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3.3 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.4 Objective Function . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.5 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Limitations of Linear Programming Model . . . . . . . . . . . . . . . . . 29 4 Heuristic Algorithm 30 4.1 Master Planning Main Procedure . . . . . . . . . . . . . . . . . . . . . . 30 4.2 Preliminary Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.1 Single Function Node Con‾rmation . . . . . . . . . . . . . . . . . 31 4.2.2 Capacity and Cost Transformation . . . . . . . . . . . . . . . . . 32 4.2.3 Network Cost Setting . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 De‾nitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.1 Planning Time Bucket . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.2 Plan Starting Time Bucket . . . . . . . . . . . . . . . . . . . . . . 33 4.3.3 Order Due Time Bucket . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.4 Final Available Time Bucket . . . . . . . . . . . . . . . . . . . . . 33 4.3.5 MLBCP: Minimum Lead time Bucket of Common Part . . . . . . 34 4.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.4.1 Greedy Capacity Allotment Algorithm . . . . . . . . . . . . . . . 34 4.4.2 Average Capacity Allotment Algorithm . . . . . . . . . . . . . . . 39 4.4.3 Proportional Capacity Allotment Algorithm . . . . . . . . . . . . 43 4.5 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5.1 Greedy Capacity Allotment Algorithm . . . . . . . . . . . . . . . 51 4.5.2 Average Capacity Allotment Algorithm . . . . . . . . . . . . . . . 53 4.5.3 Proportional Capacity Allotment Algorithm . . . . . . . . . . . . 53 5 System Illustration and Model Analysis 67 5.1 System Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.1.1 Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.1.2 System Prototype . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Scenarios used in Computational Analysis . . . . . . . . . . . . . . . . . 72 5.3 Scenarios : Basic Information . . . . . . . . . . . . . . . . . . . . . . . . 74 5.3.1 BOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.3.2 Network Topology . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.3.3 Production Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.4 Computational Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.4.1 Loose Capacity, Large Demand, High Commonality . . . . . . . . 74 5.4.2 Loose Capacity, Large Demand, Low Commonality . . . . . . . . 76 5.4.3 Loose Capacity, Small Demand, High Commonality . . . . . . . . 82 5.4.4 Loose Capacity, Small Demand, Low Commonality . . . . . . . . 83 5.4.5 Tight Capacity, Small Demand, Low Commonality . . . . . . . . 84 5.4.6 Tight Capacity, Small Demand, High Commonality . . . . . . . . 86 5.4.7 Tight Capacity, Large Demand, Low Commonality . . . . . . . . 87 5.4.8 Tight Capacity, Large Demand, High Commonality . . . . . . . . 89 5.4.9 Insu±cient Capacity, Small Demand, Low Commonality . . . . . 90 5.4.10 Insu±cient Capacity, Small Demand, High Commonality . . . . . 92 5.4.11 Insu±cient Capacity, Large Demand, Low Commonality . . . . . 94 5.4.12 Insu±cient Capacity, Large Demand, High Commonality . . . . . 96 5.5 Algorithm E±ciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.6 Testing on a Real-World Case . . . . . . . . . . . . . . . . . . . . . . . . 99 6 Conclusions 102 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Appendices 104 A Results of Scenarios 1051402806 bytesapplication/pdfen-US供應鏈規劃排程共用料產品結構主規劃排程演算法master planningcommon componentsheuristic algorithmadvanced planning and schedulingsupply chain management[SDGs]SDG11otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54199/1/ntu-93-R91725050-1.pdf