陳靜枝Chern, Ching-Chin臺灣大學:資訊管理學研究所李錫濤Lei, Seak-TouSeak-TouLei2010-05-052018-06-292010-05-052018-06-292008U0001-1407200815544300http://ntur.lib.ntu.edu.tw//handle/246246/179846在全球供應鏈管理的議題中，最大化整體利益是所有供應鏈成員的共同目標。然而在現今的供應鏈架構中，錯綜複雜的生產環境將會增加供應鏈管理與規劃的困難度，同時存在需求分配的公平性、產品結構間存在共用料與替代料，以及考量產品回收機制的供應鏈網路架構更讓規劃者難以處理。本研究屬於先進規劃排程中，同時考量多個最終產品、規劃多期、有多張需求、產品存在共用料和替代料、需求分配之公平性以及回收機制，作最佳化主規劃排程。 本研究所討論的目標有六個，分別是最小化延遲成本、最大化公平性、最小化回收規費、最小化替代成本、最小化替代優先次序，以及最小化總製造、配送、存貨、運輸與需求切割成本。本研究分有兩個模式，兩者先滿足前兩個目標，在模式一中其餘四個目標可任意依序進行最佳化；模式二中其餘四個目標可設定不同的權重同時進行最佳化。本研究將先以混合整數線性規劃模型求解，但遇到規模更大的問題時，將會耗費大量時間求解或無法求得解答，因此本研究提出一套以基因演算法為基礎的啟發式演算法(GAMPA)來解決。 本研究啟發式演算法之主要流程為：調整原始供應鏈網路為不包含迴圈的架構、並對各個最終產品擷取子網路與成本轉換；需求排序方面使用基因演算法的方式產生多種不同的需求排序，並以染色體表示之，在規劃排程結束前，依照規劃模式的不同逐一比較其規劃結果，挑選出最佳的一組解答；規劃者亦可設定終止演算法的兩個參數，分別是所需規劃的染色體數目和同一組染色體連續多少次獲得最佳規劃結果的次數；在每一組染色體下，將針對其需求順序逐一為每張需求進行規劃排程，並使用隨機產生生產樹的方式決定其生產路徑，第一步先決定其產品結構，在產能充足時皆使用原始產品結構，當遇到產能不足時才開放替代料並決定其替代料之使用情形。第二步為決定產品組成物料之供應商或製造商。第三步為針對所選取的供應商和製造商連接其上下游廠商，並得出一條完整的生產路徑。每張需求以這種方式進行規劃排程，並依照規劃者輸入欲嘗試規劃的次數，最後依照模式的不同逐一比較成本，並挑選出最佳的規劃結果。For a global supply chain, maximizing the benefit of the entire supply chain is the objective of all the members involved in supply chain operations. This study focuses on solving the master planning problem for supply chains by considering product structures with multiple final products using substitutions, common components, and recycling processes and recycled components. Such problems address the difficulties involved in synchronizing manufacturing processes and transporting of materials, semi-finished products, final products, and recycling parts along a supply chain and facilitate decision-making related to the effective and efficient use of production, recycling, and transportation capacities over periods ranging from one month to one year. The priorities and costs of substitution are also taken into consideration. When integrating a recycling process into a supply chain operation, the product structure is changed from a tree configuration to a loop configuration and the supply chain structure is changed from an open loop to a closed loop. This study considers six different goals in the planning process: minimizing delay cost, maximizing fairness, minimizing recycle penalty, minimizing substitution cost, minimizing substitution priority, and minimizing the cost of production, processing, holding, transportation and demand splitting. Mixed Integer Programming is a popular way to solve supply chain master planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. Therefore, this study proposes a heuristic algorithm, called the genetic algorithm based heuristic master planning algorithm (GAMPA), to solve the supply chain master planning problem efficiently and effectively. GAMPA first transforms the closed-loop supply chain into an open-loop supply chain prone to planning and searching the sub-networks for each final product. GAMPA then uses a genetic algorithm based demand sorting approach to determine the sequence of demands. The sequence of demands is represented by chromosome, and different chromosomes are generated for planning using rule-based and random rules. At the end of planning, GAMPA selects the chromosome generating the best planning result according to the priority of the goals. GAMPA plans each demand sequentially according to the chromosome, and find a production tree randomly. GAMPA tries different production trees for each demand and select the best planning result at the end. To show the effectiveness and efficiency of GAMPA, a prototype was constructed and tested to demonstrate the power of GAMPA using complexity and computational analysis.目錄錄 一目錄 三目錄 五一章 緒論 1一節 研究動機 1二節 研究目的 4三節 研究範圍 6四節 研究架構 8二章 文獻探討 10一節 供應鏈與供應鏈管理之定義 10二節 供應鏈管理之研究範疇與模式分類 11-2-1 供應鏈管理之研究範疇 11-2-2 供應鏈管理之模式分類 12三節 先進規劃排程 14四節 主規劃排程研究 16五節 規劃排程之演算法介紹 18-5-1 線性規劃與混合整數規劃 18Linear and Mixed Integer Programming) 18-5-2 拉氏釋限法 (Lagrangian Relaxation Method) 19-5-3 基因演算法 (Genetic Algorithm) 19-5-4 限制規劃法 (Constraint Programming) 20-5-5 啟發式演算法 (Heuristic Algorithm) 21三章 問題描述與混合整數線性規劃模型 23一節 問題描述 23-1-1 產品結構 24-1-2 供應鏈網路結構 28-1-3 規劃時距 32-1-4 需求資訊 33-1-5 需求切割與公平性 34-1-6 製造商回收規費 35二節 假設條件 36三節 混合整數線性規劃模型 39-3-1 混合整數線性規劃模型之變數 39-3-2 混合整數線性規劃模型之限制式 44-3-3 混合整數線性規劃模型之多目標函式 49-3-4 複雜度分析 52四節 混合整數線性規劃模型之限制 54四章 啟發式演算法 56一節 演算法主要流程 56二節 演算法之前置作業 58-2-1 調整供應鏈網路架構 58-2-2 拆解網路成單一功能節點 60-2-3 依最終產品之結構建構子網路 60-2-4 轉換並設定網路成本 63三節 需求排序演算法 63四節 啟發式規劃排程演算法 73Genetic Algorithm based Master Planning Algorithm) 73五節 生產樹生成之演算法 80六節 判斷是否能避免回收規費之演算法 85七節 演算法在滾動式排程的應用 93八節 演算法之複雜度分析 93五章 系統說明與模式分析 96一節 規劃排程系統說明 96-1-1 資料結構 96-1-2 系統畫面與執行步驟 103二節 演算法與混合整數線性規劃模型情境設計 107-2-1 情境設計之維度 107-2-2 情境分析之各項資訊 109三節 規劃範例 117四節 情境結果分析 127-4-1 產能分析 132-4-2 公平性分析 133-4-3 目標回收率分析 135-4-4 替代料分析 137-4-5 維度交叉分析 138-4-6 規劃時間分析 142-4-7 需求排序和系統參數分析 144五節 演算法效率分析 149-5-1 時間效率分析 149-5-2 總規劃成本分析 150六節 演算法之優勢和偏離最佳解之分析 152七節 真實案例測試 154六章 結論 158一節 總論 158二節 未來研究方向 160 考 文 獻 161錄A 情境分析之規劃結果 164目錄1-1 三個目標之間的衝突 31-2 研究架構流程圖 92-1 供應鏈成員和流程 112-2 供應鏈整合模式之種類 122-3 供應鏈模式 132-4 先進規劃排程之模組架構 152-5 考慮回收機制之先進規劃排程之模組架構 163-1 產品結構資訊：製造(前段製造) 243-2 產品結構資訊(含替代資訊)：製造(前段製造) 253-3 產品結構資訊：回收(後段回收) 263-4 產品結構資訊：替代後改變之回收產品結構_P5 273-5 產品結構資訊：替代後改變之回收產品結構_P6 283-6 供應鏈網路架構 313-7 供應鏈網路架構符號詳細說明 323-8 規劃時距與各供應鏈成員產能使用狀況示意圖 333-9 需求切割示意圖 343-10 供應鏈網路節點與連結個數示意圖 524-1 啟發式演算法主要流程 584-2 調整後之供應鏈網路架構 594-3 P5之子網路架構 614-4 P6之子網路架構 624-5 需求排序演算法流程 644-6 染色體編碼 644-7 Partial Rule-Based排序結果之染色體表示方式 704-8 突變範例 714-9 交配範例 724-10 啟發式規劃排程演算法之流程 744-11 最終產品P5隨機產生的生產樹 794-12 隨機產生生產樹之流程 804-13 最終產品P5的產品結構 834-14 最終產品P5的最終隨機產生的生產樹 854-15 判斷是否能避免回收規費之流程 865-1 啟發式演算法系統畫面-初始化介面 1045-2 啟發式演算法系統畫面-總規劃結果 1055-3 啟發式演算法系統畫面-詳細規劃結果一 1065-4 啟發式演算法系統畫面-詳細規劃結果二 1065-5 情境設計中所使用之供應鏈網路架構 1095-6 不存在替代料之產品製造和回收結構 1125-7 有替代料之產品製造和回收結構(主要回收料無替代料) 1125-8 有替代料之產品製造和回收結構(主要回收料有替代料) 1135-9 替代料之替代成本資料 1145-10 規劃範例之生產樹圖示一 1195-11 規劃範例之生產樹圖示二 1205-12 規劃範例之生產樹圖示三 1225-13 最終產品P5沒有替代料之所有生產樹 1485-14 時間效率分析 1505-15 總規劃成本分析 1515-16 真實案例之產品結構：前段製造 1545-17 真實案例之產品結構：後段回收 1555-18 真實案例-筆記型電腦X某一生產路徑 155目錄3-1 各變數在最複雜情況下之總數量 533-2 各限制式在最複雜情況下之總數量 544-1 需求資訊範例 694-2 Partial Rule-Based排序後的結果 694-3 規劃排程結果 704-4 模式一之評量比較結果 704-5 模式二之評量比較結果 714-6 可行的生產樹範例 794-7 不可行的生產樹範例 804-8 最終產品P5的隨機選取物料結果1 834-9 最終產品P5的隨機選取物料結果2 834-10 最終產品P5的隨機選取使用節點結果 844-11 最終產品P5的隨機選取的上游節點 844-12 最終產品P5的隨機選取的下游節點 844-13 最終產品P5的使用時距 924-14 最終產品P5的最終使用時距 935-1 網路節點主檔 975-2 網路連結主檔 975-3 產能集合主檔 985-4 產品主檔 985-5 製造之產品結構主檔 985-6 回收之產品結構主檔 995-7 產品回收率主檔 995-8 需求主檔 995-9 產品替代主檔 1005-10 節點替代成本主檔 1005-11 產能分配結果 1005-12 回收物料產能使用結果 1015-13 使用回收物料製造情形 1015-14 染色體之規劃結果 1025-15 需求規劃結果 1025-16 情境設計各維度因子 1075-17 情境設計表 1085-18 供應鏈網路節點資訊 1105-19 供應鏈網路連結資訊 1105-20 需求基本資訊 1145-21 高公平性之情境 1155-22 最終產品目標回收率資訊 1155-23 製造節點回收規費資訊 1165-24 情境中各系統參數之預設值 1165-25 規劃範例之需求資訊 1175-26 規劃範例之系統參數資訊 1175-27 規劃範例之規劃排程次序和數量 1185-28 規劃範例之產能使用情形一 1195-29 規劃範例之產能使用情形二 1205-30 規劃範例之規劃結果比較情形一 1215-31 規劃範例之產能使用情形三 1215-32 規劃範例之產能使用情形四 1225-33 規劃範例之規劃結果比較情形二 1235-34 規劃範例之產能使用情形五 1235-35 規劃範例之產能使用情形六 1245-36 規劃範例之規劃結果比較情形三 1245-37 規劃範例之產能使用情形七 1255-38 規劃範例之產能使用情形八 1255-39 規劃範例之規劃結果比較情形四 1265-40 規劃範例之產能使用情形九 1265-41 規劃排程結果比較 1275-42 情境分析實驗結果 1295-43 總規劃成本平均差異 1315-44 情境分析-產能分析1 1335-45 情境分析-產能分析2 1335-46 情境分析-公平性分析1 1355-47 情境分析-公平性分析2 1355-48 情境分析-目標回收率分析1 1365-49 情境分析-目標回收率分析2 1365-50 情境分析-替代料分析1 1385-51 情境分析-替代料分析2 1385-52 交叉分析-情境4 1395-53 交叉分析-情境5、6 1395-54 交叉分析-情境10 1405-55 交叉分析-情境11、12、17、18 1405-56 交叉分析-情境30、36 1415-57 交叉分析-高目標回收率vs替代料 1425-58 情境分析-規劃時間分析 1425-59 ILOG CPLEX之限制式與變數個數 1445-60 需求排序分析 1465-61 成本差異分析 1465-62 時間效率分析 1495-63 總規劃成本分析 1505-64 其餘規劃成本 1515-65 真實案例之成本資訊 1565-66 真實案例之系統參數設定 1575-67 真實案例之規劃成本比較 157A-1 情境1需求規劃結果－變動成本部分 164A-2 情境1需求規劃結果－固定成本部分 164A-3 情境2需求規劃結果－變動成本部分 165A-4 情境2需求規劃結果－固定成本部分 165A-5 情境3需求規劃結果－變動成本部分 165A-6 情境3需求規劃結果－固定成本部分 165A-7 情境4需求規劃結果－變動成本部分 166A-8 情境4需求規劃結果－固定成本部分 166A-9 情境4需求規劃結果－使用回收料部分 166A-10 情境5需求規劃結果－變動成本部分 167A-11 情境5需求規劃結果－固定成本部分 167A-12 情境5需求規劃結果－使用回收料部分 167A-13 情境6需求規劃結果－變動成本部分 168A-14 情境6需求規劃結果－固定成本部分 168A-15 情境6需求規劃結果－使用回收料部分 168A-16 情境7需求規劃結果－變動成本部分 169A-17 情境7需求規劃結果－固定成本部分 169A-18 情境8需求規劃結果－變動成本部分 169A-19 情境8需求規劃結果－固定成本部分 170A-20 情境9需求規劃結果－變動成本部分 170A-21 情境9需求規劃結果－固定成本部分 170A-22 情境10需求規劃結果－變動成本部分 171A-23 情境10需求規劃結果－固定成本部分 171A-24 情境10需求規劃結果－使用回收料部分 171A-25 情境11需求規劃結果－變動成本部分 172A-26 情境11需求規劃結果－固定成本部分 172A-27 情境11需求規劃結果－使用回收料部分 172A-28 情境12需求規劃結果－變動成本部分 173A-29 情境12需求規劃結果－固定成本部分 173A-30 情境12需求規劃結果－使用回收料部分 173A-31 情境13需求規劃結果－變動成本部分 174A-32 情境13需求規劃結果－固定成本部分 174A-33 情境14需求規劃結果－變動成本部分 174A-34 情境14需求規劃結果－固定成本部分 175A-35 情境15需求規劃結果－變動成本部分 175A-36 情境15需求規劃結果－固定成本部分 175A-37 情境16需求規劃結果－變動成本部分 176A-38 情境16需求規劃結果－固定成本部分 176A-39 情境16需求規劃結果－使用回收料部分 176A-40 情境17需求規劃結果－變動成本部分 177A-41 情境17需求規劃結果－固定成本部分 177A-42 情境17需求規劃結果－使用回收料部分 177A-43 情境18需求規劃結果－變動成本部分 178A-44 情境18需求規劃結果－固定成本部分 178A-45 情境18需求規劃結果－使用回收料部分 178A-46 情境19需求規劃結果－變動成本部分 179A-47 情境19需求規劃結果－固定成本部分 179A-48 情境20需求規劃結果－變動成本部分 180A-49 情境20需求規劃結果－固定成本部分 180A-50 情境21需求規劃結果－變動成本部分 181A-51 情境21需求規劃結果－固定成本部分 181A-52 情境22需求規劃結果－變動成本部分 182A-53 情境22需求規劃結果－固定成本部分 182A-54 情境22需求規劃結果－使用回收料部分 183A-55 情境23需求規劃結果－變動成本部分 183A-56 情境23需求規劃結果－固定成本部分 184A-57 情境23需求規劃結果－使用回收料部分 184A-58 情境24需求規劃結果－變動成本部分 184A-59 情境24需求規劃結果－固定成本部分 185A-60 情境24需求規劃結果－使用回收料部分 185A-61 情境25需求規劃結果－變動成本部分 186A-62 情境25需求規劃結果－固定成本部分 186A-63 情境26需求規劃結果－變動成本部分 187A-64 情境26需求規劃結果－固定成本部分 187A-65 情境27需求規劃結果－變動成本部分 188A-66 情境27需求規劃結果－固定成本部分 188A-67 情境28需求規劃結果－變動成本部分 189A-68 情境28需求規劃結果－固定成本部分 190A-69 情境28需求規劃結果－使用回收料部分 190A-70 情境29需求規劃結果－變動成本部分 190A-71 情境29需求規劃結果－固定成本部分 191A-72 情境29需求規劃結果－使用回收料部分 191A-73 情境30需求規劃結果－變動成本部分 192A-74 情境30需求規劃結果－固定成本部分 193A-75 情境30需求規劃結果－使用回收料部分 193A-76 情境31需求規劃結果－變動成本部分 193A-77 情境31需求規劃結果－固定成本部分 194A-78 情境32需求規劃結果－變動成本部分 194A-79 情境32需求規劃結果－固定成本部分 195A-80 情境33需求規劃結果－變動成本部分 195A-81 情境33需求規劃結果－固定成本部分 196A-82 情境34需求規劃結果－變動成本部分 196A-83 情境34需求規劃結果－固定成本部分 197A-84 情境34需求規劃結果－使用回收料部分 197A-85 情境35需求規劃結果－變動成本部分 198A-86 情境35需求規劃結果－固定成本部分 199A-87 情境35需求規劃結果－使用回收料部分 199A-88 情境36需求規劃結果－變動成本部分 199A-89 情境36需求規劃結果－固定成本部分 200A-90 情境36需求規劃結果－使用回收料部分 200application/pdf1804313 bytesapplication/pdfen-US供應鏈管理先進規劃排程主規劃排程啟發式演算法多目標最佳化公平性替代料回收流程回收規費Supply Chain ManagementAdvanced Planning and SchedulingMaster PlanningHeuristic AlgorithmMultiple-goal OptimizationFairnessSubstitutionsRecycle ProcessRecycle Penalty[SDGs]SDG11http://ntur.lib.ntu.edu.tw/bitstream/246246/179846/1/ntu-97-R95725019-1.pdf