Optimal threshold levels in stochastic fluid models via simulation-based optimization. (English) Zbl 1146.90488
Summary: A number of important problems in production and inventory control involve optimization of multiple threshold levels or hedging points. We address the problem of finding such levels in a stochastic system whose dynamics can be modelled using generalized semi-Markov processes (GSMP). The GSMP framework enables us to compute several performance measures and their sensitivities from a single simulation run for a general system with several states and fairly general state transitions. We then use a simulation-based optimization method, sample-path optimization, for finding optimal hedging points. We report numerical results for systems with more than twenty hedging points and service-level type probabilistic constraints. In these numerical studies, our method performed quite well on problems which are considered very difficult by current standards. Some applications falling into this framework include designing manufacturing flow controllers, using capacity options and subcontracting strategies, and coordinating production and marketing activities under demand uncertainty.
Keywords:
Stochastic optimization; Hedging points; Threshold levels; Generalized semi-Markov processes; Infinitesimal perturbation analysis; Sample-path optimization; Service-level constraints; Stochastic fluid modelsReferences:
| [1] | Akella R, Kumar PR (1986) Optimal control of production rate in a failure prone manufacturing system. IEEE Trans Automatic Control 31(2):116–126 · Zbl 0579.90047 · doi:10.1109/TAC.1986.1104206 |
| [2] | Bielecki T, Kumar PR (1988) Optimality of zero-inventory policies for unreliable manufacturing systems. Oper Res 36(4):532–541 · Zbl 0652.90054 · doi:10.1287/opre.36.4.532 |
| [3] | Birbil Ş\.I, Gürkan G, Listeş O (2006) Solving stochastic mathematical programs with complementarity constraints using simulation. Math Oper Res 31(4):739–760 · Zbl 1278.90278 · doi:10.1287/moor.1060.0215 |
| [4] | Brémaud P, Malhamé RP, Massoulié L (1997) A manufacturing system with general stationary failure process: Stability and IPA of hedging control policies. IEEE Trans Automatic Control 42(2):155–170 · Zbl 0872.90042 · doi:10.1109/9.554397 |
| [5] | Caramanis M, Liberopoulos G (1992) Perturbation analysis for the design of flexible manufacturing system flow controllers. Oper Res 40(6):1107–1125 · Zbl 0765.90050 · doi:10.1287/opre.40.6.1107 |
| [6] | Fletcher R (1987) Prac Methods Optim, 2nd edn. Wiley, Chichester |
| [7] | Fu MC, Healy K (1992) Simulation optimization of (s, S) inventory systems. In Swain JJ, Goldsman D, Crain RC, Wilson JR (eds). Proceedings of the 1992 Winter Simulation Conference Piscataway, New Jersey: IEEE, pp 506–514 |
| [8] | Gershwin SB (1994) Manufacturing system engineering. PTR Prentice Hall, Englewood Cliffs, New Jersey |
| [9] | Gill PE, Murray W, Wright MH (1981) Practical optimization. Academic Press, London · Zbl 0503.90062 |
| [10] | Glasserman P (1991) Gradient estimation via perturbation analysis. Kluwer, Norwell, MA · Zbl 0746.90024 |
| [11] | Glasserman P, Tayur S (1995) Sensitivity analysis for base-stock levels in multiechelon production-inventory systems. Manage Sci 41(2):263–281 · Zbl 0832.90051 · doi:10.1287/mnsc.41.2.263 |
| [12] | Glynn PW (1989) A GSMP formalism for discrete event dynamic systems. Proc. of IEEE 77:14–23 · doi:10.1109/5.21067 |
| [13] | Gürkan G (2000) Simulation optimization of buffer allocations in production lines with unreliable machines. Ann Oper Res 93:177–216 · Zbl 0946.90016 · doi:10.1023/A:1018900729338 |
| [14] | Gürkan G, Özge AY, Robinson SM (1996) Sample-path solution of stochastic variational inequalities, with applications to option pricing. In Charnes JM, Morrice DM, Brunner DT, Swain JJ (eds). Proceedings of the 1996 Winter Simulation Conference. IEEE, Piscataway, New Jersey, pp 337–344 |
| [15] | Gürkan G, Özge AY, Robinson SM (1999a) Sample-path solution of stochastic variational inequalities. Math Program 84:313–333 · Zbl 0972.90079 · doi:10.1007/s101070050024 |
| [16] | Gürkan G, Özge AY, Robinson SM (1999b) Solving stochastic optimization problems with stochastic constraints: An application in network design. In: Farrington PA, Nembhard HB, Sturrock DT, Evans GW (eds). Proceedings of the 1999 Winter Simulation Conference. IEEE, Piscataway, New Jersey, pp 471–478 |
| [17] | Haurie A, L’Ecuyer P, van Delft C (1994) Convergence of stochastic approximation coupled with perturbation analysis in a class of manufacturing flow control models. Discret Event Dyn Syst: Theory Appl 4:87–111 · Zbl 0791.93104 · doi:10.1007/BF01516011 |
| [18] | Ho Y-C, Cao X-R (1991) Perturbation analysis of discrete event dynamical systems. Kluwer, Norwell, MA |
| [19] | Hu J-Q, Xiang D (1995) Monotonicity of optimal control for failure-prone production systems. J. Optim Theory Appl 86(1):57–71 · Zbl 0838.90059 |
| [20] | Hu JQ, Vakili P, Huang L (2004) Capacity and production management in a single product manufacturing systems. Ann Oper Res 125:191–204 · Zbl 1040.90010 · doi:10.1023/B:ANOR.0000011191.49933.04 |
| [21] | Kimemia J, Gershwin SB (1983) An algorithm for the computer control production in flexible manufacturing systems. IIE Trans 15:353–362 · doi:10.1080/05695558308974659 |
| [22] | Kushner HJ, Clark DS (1978) Stochastic approximation methods for constrained and unconstrained systems. Springer-Verlag, New York, NY |
| [23] | L’Ecuyer P, Giroux N, Glynn PW (1994) Stochastic optimization by simulation: numerical experiments with the M/M/1 queue in the steady-state. Manage Sci 40:1245–1261 · Zbl 0822.90066 · doi:10.1287/mnsc.40.10.1245 |
| [24] | Leung YT (1990) Single-run optimization of discrete-event simulations. Ph.D. Dissertation, Department of Industrial Engineering, University of Wisconsin-Madison, Madison, USA |
| [25] | Liberopoulos G, Caramanis M (1994) Infinitesimal perturbation analysis for second derivative estimation and design of manufacturing flow controllers. J Optim Theory Appl 81(2):297–327 · Zbl 0807.90063 · doi:10.1007/BF02191666 |
| [26] | Liberopoulos G, Hu J-Q (1995) On the ordering of optimal hedging points in a class of manufacturing flow control models. IEEE Trans Automat Contr 40(2):282–286 · Zbl 0821.90062 · doi:10.1109/9.341793 |
| [27] | Linderoth JT, Shapiro A, Wright SJ (2002) The empirical behavior of sampling methods for stochastic programming. Optimization Technical Report 02–01, University of Wisconsin-Madison, Madison, USA |
| [28] | Liu Y, Gong W (2002) Perturbation analysis for stochastic fluid queuing systems. Discret Event Dyn Syst: Theory Appl 12:391–416 · Zbl 1035.90022 · doi:10.1023/A:1019707508130 |
| [29] | Meketon M (1987) Optimization in simulation: A survey of recent results. In: Thesen A, Grant H, Kelton WD (eds). Proceedings of the 1987 Winter Simulation Conference. IEEE, Piscataway, New Jersey, pp. 58–67 |
| [30] | Moré J, Wright SJ (1993) Optimization software guide. Frontiers in applied mathematics vol. 14. Society for industrial and applied mathematics, Philadelphia, Pennsylvania · Zbl 0830.65050 |
| [31] | NAG (2002) NAG C Library Manual, Mark 7. Oxford, England: NAG Ltd |
| [32] | Plambeck EL, Fu B-R, Robinson SM, Suri R (1993) Throughput optimization in tandem production lines via nonsmooth programming. In: Schoen J (ed). Proceedings of 1993 Summer Computer Simulation Conference. Society for Computer Simulation, San Diego, CA, pp 70–75 |
| [33] | Plambeck EL, Fu B-R, Robinson SM, Suri R (1996) Sample-path optimization of convex stochastic performance functions. Math Program 75:137–176 · Zbl 0874.90150 |
| [34] | Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 22:400–407 · Zbl 0054.05901 · doi:10.1214/aoms/1177729586 |
| [35] | Robinson SM (1996) Analysis of sample-path optimization. Math Oper Res 21:513–528 · Zbl 0868.90087 · doi:10.1287/moor.21.3.513 |
| [36] | Rubinstein RY, Shapiro A (1993) Discrete event systems: Sensitivity analysis and stochastic optimization by the score function method. Wiley, Chichester and New York · Zbl 0805.93002 |
| [37] | Sethi SP, Yan H, Zhang H, Zhang Q (2002) Optimal and hiearchical controls in dynamic stochastic manufacturing systems. Manuf Serv Oper Manag 4:133–170 · doi:10.1287/msom.4.2.133.281 |
| [38] | Shapiro A, Homem-De-Mello T (1998) A simulation-based approach to two-stage stochastic programming with recourse. Math Program 81:301–325 · Zbl 0919.90120 |
| [39] | Sharifnia A (1988) Production control of a manufacturing system with multiple machine states. IEEE Trans Automat Contr 33(7):620–625 · Zbl 0647.90040 · doi:10.1109/9.1270 |
| [40] | Shedler GS (1993) Regenerative stochastic simulation. Academic Press, San Diego, CA · Zbl 0780.60083 |
| [41] | Sun G, Cassandras CG, Panayiotou CG (2004) Perturbation analysis of multiclass stochastic fluid models. Discret Event Dyn Syst: TheoryAppl 14:267–307 · Zbl 1061.90036 · doi:10.1023/B:DISC.0000028198.41139.20 |
| [42] | Suri R, Fu B-R (1994) On using continuous flow lines to model discrete production lines. Discret Event Dyn Syst 4:129–169 · Zbl 0800.93092 · doi:10.1007/BF01441209 |
| [43] | Tan B (2001) Production control of a failure prone pull manufacturing system with variable demand. Working Paper No:2000/1 v2, Koç University, Istanbul, Turkey |
| [44] | Tan B (2002a) Managing manufacturing risks by using capacity options. J Oper Res Soc 53(2):232–242 · Zbl 1138.91508 · doi:10.1057/palgrave.jors.2601283 |
| [45] | Tan B (2002b) Production control of a pull system with production and demand uncertainty. IEEE Trans Automat Control 47(5):779–783 · Zbl 1364.90147 · doi:10.1109/TAC.2002.1000272 |
| [46] | Tan B, Gershwin SB (2004) Production and subcontracting strategies for manufacturers with limited capacity and volatile demand. Ann Oper Res 125:205–232 · Zbl 1048.90101 · doi:10.1023/B:ANOR.0000011192.23903.7f |
| [47] | Yan H, Yin G, Lou SXC (1994) Using stochastic optimization to determine threshold values for the control of unreliable manufacturing systems. J Optim Theory Appl 83(3):511–539 · Zbl 0813.90056 · doi:10.1007/BF02207640 |
| [48] | Yan H, Zhou XY, Yin G (1999) Approximating an optimal production policy in a continuous flow line: Recurrence and asymptotic properties. Oper Res 47(4):535–549 · Zbl 1014.90033 · doi:10.1287/opre.47.4.535 |
| [49] | Yin G, Zhang Q, Yan HM, Boukas EK (2001) Random-direction optimization algorithms with applications to threshold controls. J Optim Theory Appl 110(1):211–233 · Zbl 0983.93074 · doi:10.1023/A:1017555931930 |
| [50] | Zhang Q, Yin GG, Boukas EK (2001) Optimal control of a marketing-production system. IEEE Trans Automat Contr 46(3):416–427 · Zbl 1017.90035 · doi:10.1109/9.911418 |
| [51] | Zhao Y, Melamed B (2004) Make-to-Stock systems with backorders: IPA gradients. In Ingalls R, Rosetti M, Smith J, Peters B (eds). Proceedings of the 2004 Winter Simulation Conference, IEEE, Piscataway, New Jersey, pp 559–567 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
