臺灣博碩士論文加值系統

本研究探討遇缺補貨型之二階層供應鏈動態批量存貨模式，此供應鏈包含一上游供應商與一下游零售商，供應商可向外部訂貨(或生產)，以滿足下游零售商之訂購需求，且不允許缺貨；而下游零售商則向上游訂貨，以滿足其末端顧客需求，當零售商存貨不足時，則以遇缺補貨方式補足顧客需求。本研究考慮固定規劃期間之動態型需求，即末端顧客需求為已知且可隨期別變動，如顧客之訂單或預測之需求，上、下游之相關成本參數為已知且亦可隨期別變動，在最小化相關總成本之目標下，決定上、下游之最佳訂購或生產批量，其中上游供應商考量之相關成本為：每次固定訂購(或整備)成本、每單位採購(或生產)成本，與存貨持有成本；下游零售商考量之相關成本為：每次固定訂購成本、每單位採購成本、存貨持有與缺貨成本。
　本研究中首先建立一數學整數規劃模式，根據問題特性與現有動態存貨理論，發展最佳解必存在之性質，並透過所發現之最佳解性質與演算範例觀察、歸納，發展出一演算時間複雜度為Ο(n^4)之啟發式動態規劃演算法，可快速求得最佳或近似最佳之各期訂購或生產批量，及其最小相關總成本，其中n為總規劃期數。
　　經由大規模演算實驗結果可發現，與整數規劃模式之精確解比較，本研究所發展之動態啟發式演算法所求出之最佳解，其平均成本偏差率0.186%，在總規劃期為70期之大型問題，其平均求解時間小於一秒，且求解時間之變異極小；相對而言，由整數規劃模式之求解軟體Lingo求解，其平均求解時間約三小時，且求解時間之變異很大，故可推論本研究之啟發式演算法在求解品質與演算效率上均表現十分優異。

A two-echelon dynamic lot-sizing problem with backorder is addressed in this thesis. The supply chain consists of an upstream supplier and a downstream retailer. The supplier orders or produces items to meet retailer's order, and shortage is not allowed. The retailer procures stock from the supplier to satisfy customer’s demand. When customer’s demand can’t be satisfied with the on-hand stock from the retailer, the shortage is backordered and filled as soon as new replenishment is available. For a given stream of demand data in finite periods, the objective is to determine the period and the associated procurement quantity to replenish the stocks for both supplier and retailer, to minimize the total relevant cost. It includes: ordering cost, procurement cost, inventory carrying cost in the supply chain, and shortage cost of the retailer.
Four dominance properties of the dynamic lot sizing problem are presented. Based on these properties, an efficient heuristic that runs in polynomial time Ο(n^4) is developed, where n is the number of planning periods. The computational experiment and result have shown that the dynamic programming-based heuristic is very efficient and effective. It takes less than 1 second to solve a lot-sizing problem with n =70 periods. In comparison with the integer programming model, the average deviation of total cost is less than 0.2%.

摘要 I
Extended Abstract II
誌謝 VI
目錄 VII
表目錄 IX
圖目錄 X
第一章　緒論 1
1.1研究動機 1
1.2研究目的 1
1.3研究範圍 2
1.4研究架構與流程 2
第二章　文獻回顧 4
2.1古典動態批量模式 4
2.2一階動態批量變型模式 6
2.2.1允許缺貨型模式 6
2.2.2其他變型模式 9
2.3多階層動態批量模式 11
2.4多階層動態批量變型模式 13
第三章　二階層動態批量模式建立與性質發現 17
3.1問題描述與假設 17
3.2數學規劃模式 19
3.3最佳解性質之發現與證明 21
第四章 動態啟發式演算法發展與求解實驗 30
4.1動態啟發式演算法 30
4.2範例說明 37
4.2.1範例一 37
4.2.2範例二 40
4.3演算實驗 43
第五章　研究發現與未來研究議題 48
5.1研究發現 48
5.2未來研究議題 49
參考文獻 50
附錄：演算法之程式碼 53

Aggarwal, A., J. K. Park. 1993. Improved algorithms for economic lot size problems. Operations Research. 41 549-571.
Aksen, D., K. Altinkemer, S. Chand. 2003. The single-item lot-sizing problem with immediate lost sales. European Journal of Operational Research. 147 558-566.
Archetti, C., L. Bertazzi, M. G. Speranza. 2014. Polynomial cases of the economic lot sizing problem with cost discounts. European Journal of Operational Research. 237 519-527.
Chen, H.-D., C.-Y. Lee. 1991. A simple algorithm for the error bound of the dynamic lot size model allowing speculative motive. Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida.
Chen, H.-D., D. W. Hearn, C.-Y. Lee. 1994. A new dynamic programming algorithm for the single item capacitated dynamic lot size model. Journal of Global Optimization. 4 285-300.
Chu, F., C. Chu. 2007. Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing. IEEE Transactions on Automation Science and Engineering. 4 233-251.
Chu, C., F. Chu, J. Zhong, S. Yang. 2013. A polynomial algorithm for a lot-sizing problem with backlogging, outsurcing and limited inventory. Computers ＆ Industrial Engineering. 64 200-210.
Evans, J. R. 1985. An efficient implementation of the Wagner-Whitin algorithm for dynamic lot-sizing. Journal of Operations Management. 5 229-235.
Federgruen, A., M. Tzur. 1991. A simple forward algorithm to solve general dynamic lot-sizing models with n periods in Ο(nlogn) or Ο(n) time. Management Science. 37 909-925.
Federgruen, A., M. Tzur. 1993. The dynamic lot sizing model withbacklogging: a simple Ο(nlon) algorithm and minimal forecast horizon procedure. Naval Research Logistics. 40 459-478.
Ganas, I., S. Papachristos. 2005. The single-product lot-sizing problem with constant parameters and backlogging: Exact results, a new solution, and all parameter stability regions. Operations Research. 53 170-176.
Harris, F. W. 1915. What quantity to make at once. In The Library of Factory Management, Vol. V. Operation and Costs. A.W. Shaw Company, Chicago, 47-52.
Hwang, H.-C., W. Van den Heuvel. 2012. Improved algorithms for a lot-sizing problem with inventory bounds and backlogging. Naval Research Logistics. 59 244-253.
Jaruphongsa, W., S. Çetinkaya, C.-Y. Lee. 2004. A two-echelon inventory optimization model with demand time window considerations. Journal of Global Optimization. 30 347-366.
Kis, T., A. Kovacs. 2013. Exact solution approaches for bilevel lot-sizing. European Journal of Operational Research. 226 237-245.
Lee, C.-Y., S. Çetinkaya, W. Jaruphongsa. 2003. A dynamic model for inventory lot sizing and outbound shipment scheduling at a third-party warehouse. Operations Research. 51 735-747.
Love, S. F. 1973. Bounded production and inventory models with piecewise concave costs. Management Science. 20 313-318.
Love, S. F. 1972. A Facilities in Series Inventory Model with Nested Schedules. Management Science. 18 327 - 338.
Melo, R. A., L. A. Wolsey. 2010. Uncapacitated two-level lot-sizing. Operations research letters. 38 241-245.
Sandbothe, R. A., G. L. Thompson. 1990. A forward algorithm for the capacitated lot size model with stockouts. Operations Research. 38 474-486.
Sedeňo-Noda, A., J. Gutiérrez, B. Abdul-Jalbar, J. Sicilia. 2004. An Ο(TlogT) algorithm for the dynamic lot size problem with limited storage and linear costs. Journal Computational Optimization and Applications. 28 311-323.
Taft, E. W. 1918. The most economical production lot. Iron Age. 101 1410-1412.
Van Hoesel, C. P. M., A. P. M. Wagelmans. 1996. An Ο(T ^3) algorithm for the economic lot-sizing problem with constant capacities. Management Science. 42 142-150.
Van Hoesel, S., H. E. Romeijn, D. R. Morales, A. P. M. Wagelmans. 2005. Integrated lot sizing in serial supply chains with production capacities. Management Science. 51 1706-1719.
Wagelmans, A., S. Van Hoesel, A. Kolen. 1992. Economic lot-sizing：An Ο(nlogn) algorithm that runs in linear time in the Wagner-Whitin case. Operations Research. 40 145-156.
Wagner, H. M., T. M. Whitin. 1958. Dynamic version of the economic lot size model. Management Science. 5 89-96.
Zangwill, W. I. 1966. A deterministic multi-period production scheduling model with backlogging. Management Science. 13 105-119.
Zangwill, W. I. 1968. Minimum concave cost flows in certain networks. Management Science. 14 429-450.
Zangwill, W. I. 1969. Backlogging model and a multi-echelon model of a dynamic economic lot size production system-network apporach. Management Science. 15 506-527.
Zhang, M., S. Kucukyavuz, H. Yaman. 2012. A polyhedral study of multiechelon lot sizing with intermediate demands. Operations Research. 60 918-935.