臺灣博碩士論文加值系統

本研究針對多階層可維修式存貨系統問題發展演算法，此存貨系統包含總倉維修中心與多個服務站，當零件損壞時，服務站扮演服務顧客的角色，提供新的替代品給顧客，但不對損壞零件進行維修，並根據存貨政策向總倉維修中心補貨。
總倉維修中心具有補貨和維修功能，負責維修服務站送來之損壞零件。在此存貨系統中，顧客需求的間隔時間、運輸時間及維修時間皆為隨機性的變數，為高複雜性的問題。
本研究之兩階層可維修式存貨系統採用連續補貨策略(S-1, S)，將顧客等候時間當作服務績效，而顧客等候時間為顧客發現零件損壞到更換零件後的間隔時間，即和總倉和各服務站之起始存貨水準相關，並期望在最小化成本且各服務站的顧客等候時間低於門檻值下，求得各服務站和總倉維修中心最佳的訂購策略。此系統具有一個確定目標式和多條隨機限制式且擁有龐大的解空間，無法用傳統數學模式有效率的求解，此外為了更符合真實情境的隨機性，因此本研究將發展一個模擬最佳化演算法，結合樣本平均近似法(Sample Average Approximation)、切面法(Cutting Plane Method)、可行性檢查程序(Feasible Check Procedure)和可行方向法(Feasible Direction Methods)求解問題。

We address a two-echelon spare parts repairable inventory system consisting of a central repair warehouse and some regional depots. The objective is to determine an (S-1, S) pair that minimizes a cost function, defined only in terms of holding costs, subject to the constraint that the average response time to each customer is below a threshold level. To avoid the mistakes resulting from the approximation and implausible assumptions in traditional methods, we propose an algorithm based on simulation instead of queueing theory. The R＆S procedure can be used to solve simulation optimization problems for which the number of feasible solution is small, and thus we propose a simulation algorithm which combines the cutting plane method, the feasible check procedure and the feasible direction approach.

目錄
摘要 i
英文延伸摘要 ii
致謝 v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3論文架構 3
第二章 文獻回顧 4
2.1多階層可維修商品存貨系統 4
2.2樣本平均近似法(Sample Average Approximation; SAA) 6
2.3可行性檢查程序(Feasibility-Check-Procedure; FCP) 8
2.3.1考慮單一隨機限制式和單一系統的可行性檢查程序(Feasibility Check-Procedure; F) 11
2.3.2考慮多條隨機限制式和多個系統的可行性檢查程序(Multiple Feasibility Check Procedure; Fβ) 12
2.4可行方向法(Feasibility Direction Methods) 14
2.4.1 Zoutendijk可行方向法(Zoutendijk’s Feasible Direction Methods) 15
2.4.2-有限微分估計法(Finite Difference Estimates; FD Estimates) 18
第三章 研究方法 20
3.1 兩階層可維修零件存貨系統 20
3.2 有服務限制的多階層可維修式商品存貨系統的樣本平均估計 23
3.3具有凸性性質的期望等候時間限制 24
3.4可行方向法 25
3.5模擬最佳化演算法 27
第四章-實驗情境與分析 32
4.1實驗評估 32
4.2實驗結果 35
4.3限制式具凸性性質之數學問題 40
4.3.1常態分佈驗證 45
第五章 結論 46
5.1論文總結 46
5.2未來方向 47
參考文獻 48

表目錄
4.1存貨模擬參數設定 35
4.2演算法參數設定 35
4.3情境參數設定 36
4.4運送時間不同下之樣本變異數比較 36
4.5維修時間不同下之樣本變異數比較 36
4.6設定A和設定B之樣本變異數比較 36
4.7實驗結果-設定A 38
4.8實驗結果-設定B 39
4.9實驗結果(EX1) 43
4.10實驗結果(EX2) 43
4.11實驗結果(EX3) 44
4.12產生常態分佈變數之程式碼45
圖目錄
2.1存在兩條限制式的理想區(D)、可接受區間(A)和不可接受區間(U) 10
2.2有限制式y≤a’的三角連續區域 12
2.3解決有限制式最佳化問題方法 15
3.1兩階層存貨系統架構 21
3.2模擬最佳化流程圖 28
4.1不同為分參數設定 33
4.2常態分佈驗證結果 45

1.S. Andradóttir, Simulation Optimization. In: Banks, J. (ED.), Handbook of Simulation, Chapter 9. John Wiley ＆ Sons, New York (1998) 307-333.
2.S. Andradóttir, S.H. Kim, Fully sequential procedures for comparing constrained systems via simulation. Naval Research Logistics 57 (2010) 403-421.
3.J. Atlason, M.A. Epelman, S.G. Henderson, Call center staffing with simulation and cutting plane methods. Annals of Operations Research 127 (2004) 333-358.
4.J. Atlason, M.A. Epelman, S.G. Henderson, Optimizing call center staffing using simulation and analytic center cutting-plane methods. Management Science 54 (2008) 295-309.
5.S. Axsӓter, Continuous review policies for multi-level inventory systems with stochastic demand. In: Graves, S.C., RinnooyKan, A.H.G. , Zipkin, P.H. (ED.), Logistics of Production and Inventory. North-Holland, New York (1993) 175-197.
6.S. Bashyam, M.C. Fu, Optimization of ($s$, $S$) inventory systems with random lead times and a service level constraint. Management Science 44 (1998) 243-256.
7.D. Batur, S.H. Kim, Finding feasible systems in the presence of constraints on multiple performance measures. ACM Transactions on Modeling and Computer Simulation 20 (2010) 1-26.
8.G. Bayraksan, D.P. Morton, A sequential sampling procedure for stochastic programming. Operations Research 59 (2010) 898-913.
9.R.E. Bechhofer, A single-sample multiple decision procedure for ranking means of Normal populations with known variances. Annals of Mathematical Statistics 25 (1954) 16-39.
10.E.M.L. Beale, An Alternative Method of Linear Programming. Mathematical Proceedings of the Cambridge Philosophical Society 50 (1954) 513-213.
11.E.M.L. Beale, On Quadratic Programming. IMA Journal of Applied Mathematics 6 (1959) 227-243.
12.I.J. Bier, J.P. Tjelle, The Importance of Interoperability in a Simulation Prototype for Spares Inventory Planning. Proceedings of the 26th conference on Winter simulation. Society for Computer Simulation International (1994) 913-919.
13.R. Bollapragada, U.S. Rao, J. Zhang, Managing Inventory and Supply Performance in Assembly Systems with Random Supply Capacity and Demand. Management Science 50 (2004) 1729-1743.
14.K.E. Caggiano, P.L. Jackson, J.A. Muckstadt, J.A. Rappold, Optimizing service parts inventory in a multi-echelon, multi-item supply chain with time-based customer service level agreements. Operations Research 55 (2007) 303-318.
15.K.E. Caggiano, P.L. Jackson, J.A. Muckstadt, J.A. Rappold, Efficient computation of time-based customer service levels in a multi-item, multi-echelon supply chain: A practical approach for inventory optimization. European Journal of Operational Research 199 (2009) 744-749.
16.D. Caglar, C.-L. Li, D. Simchi-Levi, Two-echelon spare parts inventory system subject to a service constraint. IIE Transactions 36 (2004) 655-666.
17.M.F. Candasa, E. Kutanoglua, Benefits of considering inventory in service parts logistics network design problems with time-based service constraints. IIE Transactions 39 (2007) 159-176.
18.K.D. Cattani, F.R. Jacobs, J. Schoenfelder, Common inventory modeling assumptions that fallshort: arborescent networks, Poisson demand, and single-echelon approximations. Journal of Operations Management 29 (2011) 488-499.
19.M.T. Cezik, P. L'Ecuyer, Staffing multiskill call centers via linear programming and simulation. Management Science 54 (2008) 310-323.
20.M.A. Cohen, C. Cull, H.L. Lee, D.Willen, Saturn's supply chain innovation: high value in after sales service. MIT Sloan Management Review 41 (2000) 93-101.
21.M.A. Cohen, P.R. Kleindorfer, H.L. Lee, Service constrained (s, S) inventory systems with priority demand classes and lost sales. Management Science 34 (1998) 482-499.
22.M. Frank, P. Wolfe, An Algorithm for Quadratic Progrmming. Naval research logistics quarterly 3 (1956) 95-110.
23.P.W. Glynn, Stochastic approximation for Monte Carlo optimization. Proc. Winter Simulation Conf. (1986) 356-364.
24.S.C. Graves, A multi-echelon inventory model for a repairable item with one-for-one replenishment. Management Science 31 (1985) 1247-1256.
25.K. Healy, L.W. Schruben, Retrospective simulation response optimization. In: Nelson, B.L. , Kelton, D.W., Clark, G.M. (ED.), Proc. 1991 Winter Simulation Conf., Institute of Electrical and Electronics Engineers, Piscataway, NJ (1991) 954-957.
26.Y.T. Herer, M. Tzur, E. Yucesan, The multilocation transshipment problem. IIE Transactions 38 (2006) 185-200.
27.T. Homem-de-Mello, Variable-sample methods for stochastic optimization. ACM Transactions on Modeling and Computer Simulation 13 (2003) 108-133.
28.W.J. Hopp, R.Q. Zhang, M.L. Spearman, An easily implementable hierarchical heuristic for a two-echelon spare parts distribution system. IIE Transactions 31 (1999) 977-988.
29.P.A. Jensen, J.F. Bard, Operations Research Models and Methods. John Wiley and Sons Incorporated (2003).
30.J. Kiefer, J. Wolfowitz, Stochastic estimation of the maximum of a regression function. Annals of Mathematical Statistics (1952) 462- 466.
31.A.J. Kleywegt, A. Shapiro, T. Homem-de-Mello, The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization 12 (2001) 479-502.
32.M.A. Kouritzin, On the convergence of linear stochastic approximation procedures. IEEE Transactions on Information Theory (1996)1405-1309.
33.H.J. Kushner, D.C. Clark, Stochastic Approximation Methods for Constrained and Unconstrained Systems, Springer, New York (1978).
34.S.R. Kulkarni, C.S. Horn, An alternate proof for convergence of stochastic-approximation algorithms. IEEE Transactions on Automatic Control (1996) 419-424.
35.P. L'Ecuyer, Convergence rates for steady-state derivative estimators. Annals of Operations Research 39 (1992) 121-136.
36.P. L'Ecuyer, N. Giroux, P.W. Glynn, Stochastic optimization by simulation: numerical experiments with a simple queue in steady state. Management Science (1994).
37.P. L'Ecuyer, G. Perron, On the convergence rates of IPA and FDC derivative estimators for finite-horizon stochastic simulations, Operations Research (1994) 643-656.
38.J.D.C. Little, A proof of the queueing formula: L=λ W. Operations Research 9 (1961) 383-387.
39.D.G. Luenberger, Introduction to linear and nonlinear programming. Addison-Wesley Publishing Company (1973).
40.J.A. Muckstadt, A model for a multi-item, multi-echelon, multi-indenture inventory system. Management Science 20 (1973) 472-481.
41.J.A. Muckstadt, L.J. Thomas, Are multi-echelon inventory methods worth implementing in systems with low-demand-rate items? Management Science 26 (1980) 483-494.
42.C. Palm, Analysis of the Erlang traffic formula for busy signal arrangements. Ericsson Technics 5 (1938) 39-58.
43.R. Pasupathy, On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization. Operations Research 58 (2010) 889-901.
44.C.D. Pegden, M.P. Gately, Decision optimization for GASP 4 simulation models, in Proceedings of the 1977 Winter Simulation Conference, IEEE Press, Piscataway, NJ (1977) 125-133.
45.P. Prakash, G. Deng, M.C. Converse, J.G. Webster, G.M. Mahvi, M.C. Ferris, Design optimization of a robust sleeve antenna for hepatic microwave ablation. Physics in Medicine and Biology 53 (2008) 1057-1069.
46.H. Robbins, S. Monro, A stochastic approximation method. Annals of Mathematical Statistics (1951) 400-407.
47.J.B. Rosen, The Gradient Projection Method for Nonlinear Programming, Part I - Linear Constraints. Journal of the Society for Industrial and Applied 8 (1960) 181-217.
48.W.D. Rustenburg, G.J. Van Houtum, W.H.M. Zijm, Spare parts management at complex technology-based organizations: an agenda for research. International Journal of Production Economics 71 (2001) 177-193.
49.S. Sana, K.S. Chaudhuri, On a volume flexible stock-dependent Inventory model. Advanced Modeling and Optimization 5 (2003) 197-210.
50.R.M. Simon, Stationary Properties of a Two-Echelon Inventory Model for Low Demand Items. Operations Research 19 (1971) 761-773.
51.A. Shapiro, Asymptotic analysis of stochastic programs. Annals of Operations Research 30 (1991) 169-186.
52.A. Shapiro, Monte Carlo sampling methods. Ruszczynski, A., Shapiro, A. (ED.), Stochastic Programming. Handbooks in Operations Research and Management Science. Elsevier, Amsterdam (2004) 353-426.
53.C.C. Sherbrooke, METRIC: a multi-echelon technique for recoverable item control. Operations Research 16 (1968) 122-141.
54.C.C. Sherbrooke, VARI-METRIC: improved approximations for multi-indenture, multi-echelon availability models. Operations Research 34 (1986) 311-319.
55.J. Tsitsiklis, D. Bertsekas, Distributed asynchronous deterministic and stochastic gradient optimization algorithms. Automatic Control, IEEE 31 (1986) 803 - 812.
56.E. Tekin, I. Sabuncuoglu, Simulation optimization: A comprehensive review on theory and applications, IIE Transactions 36 (2004) 1067-1081.
57.D.M. Topkis, A.F. Veinott, On the convergence of some feasible direction algorithms for nonlinear programming. SIAM Journal on Control 5 (1967) 268-279.
58.B. Verweij, S. Ahmed, A. Kleywegt, G. Nemhauser, A. Shapiro, The sample average approximation method applied to stochastic vehicle routing problems: A computational study. Computational Optimization and Applications 24 (2003) 289-333.
59.W. Wang, S. Ahmed, Sample average approximation of expected value constrained stochastic programs. Operations Research Letters 36 (2008) 515-519.
60.H. Wong, B. Kranenburg, G.-J. van Houtum, D. Cattrysse, Efficient heuristics for two-echelon spare parts inventory systems with an aggregate mean waiting time constraint per local warehouse. OR Spectrum 29 (2007) 699-722.
61.Y.X. Zheng, Using Sample Average Approximation and Feasibility Check to Solve a Two-Echelon Repairable Inventory System Problem Subject to Service Constraints. Department of Industrial and Information Management. NCKU. (2011)
62.G. Zoutendijk, Methods of Feasible Direction. Elsevier (1960).
63.G. Zoutendijk, Nonlinear programming: a numerical survey. SIAM Journal on Control 4 (1996).