回收供應鏈管理之主規劃排程演算法

A Heuristic Master Planning Algorithm for Recovery Supply Chain Management

王馨梅(Hsin-Mei Wang)

指導教授 ： 陳靜枝

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

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

摘要

回收是近來極受重視的全球性議題。回收廢棄物有諸多益處，如可提供價格低廉的再生物料以及降低垃圾量，但由於回收過程中，商品會被逐步分解成許多需求物料、需求之間無法被獨立規劃的特性，針對回收流程進行主規劃排程較一般生產規劃更顯困難。為了解決回收流程的主規劃排程問題，以往研究提出了一些網路模型，但這些模型多半過於簡化，且附帶諸多假設限制，如僅規劃單期、單一角色或單一商品的回收活動。
有鑑於此，本研究提出了結構更為完整的回收供應鏈（Recovery Supply Chain）模型，其中成員包括了廢棄物收集商（Collector）、拆解商（Disassembler）、壓碎商（Shredder）、原物料精製商（Reconditioner）及廢棄物料處理商（Garbage Handler）。以此模型為基礎，本研究致力於解決需求導向回收供應鏈的主規劃排程問題。在考量多個廢棄商品、規劃多期、且有多張需求的狀況下，以間斷時間模式進行回收供應鏈中期的生產、運輸、存貨、整備及物料棄置活動規劃。
本研究首先提出一多目標混合整數線性規劃模型，最小化總需求延遲成本以滿足需求為首要考量；當延遲成本獲得最佳解之後，再以最小化總處理、運輸、存貨、整備及廢棄商品成本為目標。此規劃問題若以混合整數線性規劃模型求解，在問題規模龐大時，需要花費大量時間求解，也可能無法求得可行解。因此本研究提出ㄧ啟發式演算法，使得問題能在有效率的時間下，得到一趨近最佳解之解決方案。
本研究啟發式演算法的流程為：先進行規劃排程之前置作業，接著將需求排序，完成後依照排序結果對每張需求進行規劃排程，找出對應的最佳生產路徑及生產時程。最後，本研究將實際建立一規劃排程系統，並進行情境分析及實例討論，以驗證本啟發式演算法為一可行且高效率之規劃求解選擇。

關鍵字

主規劃排程 ； 多目標混合整數線性規劃模型 ； 啟發式演算法 ； 回收之產品結構 ； 回收供應鏈

並列摘要

Recently, recovery management becomes an important issue around the world. In spite of all economical and environmental advantages of recovery, it is difficult to solve corresponding master planning (MP) problems as products are sequentially decomposed into multiple demand sources. Some network models are proposed before to solve such problems, but they are simple and with unrealistic assumptions.
In this study, a complete recovery supply chain model, which includes players like collectors, disassebmlers, shredders, reconditioners and garbage handlers, is proposed. Then, considering multiple product structures, multiple discrete planning periods and multiple demands, MP problems for recovery supply chains are solved to determine optimal transportation, processing, stocking, and garbage handling quantities of players.
To solve MP problems for recovery supply chains, a multiple-goal Mixed Integer Programming (MIP) model is proposed with two objectives. The first objective is to minimize the total delay cost. The second objective is to minimize the sum of processing cost, transportation cost, holding cost, setup cost and garbage handling cost given that the first one is minimized. Though the MIP model can obtain optimal solutions when problems are simple, the solving times grow exponentially with the increase of problem sizes. It may even fail to return feasible solutions when problems become extremely complex. To improve the effectiveness and efficiency of finding solutions, a heuristic algorithm, Recovery Process Master Planning Algorithm (RPMPA), is proposed.
The main process of RPMPA consists of three phases: preliminary works, demand grouping and sorting algorithm (DGSA), and the Recovery Process Path Selection Algorithm (RPPSA). For preliminary works, all multi-function nodes are split into single-function nodes and sub-networks of requested components are extracted. In DGSA, the sequence of demands is determined. Finally, in RPPSA, best disassembly paths and disassembly time schedules are decided for individual demands based on the sequence outputted by DGSA. To show the effectiveness and efficiency of RPMPA, a prototype is constructed and a scenario analysis is conducted.

並列關鍵字

Master Planning (MP) ； Mixed Integer Programming (MIP) ； Heuristic Algorithm ； BOM for Recovery ； Recovery Supply Chain

參考文獻

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

[1] 陳昌佑，「供應鏈管理之主規劃排程演算法 ─　考慮批量對決策之影響」，台灣大學資訊管理學系研究所碩士論文，民國97年。

[2] 傅光宇，供應鏈之主規劃排程演算法 ─ 考慮整備成本與時間決策之影響」，台灣大學資訊管理學系研究所碩士論文，民國94年。

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

[6] Adenso-Díaz, B., S. García-Carbajal and S. Lozano, “An Efficient GRASP Algorithm for Disassembly Sequence Planning,” OR Spectrum, Vol. 29, No. 3, ppt. 535-549, 2007.