(3.230.173.249) 您好!臺灣時間:2021/04/18 08:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:羅蘭英
研究生(外文):Brigitte Trista Indah Yudhiana Sutrisno
論文名稱:A Review of Dynamic Lot Sizing Problems and Its Related Inventory Control Problems
論文名稱(外文):A Review of Dynamic Lot Sizing Problems and Its Related Inventory Control Problems
指導教授:水谷英二
指導教授(外文):Eiji Mizutani
口試委員:王孔政黃安橋
口試委員(外文):Kung-Jeng WangAn-Chyau Huang
口試日期:2019-05-24
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:94
中文關鍵詞:Dynamic ProgrammingDynamic Lot SizeInventory Control
外文關鍵詞:Dynamic ProgrammingDynamic Lot SizeInventory Control
相關次數:
  • 被引用被引用:0
  • 點閱點閱:41
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
This thesis primarily discusses dynamic lot sizing problems for a single item with time-varying deterministic demand. In particular, we carefully review the literature on how special cost assumptions affect the optimal policy structure so as to develop an efficient solution pro-cedure. Our main focus is placed on the development of efficient dynamic programming (DP) procedures, especially a well-known Wagner-Whitin forward DP method for seeking an ex-act optimal solution. This Wagner-Whitin DP algorithm can solve the N-period problem in O(N2) under the concave cost assumptions. In the literature, however, some statements can be found that oppose this exact Wagner-Whitin DP algorithm, misleading the readers to approx-imate heuristic procedures. This is our initial impetus for this thesis to investigate why such misperception of the Wagner-Whitin DP method has arisen in the literature.

Through our early investigation of the literature, we shall carefully describe the develop-ment of various DP procedures. To this end, we begin with a (standard) straight-forward DP that can work under no particular cost assumption, but it works painfully slow, evaluating all the possible inventory levels at each period and also all the possible decisions at each state of inventory level. In practice, however, certain cost structure often entails in the objective func-tion to be minimized. Exploiting such posed special cost structure is often useful in narrowing down the DP search space for an optimal solution. In an extreme case, where the cost func-tion and constraints are all linear functions, the standard linear programming (LP) can apply, and an optimal solution can be found at an extreme point in the feasible solution space. Un-der the concave cost assumptions, Wagner and Whitin (1958) discovered such similar solution structure, and then developed a so-called regeneration-point DP approach, which is called the Wagner-Whitin DP algorithm above.

Furthermore, Wagner and Whitin discovered what they called “Planning Horizon Theo-rem” based on the special concave cost assumption; this makes the procedure more computationally attractive than the above-mentioned Wagner-Whitin DP that works in O(N2). In the literature, some investigators appeared to ignore the special cost assumptions; in consequence, some misleading results and statements can be found that a heuristic method can outperform the Wagner-Whitin DP method for rolling-horizon schedules, some of which are totally outside the special assumptions required for the “Planning Horizon Theorem” to hold. We shall discuss this issue in this thesis.

Finally, we also describe how to improve the (standard) straight-forward DP in order to make it as attractive as the Wagner-Whitin regeneration point approach. This is motivated by Dreyfus and Law (1977, Chapter 2), where the straight-forward DP and a regeneration-point DP work equally well in solving an equipment replacement problem, although the straight-forward DP has two state variables whereas the regeneration-pint DP has only one state variable. We compare them in some detail since this comparison is new to the dynamic lot sizing literature to the best of our knowledge.
This thesis primarily discusses dynamic lot sizing problems for a single item with time-varying deterministic demand. In particular, we carefully review the literature on how special cost assumptions affect the optimal policy structure so as to develop an efficient solution pro-cedure. Our main focus is placed on the development of efficient dynamic programming (DP) procedures, especially a well-known Wagner-Whitin forward DP method for seeking an ex-act optimal solution. This Wagner-Whitin DP algorithm can solve the N-period problem in O(N2) under the concave cost assumptions. In the literature, however, some statements can be found that oppose this exact Wagner-Whitin DP algorithm, misleading the readers to approx-imate heuristic procedures. This is our initial impetus for this thesis to investigate why such misperception of the Wagner-Whitin DP method has arisen in the literature.

Through our early investigation of the literature, we shall carefully describe the develop-ment of various DP procedures. To this end, we begin with a (standard) straight-forward DP that can work under no particular cost assumption, but it works painfully slow, evaluating all the possible inventory levels at each period and also all the possible decisions at each state of inventory level. In practice, however, certain cost structure often entails in the objective func-tion to be minimized. Exploiting such posed special cost structure is often useful in narrowing down the DP search space for an optimal solution. In an extreme case, where the cost func-tion and constraints are all linear functions, the standard linear programming (LP) can apply, and an optimal solution can be found at an extreme point in the feasible solution space. Un-der the concave cost assumptions, Wagner and Whitin (1958) discovered such similar solution structure, and then developed a so-called regeneration-point DP approach, which is called the Wagner-Whitin DP algorithm above.

Furthermore, Wagner and Whitin discovered what they called “Planning Horizon Theo-rem” based on the special concave cost assumption; this makes the procedure more computationally attractive than the above-mentioned Wagner-Whitin DP that works in O(N2). In the literature, some investigators appeared to ignore the special cost assumptions; in consequence, some misleading results and statements can be found that a heuristic method can outperform the Wagner-Whitin DP method for rolling-horizon schedules, some of which are totally outside the special assumptions required for the “Planning Horizon Theorem” to hold. We shall discuss this issue in this thesis.

Finally, we also describe how to improve the (standard) straight-forward DP in order to make it as attractive as the Wagner-Whitin regeneration point approach. This is motivated by Dreyfus and Law (1977, Chapter 2), where the straight-forward DP and a regeneration-point DP work equally well in solving an equipment replacement problem, although the straight-forward DP has two state variables whereas the regeneration-pint DP has only one state variable. We compare them in some detail since this comparison is new to the dynamic lot sizing literature to the best of our knowledge.
Contents
Master’s Thesis Recommendation Form
Qualification Form by Master’s Degree Examination Committee
1 INTRODUCTION
1.1 Overview of Inventory Control Systems
1.2 Dynamic lot sizing problems
1.3 Regeneration-point dynamic programming procedure of Wagner and Whitin
1958 and its related issues
1.4 Organization of Thesis
2 Lot-Sizing for Single-Item with Time-Varying Deterministic Demand in a Fixed-
Horizon
2.1 Problem Statement
2.2 Lot-sizing inventory model with concave costs
2.3 Wagner-Whitin Regeneration Point DP
2.3.1 Numerical Examples using Wagner-Whitin Regeneration Point DP
2.4 The Key Feature of Wagner-Whitin Regeneration Point DP
2.4.1 Numerical Examples for Key Feature of Wagner-Whitin Regeneration
Point DP
2.5 Analysis of Planning Horizon Theorem
2.6 Standard Forward Dynamic-Programming and its improvements
2.6.1 Numerical Examples using Improved Version 1 of Standard DP
2.6.2 Numerical Examples using Improved Version 2 of Standard DP
2.7 The Key Feature of Improved Standard DP
2.8 Regeneration point dynamic programming (DP) versus standard DP
2.9 Results obtained by Silver-Meal Heuristic
3 Lot-Sizing for Single-Item with Time-Varying Demand in a Rolling-Horizon
3.1 The Wagner-Whitin Regeneration Point DP in a Rolling Horizon
3.2 An Observation of Wagner-Whitin in a Rolling Horizon
3.3 A well-known Silver-Meal heuristic
4 CONCLUSION AND FUTURE RESEARCH
Bibliography
Appendices
A Results for Example of Silver et al. [2, p.202]
A.1 Obtained by Wagner-Whitin Regeneration Point DP
A.2 Obtained by Improved Standard DP Version 1
A.3 Obtained by Improved Standard DP Version 2
A.4 Obtained by SM Heuristic
B Results for Modified Example of Wagner & Whitin [3, p.94]
B.1 Obtained by Wagner Whitin Regeneration Point DP
B.2 Obtained by Improved Standard DP Version 1
B.3 Obtained by Improved Standard DP Version 2
B.4 Obtained by SM Heuristic
C Results for Example of Dreyfus & Law [1, p.162]
C.1 Obtained by Wagner-Whitin Regeneration Point DP
C.2 Obtained by Improved Standard DP Version 1
C.3 Obtained by Improved Standard DP Version 2
C.4 Obtained by SM Heuristic
D Results of Planning Horizon Theorem Analysis
D.1 Case A
D.2 Case B
[1] Stuart E. Dreyfus and Averill M. Law. Art and Theory of Dynamic Programming. Academic Press, Inc. Orlando, FL, USA, 1977.

[2] E.A. Silver, D.F. Pyke, and R. Peterson. Inventory Management and Production Planning and Scheduling : Third Edition. Wiley, 1998.

[3] Harvey M. Wagner and Thomson M. Whitin. Dynamic version of the economic lot size model. Management Science, 5(1):89–96, 1958.

[4] Joseph D Blackburn and Robert A Millen. Heuristic lot-sizing performance in a rolling-schedule environment. Decision Sciences, 11(4):691–701, 1980.

[5] E.A. Silver and H.C. Meal. A simple modification of the eoq for the case of varying demand rate. Production and Inventory Management, 10:52–65, 1969.

[6] Gabriel R Bitran, Thomas L Magnanti, and Horacio H Yanasse. Approximation methods for the uncapacitated dynamic lot size problem. Management Science, 30(9):1121–1140, 1984.

[7] John J. DeMatteis. An economic lot-sizing technique, i: The part-period algorithm. IBM systems Journal, 7(1):30–38, 1968.

[8] S. Nahmias and T.L. Olsen. Production and Operations Analysis: Seventh Edition. Wave-land Press, Inc., 2015.

[9] James R. Evans, Cem Saydam, and Mark McKnew. A note on solving the concave cost dynamic lot-sizing problem in almost linear time. Journal of Operations Management, 8(2):159–167, 1989.

[10] Awi Federgruen and Michal Tzur. A simple forward algorithm to solve general dynamic lot sizing models with n periods in o(nlogn) or o(n) time. Management Science, 37(8):909– 925, 1991.

[11] Nusrat T. Chowdury, M.F. Baki, and A. Azab. Dynamic economic lot-sizing problem: A new o(t) algorithm for the wagner-whitin model. Computers & Industrial Engineering, 117:6–18, 2018.

[12] Kenneth R. Baker. An experimental study of the effectiveness of rolling schedules in production planning. Decision Sciences, 8:19–27, 1977.


57


[13] Tianbing Qian, Philip C. Jones, and Yinyu Ye. Worst case analysis of forward wagner whitin algorithm with rolling horizon. unpublished, 1996.

[14] Robert C. Carlson, Sara L. Beckman, and Dean H. Kropp. The effectiveness of extending the horizon in rolling production scheduling. Decision Sciences, 13:129–145, 1982.

[15] James R. Evans. An efficient implementation of the wagner-whitin algorithm for dynamic lot-sizing. Journal of Operation Management, 5(2):229–235, 1985.

[16] Kenneth R. Baker and David W. Peterson. An analytic framework for evaluating rolling schedules. Management Science, 25(4):341–351, 1979.

[17] Richard Bellman. Dynamic programming approach to optimal inventory processes with delay in delivery. Quarterly of Applied Mathematics, 18(4):399–403, 1961.

[18] Albert P.M. Wagelmans, A. van Hoesel, and Antoon Kolen. Economic lot-sizing: An o(n log n) algorithm that runs in linear time in the wagner-whitin case. Operations Research, 40(Supp. 1):145–156, 1992.

[19] Alok Aggarwal and James K. Park. Improved algorithms for economic lot size problems Operations Research, 41(3):549–571, 1993.

[20] M. Florian and M. Klein. Deterministic production planning with concave costs and ca-pacity constraints. Management Science, 18(1):12–20, 1971.

[21] Kenneth R. Baker, P. Dixon, M.I. Magazine, and E.A. Silver. An algorithm for the dynamic lot-size problem with time-varying production capacity constraints. Management Science, 24(16):1710–1720, 1978.

[22] M. Florian, J.K. Lenstra, and A. Rinnooy Kan. Deterministic production planning: algo-rithms and complexity. Management Science, 26(7):669–679, 1980.

[23] A. Lambert and H. Luss. Production planning with time-dependent capacity bounds. Eu-ropean Journal of Operational Research, 9:275–280, 1982.

[24] Gabriel R. Bitran and Horacio H. Yanasse. Computational complexity of the capacitated lot size problem. Management Science, 28:1–13, 1982.

[25] Chia Shin Chung and Chien Hua Mike Lin. An O(T 2) algorithm for the N I=G=N I=N D capacitated lot size problem. Management Science, 34:420–426, 1988.

[26] O. Kirca. An efficient algorithm for the capacitated single item dynamic lot size problem. European Journal of Operational Research, 45(1):15–24, 1990.

[27] Hsin-Der Chen, Donald W. Hearn, and Chung Yee Lee. A new dynamic programming algorithm for the single item capacitated dynamic lot size model. Journal of Global Opti-mization, 4:285–300, 1994.

[28] C. P. M. van Hoesel and Albert P.M. Wagelmans. An O(T 3) algorithm for the economic lot-sizing problem with constant capacities. Management Science, 42:142–150, 1996.



58


[29] Dong X. Shaw and Albert P.M. Wagelmans. An algorithm for single-item capacitated lot sizing with piecewise linear production costs and general holding costs. Management Science, 44:831–838, 1998.

[30] Wilco van den Heuvel and Albert P.M. Wagelmans. An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem. Computers & Operations Research, 33:3583–3599, 2006.

[31] Yi Feng, Shaoxiang Chen, Arun Kumar, and Bing Lin. Solving single-product economic lot-sizing problem with non-increasing setup cost, constant capacity and convex inventory in o(nlogn) time. Computers & Operations Research, 38:717–722, 2011.

[32] Jinwen Ou. Economic lot-sizing with constant capacity and concave inventory costs. Naval Research Logistics, 59:717–722, 2012.

[33] H.M. Wagner. Principles of Operations Research with Applications to Managerial Deci-sions: 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, Inc., 1975.

[34] Kenneth R. Baker. An analysis of terminal conditions in rolling schedules. European Journal of Operational Research, 7:355–361, 1981.

[35] Eiji Mizutani and Stuart Dreyfus. Stage-lookahead dynamic programming algorithms for stochastic problems with time-lagged control dynamics. IEEE IEEM, 2009.

[36] S. Dreyfus. An analytic solution of the warehouse problem. Operations Research, 1:99– 104, 1957.

[37] R. Bellman. On the Theory of Dynamic Programming – a Warehouse Problem. Manage-ment Science, 2(3):272–274, 1956.

[38] R. Bellman. Dynamic programming approach to optimal inventory processes with delay in delivery Naval Research Logistics, XVIII(4):399–403, 1960.

[39] H. M. Wagner. A postscript to “Dynamic problems in the theory of the firm” Naval Research Logistics Quarterly, 7(1):7–12, 1960.

[40] Eiji Mizutani and Brigitte Trista. On two new dynamic programming procedures com-parable to the Wagner-Whitin regeneration point type in dynamic lot sizing. unpublished, 2019.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔