×

Analysis of relaxations for the multi-item capacitated lot-sizing problem. (English) Zbl 0709.90030

Summary: The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP- hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.

MSC:

90B05 Inventory, storage, reservoirs
90C60 Abstract computational complexity for mathematical programming problems
90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C90 Applications of mathematical programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aikens, C. H., The optimal design of a physical distribution system on a multicommodity multiechelon network (1982), Knoxville, TN: The University of Tennessee, Knoxville, TN
[2] Aikens, C. H., Facility location models for distribution planning, Eur. J. Oper. Res., 22, 263-279 (1985) · Zbl 0583.90022 · doi:10.1016/0377-2217(85)90246-2
[3] Ali, A. I.; Helgason, R. V.; Kennington, J. L.; Hall, H., Computational comparison among three multicommodity network flow algorithms, Oper. Res., 23, 995-1000 (1980) · Zbl 0445.90086 · doi:10.1287/opre.28.4.995
[4] Ali, A. I.; Barnett, D.; Farhangian, K.; Kennington, J.; Mccarl, B.; Patty, B.; Shetty, B.; Wong, P., Multicommodity network problems: Applications and computations, IIE Trans., 16, 2, 127-134 (1984) · doi:10.1080/07408178408974677
[5] D. Atkins, A survey of lower bounding methodologies for production/inventory model, Ann. Oper. Res., this volume. · Zbl 0709.90032
[6] Bahl, H. C., Column generation based heuristic algorithm for multi-item scheduling, AIIE Trans., 15, 2, 136-141 (1983)
[7] Bahl, H. C.; Ritzman, L. P., A cyclical scheduling heuristic for lot sizing with capacity constraints, Int. J. Prod. Res., 22, 791-800 (1984) · Zbl 0542.90055 · doi:10.1080/00207548408942499
[8] Barany, I.; Van Roy, T. J.; Wolsey, L. A., Strong formulations for multi-item capacitated lot sizing, Manag. Sci., 30, 10, 1255-1261 (1984) · Zbl 0601.90037 · doi:10.1287/mnsc.30.10.1255
[9] Bertsekas, D. P.; Tseng, P., Relaxation methods for minimum cost network flow problems (1983), Cambridge, MA: MIT, Cambridge, MA
[10] Bertsekas, D. P.; Gafni, E. M., Projected Newton methods and optimization of multicommodity flows, IEEE Trans. Automatic Control AC, 28, 12, 1090-1096 (1983) · Zbl 0525.90042 · doi:10.1109/TAC.1983.1103183
[11] P.J. Billington, Multi-level lot-sizing with a bottleneck work center, Ph.D. Thesis, Graduate School of Business and Public Administration, Cornell University (1983).
[12] P.J. Billington, The capacitated lot-sizing problem (CLSP), review and extensions, Working Paper No. 84-13, College of Business Administration, Northeastern University (1984).
[13] Bitran, G. R.; Yanasse, H. H., Computational complexity of the capacitated lot size problem, Manag. Sci., 28, 1174-1186 (1982) · Zbl 0502.90046 · doi:10.1287/mnsc.28.10.1174
[14] Bitran, G. R.; Matsuo, H., The multi-item capacitated lot size problem: Error bounds of Manne’s formulations, Manag. Sci., 32, 350-359 (1986) · Zbl 0596.90043 · doi:10.1287/mnsc.32.3.350
[15] Blackburn, J. D.; Millen, R. A., Heuristic lot-sizing performance in a rolling-schedule environment, Decision Sci., 11, 691-701 (1980) · doi:10.1111/j.1540-5915.1980.tb01170.x
[16] Bowman, E. H., Production scheduling by the transportation method of linear programming, Oper. Res., 4, 100-103 (1956) · Zbl 1414.90147 · doi:10.1287/opre.4.1.100
[17] Cornuéjols, G.; Fisher, M. L.; Nemhauser, G. L., Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Manag. Sci., 23, 789-810 (1977) · Zbl 0361.90034 · doi:10.1287/mnsc.23.8.789
[18] Dantzig, G. B.; Van Slyke, R. M., Generalized upper bounding techniques, J. Comp. Syst. Sci., 1, 213-226 (1967) · Zbl 0162.23003 · doi:10.1016/S0022-0000(67)80015-1
[19] Dixon, P.; Silver, E. A., A heuristic solution procedure for the multi-item, single-level, limited capacity, lot-sizing problem, J. Oper. Management, 2, 1, 23-39 (1981) · doi:10.1016/0272-6963(81)90033-4
[20] Dogramaci, A.; Panayiotopoulos, J. C.; Adam, N. R., The dynamic lot-sizing problem for multiple items under limited capacity, AIIE Trans., 13, 4, 294-303 (1981) · doi:10.1080/05695558108974565
[21] Dzielinski, B. P.; Gomory, R. E., Optimal programming of lot sizes, inventories, and labor allocations, Manag. Sci., 11, 9, 874-890 (1965) · doi:10.1287/mnsc.11.9.874
[22] Eppen, G. D.; Martin, R. K., Solving multi-item capacitated lot-sizing problems using variable redefinition, Oper. Res., 35, 6, 832-848 (1987) · Zbl 0639.90046 · doi:10.1287/opre.35.6.832
[23] Evans, J. R., Network-based optimization algorithms for the capacitated multi-item lot sizing problem, Comp. Ind. Eng., 9, 3, 297-305 (1985) · doi:10.1016/0360-8352(85)90009-9
[24] A. Federgruen, A simple forward algorithm to solve general dynamic lot sizing models withn periods inO(n logn) orO(n) time, Graduate School of Business, Columbia University (1989).
[25] Florian, M.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Deterministic production planning: Algorithms and complexity, Manag. Sci., 26, 7, 669-679 (1980) · Zbl 0445.90025 · doi:10.1287/mnsc.26.7.669
[26] Florian, M.; Klein, M., Deterministic production planning with concave costs and capacity constraints, Manag. Sci., 18, 1, 12-20 (1971) · Zbl 0273.90023 · doi:10.1287/mnsc.18.1.12
[27] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. Quart., 3, 2, 95-110 (1956) · doi:10.1002/nav.3800030109
[28] Gabbay, H., Multi-stage production planning, Manag. Sci., 25, 1138-1148 (1979) · Zbl 0466.90035 · doi:10.1287/mnsc.25.11.1138
[29] Garey, M. R.; Johnson, D. S., Strong NP-completeness results: Motivation, examples and implications, J. ACM, 25, 499-508 (1978) · Zbl 0379.68035 · doi:10.1145/322077.322090
[30] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco: Freeman, San Francisco · Zbl 0411.68039
[31] Geoffrion, A. M., Lagrangian relaxation for integer programming, Math. Progr. Study, 2, 82-114 (1974) · Zbl 0395.90056 · doi:10.1007/BFb0120690
[32] Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by Benders decomposition, Manag. Sci., 20, 5, 822-844 (1974) · Zbl 0304.90122 · doi:10.1287/mnsc.20.5.822
[33] Geoffrion, A. M., Better distribution planning with computer models, Harvard Business Rev., 54, 4, 92-99 (1976)
[34] Glover, F.; Hultz, J.; Klingman, D.; Stutz, J., Generalized networks: A fundamental computer-based planning tool, Manag. Sci., 24, 12, 1209-1220 (1978) · doi:10.1287/mnsc.24.12.1209
[35] Graves, S. C., Using Lagrangian techniques to solve hierarchical production planning systems, Manag. Sci., 28, 3, 260-275 (1982) · Zbl 0488.90032 · doi:10.1287/mnsc.28.3.260
[36] M. Guignard and K. Opaswongkarn, Primal and dual approaches to single- and multi-commodity capacitated plant location problems, Technical Report No. 53, Department of Statistics, University of Pennsylvania (1983). · Zbl 0719.90051
[37] Hearn, D. W.; Lawphongpanich, S.; Ventura, J. A., Finiteness in restricted simplicial decomposition, Oper. Res. Lett., 4, 3, 125-130 (1985) · Zbl 0582.90078 · doi:10.1016/0167-6377(85)90016-1
[38] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Progr., 6, 1, 62-88 (1974) · Zbl 0284.90057 · doi:10.1007/BF01580223
[39] Holloway, C. A., An extension of the Frank and Wolfe method of feasible directions, Math. Progr., 6, 14-27 (1974) · Zbl 0283.90042 · doi:10.1007/BF01580219
[40] Kennington, J. L., A survey of linear cost multicommodity network flows, Oper. Res., 26, 209-236 (1978) · Zbl 0377.90097 · doi:10.1287/opre.26.2.209
[41] Kennington, J. L.; Helgason, R. V., Algorithms for Network Programming (1980), New York: Wiley, New York · Zbl 0502.90056
[42] Kleindorfer, P. R.; Newson, E. F.P., A lower bounding structure for lot-sizing scheduling problems, Oper. Res., 23, 2, 299-311 (1975) · Zbl 0304.90063 · doi:10.1287/opre.23.2.299
[43] Klincewicz, J. G., A large-scale distribution and location model, AT&T Tech. J., 64, 7, 1705-1730 (1985) · doi:10.1002/j.1538-7305.1985.tb00032.x
[44] Lambrecht, M. R.; Vanderveken, H., Heuristic procedures for the single operation, mulyi-item loading problem, AIIE Trans., 11, 4, 319-326 (1979) · doi:10.1080/05695557908974478
[45] Lasdon, L. S.; Terjung, R. C., An efficient algorithm for multi-item scheduling, Oper. Res., 19, 4, 946-969 (1971) · Zbl 0224.90039 · doi:10.1287/opre.19.4.946
[46] J. Maes and L.N. Van Wassenhove, Multi item single level capacitated dynamic lotsizing heuristics: A computational comparison (Part I: Static case), IIE Trans. (1986) 114-123.
[47] Manne, A. S., Programming of economic lot sizes, Manag. Sci., 4, 2, 115-135 (1958) · doi:10.1287/mnsc.4.2.115
[48] Martin, R. K., Generating alternative mixed integer programming models using variable redefinition, Oper. Res., 35, 6, 820-831 (1987) · Zbl 0638.90076 · doi:10.1287/opre.35.6.820
[49] Pochet, Y.; Wolsey, L. A., Lot-size models with backlogging: Strong reformulations and cutting planes (1986), Belgium: Université Catholique de Louvain, Belgium · Zbl 0663.90038
[50] Shan, Y.-S., A dynamic multicommodity network flow model for real time optimal rail freight car management (1985), Princeton, NJ: Civil Engineering Department, Princeton University, Princeton, NJ
[51] Srinivasan, V.; Thompson, G. L., Benefit-cost analysis of coding techniques for the primal transportation algorithm, J. ACM, 20, 194-213 (1973) · Zbl 0257.68034 · doi:10.1145/321752.321754
[52] Stoer, J.; Witzgall, C., Convexity and Optimization in Finite Dimensions I (1970), New York: Springer, New York · Zbl 0203.52203
[53] Thizy, J.-M.; Van Wassenhove, L. N., Lagrangian relaxation for the multi-item capacitated lotsizing: A heuristic implementation, IIE Trans., 17, 4, 308-313 (1985) · doi:10.1080/07408178508975308
[54] J.-M. Thizy, Analysis of Lagrangian decomposition for the multi-item capacitated lot-sizing problem, INFOR, to appear. · Zbl 0778.90008
[55] W.W. Trigeiro, A dual-based heuristic for the capacitated lot-sizing problem, Ph.D. Thesis Graduate School of Business and Public Administration, Cornell University (1985).
[56] Von Hohenbalken, B., Simplicial decomposition in nonlinear programming algorithms, Math. Progr., 13, 49-68 (1977) · Zbl 0362.90086 · doi:10.1007/BF01584323
[57] Wagner, H. M.; Whitin, T., Dynamic version of the economic lot size model, Manag. Sci., 5, 1, 89-96 (1958) · Zbl 0977.90500 · doi:10.1287/mnsc.5.1.89
[58] Zangwill, W. I., A backlogging model and a multi-echelon model of a dynamic economic lot size production system: A network approach, Manag. Sci., 15, 9, 506-527 (1969) · Zbl 0172.44603 · doi:10.1287/mnsc.15.9.506
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.