考慮固定批量之供應鏈主規劃排程演算法

A Heuristic Master Planning Algorithm Considering Fixed Lot Size for Supply Chain Management

陳昌佑(Chang-You Chen)

指導教授 ： 陳靜枝

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

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

摘要

在現今競爭激烈的環境中，企業必須整合供應鏈各成員，方能使整體利潤最大化。在供應鏈實際運作上，為了經濟效益的考量而產生出製造、訂購及運輸批量的概念，然而供應鏈各成員間的批量政策各自不同，容易造成彼此的存貨累積、整備活動無法相互配合。本研究即為考慮固定批量下之主規劃排程研究，以達到整體供應鏈最佳化為目的。
本研究屬於先進規劃排程中之主規劃排程，規劃供應鏈中期的採購、製造與配銷計畫。本研究考慮多產品、多層級、有產能限制、有整備成本下之靜態批量中，固定批量下最佳化批量數之生產排程問題，以間斷時間模式規劃多張需求。
本研究針對此類規劃問題提出一多目標模型：以最小化總需求延遲成本以滿足顧客需求為第一優先目標，再以最小化其他總成本為次要目標。在本研究中，各節點間的批量關係為一重要因子。不成倍數關係的批量會影響各節點的存貨以及整備成本，進而影響最後的總成本。
由於考量批量以及整備成本，本研究之規劃問題若用最佳演算法求解將屬於一混合整數線性規劃模型。在問題規模龐大時，解題時間將大幅提昇，且不能保證有解以及無解時沒有任何資訊可找出其原因。此外，規劃環境變動時，必須重新建構模型。因此本研究提出一啟發性演算法，使本研究問題能在合理時間內，得到一趨近最佳解之可行解決方案。
本研究啟發性演算法流程為：進行規劃排程之前置作業，接著針對各項目標做需求排序，完成後將依此排序結果規劃每張需求。進行規劃時，會針對該需求之最終產品每一個可能的生產樹，當作第一生產樹規劃，若不足則隨機選取下一棵生產樹直到全部規劃完畢。最後選擇單位規劃成本最低者為該需求最終規劃的結果。在規劃時，會嘗試往前搜尋可用的時距，以降低整備成本。在規劃完該張需求後，也會嘗試往後搜尋可提前的需求，以充分發揮批量的經濟效益。
最後，本研究實做出此規劃排程系統，並進行情境分析與實務案例測試，以驗證本演算法確實可行且具高效率性。

關鍵字

供應鏈管理 ； 先進規劃排程 ； 主規劃排程 ； 啟發式演算法 ； 多目標最佳化 ； 批量 ； 整備成本 ； 整備時間

並列摘要

In a competitive business environment, the partners in a supply chain take responsibility for different tasks, and depending on the tasks it performs, each partner organization generates its own costs (e.g., production, transportation, or inventory). It is in the best interest of the whole supply chain to meet all demands by allotting the resources in the most efficient way, thus minimizing the supply chain’s overall costs. Partners of a supply chain prefer to produce or transport mass quantities of products in order to benefit from economies of scale. However, inconsistent lot-sizing policies taken by different partners of a supply chain may result in high inventory cost and huge setup cost. Considering multiple final products, multi-level BOM, setup cost, and capacitated fixed lot size, this study focuses on solving master planning problems of an “Advanced Planning and Scheduling” system, which is designed to determine a production and distribution plan of a supply chain network to fulfill all demands.
The objective of this study is to produce optimal production plans that will satisfy all demands while minimizing delay penalties and minimizing the costs of setup, materials, production, processing, transportation, and inventory holding—all while respecting the fixed lot-sizing policies, the capacity limitations, and demand deadlines of everyone involved in a given supply chain network. In this study, lot-sizing policy taken by each member of a supply chain is the most important factor that affects the cost of setup and inventory holding.
Mixed Integer Programming (MIP) is a popular way to solve this type of master planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. In response to the difficulty of solving the planning problem, this study proposes a heuristic algorithm, called the Lot-Sizing Master Planning Algorithm or LSMPA. First, LSMPA groups and sorts demands according to the required products and the imposed due dates. Then, the LSMPA plans the demands individually, choosing the best planning production tree from all possible production trees and using BSATA (Backward Searching Available Time Algorithm) to lower the setup cost and FSADA (Forward Searching Available Demand Algorithm) to optimize lot-sizing economic effect. To show the effectiveness and efficiency of the heuristic algorithm, a prototype was constructed and tested, using complexity and computational analyses to demonstrate the power of the algorithm.

並列關鍵字

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

參考文獻

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

[3] 傅光宇著，供應鍊管理之主規劃排程演算法：考慮整備成本與時間對決策之影響，台灣大學資訊管理研究所未出版碩士論文，民國94年。

[7] Boctor, F. F. and P. Poulin , “Heuristics for the N-product, M-stage, Economic Lot Sizing and Scheduling Problem with Dynamic Demand,” International Journal of Production Research, Vol.43, No.13, 2005, pp.2809—2828.

[8] Chan, G. H. and K. S. Chiu,” A Simple Heuristic for Multi-Product Dynamic Lot Sizing Problems,” Computer Ops Res., Vol.24, No.10, 1997, pp. 969—979.

[9] Chopra, S. and P. Meindl, Supply Chain Management: Strategy, Planning, and Operation, USA, Prentice-Hall, Inc., 2001.1