整合性供應鏈網路之主規劃排程演算法： 同時考量公平性、替代料與回收機制

A Heuristic Master Planning Algorithm Considering Fairness, Substitution, and Recycling for an Integrated Supply Chain Network

李錫濤(Seak-Tou Lei)

指導教授 ： 陳靜枝

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

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

摘要

在全球供應鏈管理的議題中，最大化整體利益是所有供應鏈成員的共同目標。然而在現今的供應鏈架構中，錯綜複雜的生產環境將會增加供應鏈管理與規劃的困難度，同時存在需求分配的公平性、產品結構間存在共用料與替代料，以及考量產品回收機制的供應鏈網路架構更讓規劃者難以處理。本研究屬於先進規劃排程中，同時考量多個最終產品、規劃多期、有多張需求、產品存在共用料和替代料、需求分配之公平性以及回收機制，作最佳化主規劃排程。
本研究所討論的目標有六個，分別是最小化延遲成本、最大化公平性、最小化回收規費、最小化替代成本、最小化替代優先次序，以及最小化總製造、配送、存貨、運輸與需求切割成本。本研究分有兩個模式，兩者先滿足前兩個目標，在模式一中其餘四個目標可任意依序進行最佳化；模式二中其餘四個目標可設定不同的權重同時進行最佳化。本研究將先以混合整數線性規劃模型求解，但遇到規模更大的問題時，將會耗費大量時間求解或無法求得解答，因此本研究提出一套以基因演算法為基礎的啟發式演算法(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.

並列關鍵字

Supply Chain Management ； Advanced Planning and Scheduling ； Master Planning ； Heuristic Algorithm ； Multiple-goal Optimization ； Fairness ； Substitutions ； Recycle Process ； Recycle Penalty

參考文獻

[4] 林仲輝，「考慮共用料之供應鏈網路主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國93年。

[5] 楊依潔，「供應鏈網路中考量替代料之主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國94年。

[7] 黃慨郁，「供應鏈網路中考量回收機制之主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國95年。

[8] 李和璞，「考量替代路徑下，上下游多廠整合生產規劃問題之研究」，台灣大學商學研究所碩士論文，民國93年。

[6] 吳宏佑，「先進規劃排程中考慮切單限制與公平性之主規劃排程演算法」，台灣大學資訊管理研究所碩士論文，民國94年。