×

Supply capacity acquisition and allocation with uncertain customer demands. (English) Zbl 1178.90135

Summary: We study a class of capacity acquisition and assignment problems with stochastic customer demands often found in operations planning contexts. In this setting, a supplier utilizes a set of distinct facilities to satisfy the demands of different customers or markets. Our model simultaneously assigns customers to each facility and determines the best capacity level to operate or install at each facility. We propose a branch-and-price solution approach for this new class of stochastic assignment and capacity planning problems. For problem instances in which capacity levels must fall between some pre-specified limits, we offer a tailored solution approach that reduces solution time by nearly 80% over an alternative approach using a combination of commercial nonlinear optimization solvers. We have also developed a heuristic solution approach that consistently provides optimal or near-optimal solutions, where solutions within 0.01% of optimality are found on average without requiring a nonlinear optimization solver.

MSC:

90B30 Production models
90B80 Discrete location and assignment
90B05 Inventory, storage, reservoirs
90B06 Transportation, logistics and supply chain management
91B44 Economics of information

Software:

BARON; DICOPT; GAMS
Full Text: DOI

References:

[1] Ahmed, S.; Garcia, R., Dynamic capacity acquisition and assignment under uncertainty, Annals of Operations Research, 124, 267-283 (2004) · Zbl 1053.90097
[2] Albareda-Sambola, M.; van der Vlerk, M.; Fernández, E., Exact solutions to a class of stochastic generalized assignment problems, European Journal of Operational Research, 173, 2, 465-487 (2006) · Zbl 1113.90082
[3] Berman, O.; Ganz, Z.; Wagner, J., A stochastic optimization model for planning capacity expansion in a service industry under uncertain demand, Naval Research Logistics, 41, 545-564 (1994) · Zbl 0801.90068
[4] Birge, J.; Louveaux, F., Introduction to Stochastic Programming (1997), Springer Series in Operations Research: Springer Series in Operations Research New York, NY · Zbl 0892.90142
[5] Bish, E.; Hong, S., Coordinating the resource investment decision for a two-market, price-setting firm, International Journal of Production Economics, 101, 1, 63-88 (2006)
[6] Bish, E.; Wang, Q., Optimal investment strategies for flexible resources, considering pricing and correlated demands, Operations Research, 52, 6, 954-964 (2004) · Zbl 1165.91428
[7] Cattrysse, D.; Salomon, M.; Wassenhove, L. V., A set partitioning heuristic for the generalized assignment problem, European Journal of Operational Research, 72, 167-174 (1994) · Zbl 0798.90107
[8] Cattrysse, D.; Wassenhove, L. V., A survey of algorithms for the generalized assignment problem, European Journal of Operational Research, 60, 260-272 (1992) · Zbl 0760.90071
[9] Chod, J.; Rudi, N., Resource flexibility with responsive pricing, Operations Research, 53, 3, 532-548 (2005) · Zbl 1165.90433
[10] Duran, M. A.; Grossmann, I. E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical Programming, 36, 3, 307-339 (1986) · Zbl 0619.90052
[11] Eppen, G.; Martin, R.; Schrage, L., A scenario approach to capacity planning, Operations Research, 37, 517-527 (1989)
[12] Fine, C.; Freund, R., Optimal investment in product-flexible manufacturing capacity, Management Science, 36, 4, 449-466 (1990) · Zbl 0699.90044
[13] Fisher, M., The Lagrangian relaxation method for solving integer programming problems, Management Science, 27, 1, 1-18 (1981) · Zbl 0466.90054
[14] Freling, R.; Romeijn, H.; Morales, D. R.; Wagelmans, A., A branch-and-price algorithm for the multi-period single-sourcing problem, Operations Research, 51, 6, 922-939 (2003) · Zbl 1165.90435
[15] GAMS Development Corporation, 2008. GAMS - The Solver Manuals. Washington, DC.; GAMS Development Corporation, 2008. GAMS - The Solver Manuals. Washington, DC.
[16] Grossmann, I.E., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E., 2003. DICOPT: A discrete continuous optimization package. <http://www.gams.com/dd/docs/solvers/dicopt.pdf>; Grossmann, I.E., Viswanathan, J., Vecchietti, A., Raman, R., Kalvelagen, E., 2003. DICOPT: A discrete continuous optimization package. <http://www.gams.com/dd/docs/solvers/dicopt.pdf>
[17] Huang, W.; Romeijn, H.; Geunes, J., The continuous-time single-sourcing problem with capacity expansion opportunities, Naval Research Logistics, 52, 3, 193-211 (2005) · Zbl 1090.90008
[18] Kennington, J.; Wang, Z., An empirical analysis of the dense assignment problem: Sequential and parallel implementations, ORSA Journal on Computing, 3, 4, 299-306 (1991) · Zbl 0775.90286
[19] Merzifonluoğlu, Y., Geunes, J., Romeijn, H., 2008. The static stochastic knapsack problem with normally distributed item sizes. Technical Report, Virginia Polytechnic Institute.; Merzifonluoğlu, Y., Geunes, J., Romeijn, H., 2008. The static stochastic knapsack problem with normally distributed item sizes. Technical Report, Virginia Polytechnic Institute.
[20] Mine, H.; Fukushima, M.; Ishikawa, K.; Sawa, I., An algorithm for the assignment problem with stochastic side constraints, Memoirs of the Faculty of Engineering Kyoto University, 26-35 (1983), XLV (Part 4)
[21] Nahmias, S., Production and Operations Analysis (2005), Irwin, McGraw-Hill: Irwin, McGraw-Hill Boston, Massachusetts
[22] Netessine, S.; Dobson, G.; Shumsky, R., Flexible service capacity: Optimal investment and the impact of demand correlation, Operations Research, 50, 375-388 (2002) · Zbl 1163.90343
[23] Prékopa, A., Stochastic Programming (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0834.90098
[24] Sahinidis, N.V., Tawarmalani, M., 2005. BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual.; Sahinidis, N.V., Tawarmalani, M., 2005. BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual.
[25] Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem, Operations Research, 45, 831-841 (1997) · Zbl 0895.90161
[26] Schultz, R.; Stougie, L.; van der Vlerk, M., Two-stage stochastic integer programming: A survey, Statistica Neerlandica, 50, 3, 404-416 (1996) · Zbl 0909.90222
[27] Sen, S.; Higle, J., An introductory tutorial on stochastic linear programming models, Interfaces, 29, 33-61 (1999)
[28] Shen, Z.; Coullard, C.; Daskin, M., A joint location-inventory model, Transportation Science, 37, 1, 40-55 (2003)
[29] Spoerl, D., Wood, K., 2003. A stochastic generalized assignment problem. Working Paper, Naval Postgraduate School.; Spoerl, D., Wood, K., 2003. A stochastic generalized assignment problem. Working Paper, Naval Postgraduate School.
[30] Swaminathan, J., Tool capacity planning for semiconductor fabrication facilities under demand uncertainty, European Journal of Operational Research, 120, 3, 545-558 (2000) · Zbl 0985.90030
[31] Taaffe, K.; Geunes, J.; Romeijn, H., Target market selection and market effort under uncertainty: The selective newsvendor problem, European Journal of Operational Research, 189, 3, 987-1003 (2008) · Zbl 1142.91498
[32] Tawarmalani, M.; Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: A theoretical and computational study, Mathematical Programming, 99, 563-591 (2004) · Zbl 1062.90041
[33] Toktas, B.; Yen, J.; Zabinsky, Z., Addressing capacity uncertainty in resource-constrained assignment problems, Computers and Operations Research, 33, 3, 724-745 (2006) · Zbl 1088.90047
[34] Van Mieghem, J., Investment strategies for flexible resources, Management Science, 44, 8, 1071-1078 (1998) · Zbl 0989.91534
[35] Viswanathan, J.; Grossmann, I. E., A combined penalty function and outer approximation method for minlp optimization, Computers and Chemical Engineering, 14, 769-782 (1990)
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.