陳靜枝臺灣大學：資訊管理學研究所傅光宇Fu, AllenAllenFu2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/54396在競爭激烈的商業環境中，企業必須透過對供應鏈整體的規劃，才能有效達到整體利潤最大、成本降低或是減少前置時間的目的，因此先進規劃排程中的主規劃排程即是在數個不同的設施與組織間進行協調規劃，以期達到整體供應鏈規劃最佳化的目的。 主規劃排程的問題通常使用線性規劃模式求解，當主規劃排程的問題加入固定成本考量之後，即必須以混合整數規劃模式求解，混合整數規劃模式求解的難度和所需時間遠遠大於線性規劃模式，並且混合整數規劃模式往往會因為變數和限制式過多而無法求解。 基於整數規劃的不可行性，本研究提出一啟發式演算法以解決主規劃排程的問題，除了滿足多最終產品的產品結構、複雜的供應鏈網路架構和多張訂單需求、多期與共用料的環境，並加入整備成本與時間的考量規劃整體供應鏈的生產與配送計畫。 本研究於整備成本與時間的重點研究包括考慮整備成本與時間之訂單排序法、生產路徑選擇法和時距微調法，並提出整備與變動成本平衡演算法(SVCB)和整備與變動成本循序演算法(SVCS)，分別針對兩個多目標模式進行求解，演算法主要流程首先轉換供應鏈網路架構；第二步利用子網路搜尋演算法，依照最終產品的不同，從供應鏈網路萃取出與該最終產品相關的供應鏈組織與路徑；第三步是決定訂單進行規劃的順序；第四步則是依據訂單排序的順序，來進行訂單規劃，直至所有訂單規劃完成。 本研究設計四個維度組合而成的二十四個情境測試，由於問題過於複雜導致整數規劃模式無法求解，因此以不考慮整備成本與時間的演算法作為比較基準，在絕大部分的情境中本研究之演算法皆能取得較佳的成本，並且能在短時間內得出規劃結果。Under a more and more competitive business environment, maximizing the profit, cutting down the cost, and reducing lead time should be the first prioritized goals and can be achieved by the integrated planning of an overall supply chain. In the supply chain management, “Master Planning” is the way to coordinate several organizations and facilities to achieve the efficiency and effectiveness of the overall supply chain. “Linear Programming” is usually used for solving problems related to “Master Planning”. Moreover, for master planning with fixed setup cost and time consideration, “Mixed Integer Programming” is adapted to solve such a problem. However, the complexity and computer solving time are much larger than a problem formulated as a “Linear Programming” model. Too many variables and constraints lead the problem to be unsolvable. For the infeasibility or unsolvability of the “Mixed Integer Programming” formulations, this study develops a heuristic algorithm to solve “Mater Planning” problem with fixed setup cost and time. Multiple final products structure, multiple discrete periods, multiple orders, complexed supply chain networks, and fixed setup cost and time are considered to determine a production and distribution plan of all orders on each node of the supply chain network. With fixed setup cost and time consideration, this study focuses on three main steps including order sorting algorithm, planning algorithm, and tuning algorithm. And the study proposes SVCB (Setup-Variable Cost Balance Algorithm) and SVCS (Setup-Variable Cost Sequence Algorithm) to solve two different multiple-objectives models. These algorithms are similar and composed of four steps: (1) Transform supply chain network structure into single-function based supply chain network structure. (2) Search relative organizations and paths to each final product. (3) Determine the planning sequence of orders. (4) Plan orders sequentially until each order is finished. This study designs 24 scenarios by four dimensions. Due to complexity of these scenarios,”Mixed Integer Programming” formulations of these scenarios are unsolvable. Therefore, the algorithm without fixed cost and time consideration is adapted to be the benchmark. In the most of scenarios, the algorithms of this study can attain better solutions in a short solving time.謝詞 一 論文摘要 二 THESIS ABSTRACT 三 目錄 四 圖目錄 六 表目錄 八 第一章 緒論 1 第一節、 研究動機 1 第二節、 研究目的 3 第三節、 研究範圍 4 第四節、 研究架構 5 第二章 文獻探討 7 第一節、 供應鏈管理之定義與研究範疇 7 第二節、 供應鏈管理問題分類、模式分類 8 第三節、 先進規劃排程與生產規劃排程之研究與方法論 11 第四節、 整備成本與時間之相關研究 15 第三章 問題描述與混合整數規劃 19 第一節、 問題描述 19 3-1.1、 產品結構 19 3-1.2、 成本結構 20 3-1.3、 規劃時距 21 3-1.4、 供應鏈網路架構 21 3-1.5、 訂單資訊 22 3-1.6、 整備成本與時間 22 第二節、 假設條件 24 第三節、 混合整數規劃模型 26 3-3.1、 混合整數規劃模型建立流程 26 3-3.2、 混合整數規劃模型 28 3-3.3、 複雜度分析 35 第四節、 混合整數規劃模式之限制 37 第四章 啟發式演算法 38 第一節、 演算法概述 38 第二節、 演算法主要流程 40 P1、轉換原始網路 40 P2、子網路搜尋演算法 44 第三節、 訂單排序演算法 47 I. Model_M1訂單排序演算法 47 II. Model_M2訂單排序演算法 50 第四節、 規劃排程演算法概述 52 第五節、 整備與變動成本平衡演算法(SVCB) 55 第六節、 整備與變動成本循序演算法(SVCS) 69 第七節、 時間(Time Complexity)複雜度分析 71 第五章、 系統說明與模式分析 73 第一節、 系統說明 73 5-1-1、 資料結構 73 5-1-2、 系統畫面與執行步驟 77 第二節、 情境設計與結果 80 5-2-1、 情境設計 80 5-2-2、 訂單資訊 81 5-2-3、 供應鏈與產品資訊 82 5-2-4、 規劃範例 90 5-2-5、 情境結果 103 第三節、 情境分析 107 第四節、 效率分析 113 5-4-1、 時間效率分析 114 5-4-2、 總成本分析 114 第五節、 實例測試 116 第六章、 結論 118 第一節、 總論 118 第二節、 應用 118 第三節、 未來研究方向 119 參考文獻 121 附錄A、情境分析之規劃結果 1232522192 bytesapplication/pdfen-US供應鏈管理主規劃排程啟發式演算法先進規劃排程多目標最佳化整備成本整備時間Supply Chain ManagementMaster PlanningHeuristic AlgorithmAdvanced Planning and SchedulingMultiple-goal OptimizationSetup CostSetup Timeotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54396/1/ntu-94-R92725033-1.pdf