A multiobjective metaheuristic for a mean-risk multistage capacity investment problem
Tóm tắt
We propose a multiobjective local search metaheuristic for a mean-risk multistage capacity investment problem with irreversibility, lumpiness and economies of scale in capacity costs. Conditional value-at-risk is considered as a risk measure. Results of a computational study are presented and indicate that the approach is capable of producing high-quality approximations to the efficient sets with a modest computational effort. The best results are achieved with a new hybrid approach, combining Tabu Search and Variable Neighbourhood Search.
Tài liệu tham khảo
Ahmed, M.A., Alkhamis, T.M.: Simulation-based optimization using simulated annealing with ranking and selection. Comput. Oper. Res. 29(4), 387–402 (2002)
Ahmed, S.: Convexity and decomposition of mean-risk stochastic programs. Math. Program. 106(3), 433–446 (2006)
Ahmed, S., Sahinidis, N.V.: An approximation scheme for stochastic integer programs arising in capacity expansion. Oper. Res. 51(3), 461–471 (2003)
Ahmed, S., King, A., Parija, G.: A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. J. Glob. Optim. 26(1), 3–24 (2003)
Alrefaei, M.H., Andradottir, S.: A simulated annealing algorithm with constant temperature for discrete stochastic optimization. Manag. Sci. 45(5), 748–764 (1999)
Barahona, F., Bermon, S., Günlük, O., Hood, S.: Robust capacity planning in semiconductor manufacturing. Nav. Res. Logist. 52(5), 459–468 (2005)
Benjamini, Y., Hochberg, Y.: Controlling the false discovery rate: A practical and powerful approach to multiple testing. J. R. Stat. Soc. 57(1), 289–300 (1995)
Çakanyildirim, M., Roundy, R.O.: Optimal capacity expansion and contraction under demand uncertainty. Working paper. University of Texas at Dallas (2002)
Chang, T.J., Meade, N., Beasley, J.E., Sharaiha, Y.M.: Heuristics for cardinality constrained portfolio optimisation. Comput. Oper. Res. 27(13), 1271–1302 (2000)
Chen, Z.-L., Li, S., Tirupati, D.: A scenario-based stochastic programming approach for technology and capacity planning. Comput. Oper. Res. 29(7), 781–806 (2002)
Cheng, L.F., Subrahmanian, E., Westerberg, A.W.: Multi-objective decisions on capacity planning and production - inventory control under uncertainty. Ind. Eng. Chem. Res. 43(9), 2192–2208 (2004)
Claro, J., Sousa, J.P.: An object-oriented framework for multiobjective local search. In: J.P. Sousa, (ed.) MIC’2001 4th Metaheuristics Int. Conf., Porto, Portugal, pp. 231–236 (2001)
Costa, D., Silver, E.A.: Tabu search when noise is present: An illustration in the context of cause and effect analysis. J. Heuristics 4(1), 5–23 (1998)
Crama, Y., Schyns, M.: Simulated annealing for complex portfolio selection problems. Eur. J. Oper. Res. 150(3), 546–571 (2003)
Czyzak, P., Jaszkiewicz, A.: Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. J. Multi-Criteria Decis. Anal. 7(1), 34–47 (1998)
Das, I.: Robustness optimization for constrained nonlinear programming problems. Eng. Optim. 32(5), 585–618 (2000)
Deb, K., Gupta, H.: Introducing robustness in multiobjective optimization. Report No. 2004016, Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology, Kanpur, India (2004)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Dixit, A.K., Pindyck, R.S.: Investment Under Uncertainty. Princeton University Press, Princeton (1994)
Ehrgott, M., Gandibleux, X.: A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22(4), 425–460 (2000)
Ehrgott, M., Gandibleux, X.: Approximative solution methods for multiobjective combinatorial optimization. TOP 12(1), 1–90 (2004). (Spanish journal of operations research)
Ehrgott, M., Klamroth, K., Schwehm, C.: An MCDM approach to portfolio optimization. Eur. J. Oper. Res. 155(3), 752–770 (2004)
Eichhorn, A., Romisch, W.: Polyhedral risk measures in stochastic programming. SIAM J. Optim. 16(1), 69–95 (2005)
Eppen, G.D., Martin, R.K., Schrage, L.: A scenario approach to capacity planning. Oper. Res. 37(4), 517–527 (1989)
Gandibleux, X., Ehrgott, M.: 1984–2004—20 years of multiobjective metaheuristics. but what about the solution of combinatorial problems with multiple objectives? In: Coello, C.A.C., Aguirre, A.H., Zitzler, E. (eds.) Evol. Multi-Criterion Optim. Lect. Notes Comput. Sci., vol. 3410, pp. 33–46. Springer, Berlin (2005)
Gandibleux, X., Mezdaoui, N., Freville, A.: A multiobjective tabu search procedure to solve combinatorial optimization problems. In: Caballero, R., Ruiz, F. (eds.) Adv. Mult. Objective Goal Program. Lect. Notes Econ. Math. Syst., vol. 445, pp. 291–300. Springer, Berlin (1997)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gutjahr, W.J.: A converging ACO algorithm for stochastic combinatorial optimization. In: Albrecht, A., Steinhöfel, K. (eds.) Stoch. Alg.: Found. Appl. Lect. Notes Comput. Sci., vol. 2827, pp. 10–25. Springer, Berlin (2003)
Hansen, M.P.: Tabu search for multiobjective combinatorial optimization: TAMOCO. Control Cybern. 29(3), 799–818 (2000)
Haugen, K.K., Lokketangen, A., Woodruff, D.L.: Progressive hedging as a meta-heuristic applied to stochastic lot-sizing. Eur. J. Oper. Res. 132(1), 116–122 (2001)
Huang, K., Ahmed, S.: The value of multi-stage stochastic programming in capacity planning under uncertainty. (2005, submitted for publication)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments—a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)
Jin, Y.C., Sendhoff, B.: Trade-off between performance and robustness: An evolutionary multiobjective approach. In: Goos, G., Hartmanis, J., van Leeuwen, J. (eds.) Evol. Multi-Criterion Optim., Proc. Lect. Notes Comput. Sci., vol. 2632, pp. 237–251. Springer, Berlin (2003)
Jones, D.F., Mirrazavi, S.K., Tamiz, M.: Multi-objective meta-heuristics: An overview of the current state-of-the-art. Eur. J. Oper. Res. 137(1), 1–9 (2002)
Jorion, P.: Risk2: Measuring the risk in value-at-risk. Financ. Anal. J. 52(6), 47–56 (1996)
Julka, N., Baines, T., Tjahjono, B., Lendermann, P., Vitanov, V.: A review of multi-factor capacity expansion models for manufacturing plants: Searching for a holistic decision aid. Int. J. Prod. Econ. 106(2), 607–621 (2007)
Knowles, J., Corne, D.: The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation. Proc. 1999 Cong. Evol. Comput., CEC ’99, vol. 1, pp. 98–105 (1999)
Luss, H.: Operations research and capacity expansion problems: A survey. Oper. Res. 30(5), 907–947 (1982)
Malakooti, B., Wang, J., Tandler, E.C.: A sensor-based accelerated approach for multi-attribute machinability and tool life evaluation. Int. J. Prod. Res. 28(12), 2373–2392 (1990)
Medaglia, A.L., Graves, S.B., Ringuest, J.L.: A multiobjective evolutionary approach for linearly constrained project selection under uncertainty. Eur. J. Oper. Res. 179(3), 869–894 (2007)
Narongwanich, W., Duenyas, I., Birge, J.R.: Optimal portfolio of reconfigurable and dedicated capacity under uncertainty. Preprint. University of Michigan (2002)
Rajagopalan, S., Swaminathan, J.M.: A coordinated production planning model with capacity expansion and inventory management. Manag. Sci. 47(11), 1562–1580 (2001)
Ray, T.: Constrained robust optimal design using a multiobjective evolutionary algorithm. In: Proc. 2002 Cong. Evol. Comput., 2002, CEC ’02, vol. 1, pp. 419–424 (2002)
Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26(7), 1443–1471 (2002)
Rockafellar, R.T., Wets, R.J.B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1), 119–147 (1991)
Rosen, S.L., Harmonosky, C.M.: An improved simulated annealing simulation optimization method for discrete parameter stochastic systems. Comput. Oper. Res. 32(2), 343–358 (2005)
Rudberg, M., Olhager, J.: Manufacturing networks and supply chains: an operations strategy perspective. Omega 31(1), 29–39 (2003)
Ruszczynski, A., Shapiro, A.: Optimization of convex risk functions. Math. Oper. Res. 31(3), 433–452 (2006)
Schaffer, J.D.: Multiple objective optimization with vector evaluated genetic algorithms. J.J. Grefenstette (ed.) Gen. Alg. Appl.: Proc. First Int. Conf. Gen. Alg., pp. 92–100, Lawrence Erlbaum (1985)
Schlottmann, F., Seese, D.: A hybrid heuristic approach to discrete multi-objective optimization of credit portfolios. Comput. Stat. Data Anal. 47(2), 373–399 (2004)
Schultz, R.: Stochastic programming with integer variables. Math. Program. 97(1–2), 285–309 (2003)
Schultz, R., Tiedemann, S.: Conditional value-at-risk in stochastic programs with mixed-integer recourse. Math. Program. 105(2–3), 365–386 (2006)
Serafini, P.: Simulated annealing for multiple objective optimization problems. In: Proc. Tenth Int. Conf. Mult. Criteria Decision Making, pp. 87–96, Taipei, Taiwan (1992)
Snow, D.C., Wheelwright, S.C., Wagonfeld, A.B.: Genentech—Capacity Planning. Harvard Business School Case Series, 9-606-052 (2006)
Steuer, R.E.: Multiple Criteria Optimization: Theory, Computation, and Optimization. Wiley, New York (1986)
Swaminathan, J.M.: Tool capacity planning for semiconductor fabrication facilities under demand uncertainty. Eur. J. Oper. Res. 120(14), 545–558 (2000)
Tomlin, B., Wang, Y.: On the value of mix flexibility and dual sourcing in unreliable newsvendor networks. Manuf. Serv. Oper. Manag. 7(1), 37–57 (2005)
Ulungu, E.L., Teghem, J., Fortemps, P.H., Tuyttens, D.: MOSA method: a tool for solving multiobjective combinatorial optimization problems. J. Multi-Criteria Decis. Anal. 8(4), 221–236 (1998)
Van Mieghem, J.A.: Capacity management, investment, and hedging: Review and recent developments. Manuf. Serv. Oper. Manag. 5(4), 269–302 (2003)
Van Mieghem, J.A.: Risk mitigation in newsvendor networks: Resource diversification, flexibility, sharing, and hedging. Manag. Sci. 53(8), 1269–1288 (2007)
Wheelwright, S.C.: Reflecting corporate strategy in manufacturing decisions. Bus. Horiz. 21(1), 57–66 (1978)
Wu, S.D., Erkoc, M., Karabuk, S.: Managing capacity in the high-tech industry: A review of literature. Eng. Econ. 50(2), 125–158 (2005)
Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms—a comparative case study. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.P. (eds.) Parallel Problem Solving from Nature—PPSN V. Lect. Notes Comput. Sci., vol. 1498, pp. 292–301. Springer, Berlin (1998)