供應鏈管理之主規劃排程演算法:考慮整備成本與時間對決策之影響

A Heuristic Master Planning Algorithm for Supply Chain Network:The Impact on Decision Making with Setup Cost and Time

傅光宇(Allen Fu)

指導教授 ： 陳靜枝

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

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

摘要

在競爭激烈的商業環境中，企業必須透過對供應鏈整體的規劃，才能有效達到整體利潤最大、成本降低或是減少前置時間的目的，因此先進規劃排程中的主規劃排程即是在數個不同的設施與組織間進行協調規劃，以期達到整體供應鏈規劃最佳化的目的。
主規劃排程的問題通常使用線性規劃模式求解，當主規劃排程的問題加入固定成本考量之後，即必須以混合整數規劃模式求解，混合整數規劃模式求解的難度和所需時間遠遠大於線性規劃模式，並且混合整數規劃模式往往會因為變數和限制式過多而無法求解。
基於整數規劃的不可行性，本研究提出一啟發式演算法以解決主規劃排程的問題，除了滿足多最終產品的產品結構、複雜的供應鏈網路架構和多張訂單需求、多期與共用料的環境，並加入整備成本與時間的考量規劃整體供應鏈的生產與配送計畫。
本研究於整備成本與時間的重點研究包括考慮整備成本與時間之訂單排序法、生產路徑選擇法和時距微調法，並提出整備與變動成本平衡演算法(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.

並列關鍵字

Supply Chain Management ； Master Planning ； Heuristic Algorithm ； Advanced Planning and Scheduling ； Multiple-goal Optimization ； Setup Cost ； Setup Time

參考文獻

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

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

[7] Cohen, M. A., and H. L. Lee, “Strategic Analysis of Integrated Production-Distribution Systems: Models and Methods,” Operations Research, Vol.36, No.2, 1988, pp. 216—228.

[8] Degraeve, Z., E. Labro, and F. Roodhooft, “An Evaluation of Vendor Selection Models from A Total Cost of Ownership Perspective,” European Journal of Operational Research, Vol.125, 2000, pp. 34—58.

[9] Geunes, J., “Solving Large-scale Requirements Planning Problems with Component Substitution Options,” Computers & Industrial Engineering, Vol.44, 2003, pp.475—491.