Approximation algorithms for supply chain planning and logistics problems with market choice. (English) Zbl 1229.90011
Summary: We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of \(markets\), each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost production plan (set of facilities) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility opening and connection) costs. These models capture important aspects of demand shaping within supply chain planning and logistics models. We introduce a general algorithmic framework that leverages existing approximation results for the traditional models to obtain corresponding results for their counterpart models with market choice. More specifically, any LP-based \(\alpha \)-approximation for the traditional model can be leveraged to a \({\frac{1}{1-e^{-1/\alpha}}}\)-approximation algorithm for the counterpart model with market choice. Our techniques are also potentially applicable to other covering problems.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 68W25 | Approximation algorithms |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Aggarwal A., Park J.K.: Improved algorithms for economic lot-sizing problems. Oper. Res. 14, 549–571 (1993) · Zbl 0820.90035 · doi:10.1287/opre.41.3.549 |
| [2] | Arkin E., Joneja D., Roundy R.: Computational complexity of uncapacitated multi-echelon production planning problems. Oper. Res. Lett. 8, 61–66 (1989) · Zbl 0674.90044 · doi:10.1016/0167-6377(89)90001-1 |
| [3] | Balas E.: The prize collection travelling salesman problem. Networks 19, 621–636 (1989) · Zbl 0676.90089 · doi:10.1002/net.3230190602 |
| [4] | Bárány I., Van Roy T.J., Wolsey L.A.: Uncapacitated lot-sizing: the convex hull of solutions. Math. Program. Study 22, 32–43 (1984) · Zbl 0551.90068 · doi:10.1007/BFb0121006 |
| [5] | Bartal Y., Leonardi S., Spaccamela A.M., Sgall J., Stougie L.: Multiprocessor scheduling with rejection. SIAM J. Discret. Math. 13, 64–78 (2000) · Zbl 0936.68012 · doi:10.1137/S0895480196300522 |
| [6] | Bertsimas D., Teo C., Vohra R.: On dependent randomized rounding algorithms. Oper. Res. Lett. 25, 105–114 (1999) · Zbl 0954.90025 · doi:10.1016/S0167-6377(99)00010-3 |
| [7] | Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993) · Zbl 0793.90089 · doi:10.1007/BF01581256 |
| [8] | Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of APPROX-RANDOM, pp. 29–43 (2007) · Zbl 1171.90456 |
| [9] | Chan A., Muriel A., Shen Z.-J., Simchi-Levi D., Teo C.-P.: Effectiveness of zero inventory ordering policies for an one-warehouse multi-retailer problem with piecewise linear cost structures. Manage. Sci. 48, 1446–1460 (2000) · Zbl 1232.90031 · doi:10.1287/mnsc.48.11.1446.267 |
| [10] | Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642–651 (2001) · Zbl 1012.90026 |
| [11] | Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the capacitated facility location problem. In: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. S875–S876, (1999) · Zbl 1052.90580 |
| [12] | Federgruen A., Tzur M.: A simple forward algorithm to solve general dynamic lot-sizing models with n periods in O(n log n) or O(n) time. Manage. Sci. 37, 909–925 (1991) · Zbl 0748.90011 · doi:10.1287/mnsc.37.8.909 |
| [13] | Feige U.: A threshold of ln(n) for approximating set-cover. J. ACM 45, 634–652 (1998) · Zbl 1065.68573 · doi:10.1145/285055.285059 |
| [14] | Geunes J., Romeijn H.E., Taaffe K.: Requirements planning with order selection flexibility. Oper. Res. 54, 394–401 (2006) · Zbl 1167.90485 · doi:10.1287/opre.1050.0255 |
| [15] | Goemans, M.X.: Approximate solutions of hard combinatorial problems, Lecture notes in the school of ASHCOMP (1996) |
| [16] | Goemans M.X., Williamson D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296–317 (1995) · Zbl 0834.68055 · doi:10.1137/S0097539793242618 |
| [17] | Hoesel A.V., Wagelmans A., Kolen A.: A dual algorithm for the economic lot-sizing problem. Eur. J. Oper. Res. 52, 315–325 (1991) · Zbl 0738.90022 · doi:10.1016/0377-2217(91)90166-S |
| [18] | Krarup, J., Bilde, O.: Plant location, set covering and economic lot sizing: an O(mn) algorithm for structured problems. In: Numerische Methoden Bei Optimierungsaufgaben, vol. 3, pp. 155–180 (1977) · Zbl 0364.90067 |
| [19] | Levi, R., Geunes, J., Romeijn, E.H., Shmoys, D.B.: Inventory and facility location models with market selection. In: Proceedings of the 12th IPCO, pp. 111–124, (2005) · Zbl 1119.90323 |
| [20] | Levi R., Roundy R.O., Shmoys D.B.: Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31, 267–284 (2006) · Zbl 1278.90026 · doi:10.1287/moor.1050.0178 |
| [21] | Levi R., Roundy R.O., Shmoys D.B., Sviridenko M.: A constant approximation algorithm for the one-warehouse multi-retailer problem. Manage. Sci. 54, 763–776 (2008) · Zbl 1232.90071 · doi:10.1287/mnsc.1070.0781 |
| [22] | Magnanti, T.L., Stratila, D.: Separable concave optimization approximately equals piecewise linear optimization. In: Proceedings of the 11th IPCO, pp. 234–243 (2004) · Zbl 1092.90533 |
| [23] | Magnanti, T.L., Stratila, D.: Strongly polynomial algorithms for concave cost combinatorial optimization problems. (2007) (in preparation) |
| [24] | Müller A., Stoyan D.: Comparison Methods for Stochastic Models and Risks. Wiley, London (2002) · Zbl 0999.60002 |
| [25] | Pochet Y., Wolsey L.A.: Lot-sizing with constant batches: formulation and valid inequalities. Math. Oper. Res. 18, 767–785 (1993) · Zbl 0808.90058 · doi:10.1287/moor.18.4.767 |
| [26] | van den Heuvel, W., Kundakcioglu, O.E., Geunes, J., Romeijn, H.E., Sharkey, T.C., Wagelmans, A.P.M.: Integrated market selection and production planning: complexity and solution approaches. Unpublished manuscript (2009) · Zbl 1254.90064 |
| [27] | Wagelmans A.P.M., van Hoesel C.P.M., Kolen A.: Economic lot-sizing: An O(n log n) algorithm that runs in linear time in the Wagner-Whitin case. Oper. Res. 40, 145–156 (1992) · Zbl 0771.90031 |
| [28] | Wagner H.M., Whitin T.M.: Dynamic version of the economic lot sizing model. Manage. Sci. 5, 89–96 (1958) · doi:10.1287/mnsc.5.1.89 |
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.
