陳靜枝Chern, Ching-Chin臺灣大學:資訊管理學研究所陳昌佑Chen, Chang-YouChang-YouChen2010-05-052018-06-292010-05-052018-06-292008U0001-1407200815155200http://ntur.lib.ntu.edu.tw//handle/246246/179843在現今競爭激烈的環境中，企業必須整合供應鏈各成員，方能使整體利潤最大化。在供應鏈實際運作上，為了經濟效益的考量而產生出製造、訂購及運輸批量的概念，然而供應鏈各成員間的批量政策各自不同，容易造成彼此的存貨累積、整備活動無法相互配合。本研究即為考慮固定批量下之主規劃排程研究，以達到整體供應鏈最佳化為目的。研究屬於先進規劃排程中之主規劃排程，規劃供應鏈中期的採購、製造與配銷計畫。本研究考慮多產品、多層級、有產能限制、有整備成本下之靜態批量中，固定批量下最佳化批量數之生產排程問題，以間斷時間模式規劃多張需求。研究針對此類規劃問題提出一多目標模型：以最小化總需求延遲成本以滿足顧客需求為第一優先目標，再以最小化其他總成本為次要目標。在本研究中，各節點間的批量關係為一重要因子。不成倍數關係的批量會影響各節點的存貨以及整備成本，進而影響最後的總成本。於考量批量以及整備成本，本研究之規劃問題若用最佳演算法求解將屬於一混合整數線性規劃模型。在問題規模龐大時，解題時間將大幅提昇，且不能保證有解以及無解時沒有任何資訊可找出其原因。此外，規劃環境變動時，必須重新建構模型。因此本研究提出一啟發性演算法，使本研究問題能在合理時間內，得到一趨近最佳解之可行解決方案。研究啟發性演算法流程為：進行規劃排程之前置作業，接著針對各項目標做需求排序，完成後將依此排序結果規劃每張需求。進行規劃時，會針對該需求之最終產品每一個可能的生產樹，當作第一生產樹規劃，若不足則隨機選取下一棵生產樹直到全部規劃完畢。最後選擇單位規劃成本最低者為該需求最終規劃的結果。在規劃時，會嘗試往前搜尋可用的時距，以降低整備成本。在規劃完該張需求後，也會嘗試往後搜尋可提前的需求，以充分發揮批量的經濟效益。後，本研究實做出此規劃排程系統，並進行情境分析與實務案例測試，以驗證本演算法確實可行且具高效率性。In a competitive business environment, the partners in a supply chain take responsibility for different tasks, and depending on the tasks it performs, each partner organization generates its own costs (e.g., production, transportation, or inventory). It is in the best interest of the whole supply chain to meet all demands by allotting the resources in the most efficient way, thus minimizing the supply chain’s overall costs. Partners of a supply chain prefer to produce or transport mass quantities of products in order to benefit from economies of scale. However, inconsistent lot-sizing policies taken by different partners of a supply chain may result in high inventory cost and huge setup cost. Considering multiple final products, multi-level BOM, setup cost, and capacitated fixed lot size, this study focuses on solving master planning problems of an “Advanced Planning and Scheduling” system, which is designed to determine a production and distribution plan of a supply chain network to fulfill all demands. he objective of this study is to produce optimal production plans that will satisfy all demands while minimizing delay penalties and minimizing the costs of setup, materials, production, processing, transportation, and inventory holding—all while respecting the fixed lot-sizing policies, the capacity limitations, and demand deadlines of everyone involved in a given supply chain network. In this study, lot-sizing policy taken by each member of a supply chain is the most important factor that affects the cost of setup and inventory holding. ixed Integer Programming (MIP) is a popular way to solve this type of master planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. In response to the difficulty of solving the planning problem, this study proposes a heuristic algorithm, called the Lot-Sizing Master Planning Algorithm or LSMPA. First, LSMPA groups and sorts demands according to the required products and the imposed due dates. Then, the LSMPA plans the demands individually, choosing the best planning production tree from all possible production trees and using BSATA (Backward Searching Available Time Algorithm) to lower the setup cost and FSADA (Forward Searching Available Demand Algorithm) to optimize lot-sizing economic effect. To show the effectiveness and efficiency of the heuristic algorithm, a prototype was constructed and tested, using complexity and computational analyses to demonstrate the power of the algorithm.目錄錄 一目錄 三目錄 四一章 緒論 1一節 研究動機 1二節 研究目的 4三節 研究範圍 4四節 研究架構 6二章 文獻探討 8一節 供應鏈管理之定義 8二節 供應鏈管理之問題與研究模式分類 9三節 先進規劃排程 13四節 先進規劃排程與批量問題之方法論 15五節 整備成本與時間之相關研究 19六節 批量問題之相關研究 20三章 問題描述與混合整數規劃 24一節 問題描述 24. 產品結構 24. 批量架構 25. 規劃時距 25. 整備成本與時間 25. 成本結構 27. 供應鏈網路架構 28. 需求資訊 30二節 假設條件 30三節 混合整數規劃模型 32. 混合整數規劃模型建立流程 32. 混合整數規劃模型 34. 複雜度分析 41四節 混合整數規劃模型之限制 44四章 啟發式演算法 46一節 演算法概述 46二節 演算法主要流程 47三節 批量主規劃排程演算法之前置作業 48. 多產出節點拆解 48. 子網路搜尋 50. 轉換網路設定成本及產能 50四節 需求排序演算法 51五節 批量主規劃排程演算法(LSMPA) 54. 批量主規劃排程演算法概述 55. 批量主規劃排程演算法詳細流程 57. P.4 往前搜尋可用時距演算法(BSATA) 60. P.8 往後搜尋可提前需求演算法(FSADA) 66六節 批量主規劃排程演算法之滾動排程應用 67七節 複雜度分析 68五章 系統說明與模式分析 70一節 規劃排程系統說明 70. 資料結構 70. 系統畫面 75二節 情境設計 76. 情境設計之維度 76. 供應鏈網路與產品及需求資訊 79三節 規劃範例 80四節 情境結果分析 90. 批量關係分析 92. 整備成本分析 94. 產能分析 96. 因子交互作用分析 98. 規劃時間分析 101. 結論與管理意涵 103五節 效率分析 104. 時間效率分析 104. 總規劃成本分析 105六節 批量主規劃排程演算法與最佳解差異分析 106七節 實例測試 107六章 結論 111一節 總論 111二節 應用 112三節 未來研究方向 113考文獻 114錄A、情境分析之規劃結果 117amp;#8195;目錄 1-1：供應鏈管理之屋 2 1-2：研究架構 7 2-1：供應鏈網路 8 2-2：供應鏈管理問題之分類 10 2-3：供應鏈整合模式型態 12 2-4：供應鏈管理模式之分類 13 2-5：先進規劃排程模組 15 2-6：同時具有一、三特性之示意圖 20 3-1：產品結構表(Bill Of Material)資訊 25 3-2：整備成本與批量整備成本 26 3-3：整備時間與批量整備時間 26 3-4：拆解內部生產功能節點示意圖 29 3-5：供應鏈網路 30 3-6：混合整數規劃模型建立流程 33 3-7：圖3-5中的生產樹 33 3-8：最複雜情況下之供應鏈網路節點與連結示意圖 42 4-1：具有多產出的D2節點 48 4-2：拆解成單一產出的D2、D3節點 48 4-3：經拆解後之供應鏈網路 49 4-4：批量主規劃排程演算法流程圖 57 4-5：往前搜尋可用時距演算法流程圖 60 4-6：PO6生產樹圖 64 4-7：往後搜尋可提前需求演算法流程圖 66 5-1：系統畫面-前置作業 75 5-2：系統畫面-規劃排程 76 5-3：規劃範例──PO5-T1示意圖 81 5-4：規劃範例──PO5-T2示意圖 83 5-5：規劃範例──PO6-T1示意圖 87 5-6：情境分析──因子交互作用分析圖 （批量關係v.s.整備成本） 99 5-7：情境分析──因子交互作用分析圖 （批量關係v.s.產能狀況） 100 5-8：情境分析──因子交互作用分析圖 （整備成本v.s.產能狀況） 101 5-9：時間效率分析 105 5-10：總規劃成本分析 106 5-11：實例測試之產品結構表 108 5-12：實例測試之產品X生產樹示意圖 109 6-1：虛擬運輸節點之設計圖 113 目錄 2 1：批量問題相關研究 23 4-1：產能對照表 49 4-2：子網路搜尋結果 50 4-3：未排序需求資訊範例 51 4-4：最終產品之生產樹數目範例 52 4-5：需求分組結果 52 4-6：需求組內排序結果 53 4-7：需求組間排序結果 53 4-8：FECP與FECP2說明範例 55 4-9：時距調整前之規劃排程 65 4-10：時距調整後之規劃排程 65 5-1：網路節點主檔 71 5-2：網路連結主檔 71 5-3：產能集合主檔 72 5-4：產品主檔 72 5-5：產品結構主檔 72 5-6：需求主檔 73 5-7：產能使用記錄 73 5-8：整備活動記錄 74 5-9：存貨使用記錄 74 5-10：需求規劃記錄 74 5-11：情境維度表 77 5-12：情境設計表 78 5-13：情境分析──需求資訊 80 5-14：規劃範例──需求資訊 80 5-15：規劃範例──需求排序結果 81 5-16：規劃範例──PO5-T1規劃前產能與存貨狀態 81 5-17：規劃範例──PO5-T1規劃後產能與存貨狀態 82 5-18：規劃範例──PO5-T2規劃前產能與存貨狀態 83 5-19：規劃範例──PO5-T2規劃後產能與存貨狀態 84 5-20：規劃範例──PO5-T2規劃後產能與存貨狀態2 86 5-21：規劃範例──PO6-T1規劃前產能與存貨狀態 87 5-22：規劃範例──PO6-T1規劃後產能與存貨狀態 88 5-23：規劃範例──PO6-T1規劃後產能與存貨狀態2 89 5-24：規劃範例──規劃排程結果比較 90 5-25：情境分析實驗結果 91 5-26：情境分析──批量關係分析（與ILOG比較） 92 5-27：情境分析──批量關係分析（LSMPA內部比較） 93 5-28：情境分析──整備成本分析（與ILOG比較） 94 5-29：情境分析──整備成本分析（LSMPA內部比較） 95 5-30：情境分析──產能狀況分析（與ILOG比較） 96 5-31：情境分析──產能狀況分析（LSMPA內部比較） 97 5-32：情境分析──因子交互作用分析 （批量關係v.s.整備成本） 98 5-33：情境分析──因子交互作用分析 （批量關係v.s.產能狀況） 99 5-34：情境分析──因子交互作用分析 （整備成本v.s.產能狀況） 100 5-35：情境分析­規劃時間分析（單位：秒） 102 5-36：情境分析­ILOG限制式與變數個數 103 5-37：情境分析­時間效率分析（單位：秒） 104 5-38：情境分析­規劃總成本分析 105 5-39：實例測試­規劃排程結果（成本單位：萬） 109 A-1 情境1 (NLL)需求規劃記錄 117 A-2 情境2 (PLL)需求規劃記錄 117 A-3 情境3 (NML)需求規劃記錄 118 A-4 情境4 (PML)需求規劃記錄 118 A-5 情境5 (NHL)需求規劃記錄 118 A-6 情境6 (PHL)需求規劃記錄 119 A-7 情境7 (NL1)需求規劃記錄 119 A-8 情境8 (PL1)需求規劃記錄 119 A-9 情境9 (NM1)需求規劃記錄 120 A-10 情境10 (PM1)需求規劃記錄 120 A-11 情境11 (NH1)需求規劃記錄 120 A-12 情境12 (PH1)需求規劃記錄 121 A-13 情境13 (NLB)需求規劃記錄 121 A-14 情境14 (PLB)需求規劃記錄 122 A-15 情境15 (NMB)需求規劃記錄 122 A-16 情境16 (PMB)需求規劃記錄 122 A-17 情境17 (NHB)需求規劃記錄 123 A-18 情境18 (PHB)需求規劃記錄 123 A-19 情境19 (NL3)需求規劃記錄 124 A-20 情境20 (PL3)需求規劃記錄 124 A-21 情境21 (NM3)需求規劃記錄 125 A-22 情境22 (PM3)需求規劃記錄 125 A-23 情境23 (NH3)需求規劃記錄 125 A-24 情境24 (PH3)需求規劃記錄 126application/pdf826170 bytesapplication/pdfen-US供應鏈管理先進規劃排程主規劃排程啟發式演算法多目標最佳化批量整備成本整備時間Supply Chain ManagementAdvanced Planning and SchedulingMaster PlanningHeuristic AlgorithmMultiple-goal OptimizationLot SizeSetup CostSetup Time[SDGs]SDG11http://ntur.lib.ntu.edu.tw/bitstream/246246/179843/1/ntu-97-R95725006-1.pdf