Single item lot sizing problems.

*(English)*Zbl 1077.90001Summary: A state-of-the-art of a particular planning problem, the Single Item Lot Sizing Problem (SILSP), is given for its uncapacitated and capacitated versions. First classes of lot sizing problems are briefly surveyed. Various solution methods for the Uncapacitated Single Item Lot Sizing Problem (USILSP) are reviewed. Four different mathematical programming formulations of the classical problem are presented. Different extensions for real-world applications of this problem are discussed. Complexity results of the Capacitated Single Item Lot Sizing Problem (CSILSP) are given together with its different formulations and solution techniques.

##### MSC:

90B05 | Inventory, storage, reservoirs |

90C59 | Approximation methods and heuristics in mathematical programming |

90C60 | Abstract computational complexity for mathematical programming problems |

##### Software:

bc-prod
PDF
BibTeX
XML
Cite

\textit{N. Brahimi} et al., Eur. J. Oper. Res. 168, No. 1, 1--16 (2006; Zbl 1077.90001)

Full Text:
DOI

##### References:

[1] | Afentakis, P.; Gavish, B., Optimal lot-sizing for complex product structures, Operations research, 34, 237-249, (1986) · Zbl 0602.90048 |

[2] | Aggarwal, A.; Park, J.K., Improved algorithms for economic lot-size problems, Operations research, 41, 549-571, (1993) · Zbl 0820.90035 |

[3] | Baker, K.R.; Dixon, P.; Magazine, M.J.; Silver, E.A., An algorithm for the dynamic lot-size problem with time-varying production capacity constraints, Management science, 24, 1710-1720, (1978) · Zbl 0491.90033 |

[4] | Barany, I.; Van Roy, T.J.; Strong, W.L.A., Formulations for multi-item capacitated lot-sizing, Management science, 30, 1255-1261, (1984) · Zbl 0601.90037 |

[5] | Belvaux, G.; Wolsey, L.A., BC-PROD: A specialized branch-and-cut system for lot-sizing problems, Management science, 46, 724-738, (2000) · Zbl 1231.90384 |

[6] | Belvaux, G.; Wolsey, L.A., Modelling practical lot-sizing problems as mixed-integer programs, Management science, 47, 7, 993-1007, (2001) · Zbl 1232.90169 |

[7] | Bhatnagar, R.; Chandra, P.; Goyal, S.K., Models for multi-plant coordination, European journal of operational research, 67, 2, 141-160, (1993) |

[8] | Billington, P.J.; McClain, J.O.; Thomas, L.J., Heuristics for multilevel lot-sizing with a bottleneck, Management science, 32, 8, 989-1006, (1986) · Zbl 0596.90038 |

[9] | Bitran, G.R.; Matsuo, H., The multi-item capacitated lot size problem: error bounds of manne’s formulation, Management science, 32, 3, 350-359, (1986) · Zbl 0596.90043 |

[10] | G.R. Bitran, D. Tirupati, Hierarchical Production Planning, Handbooks on Operations Research and Management Science, vol. 4, North Holand, Amsterdam, 1993, pp. 523-568 (Chapter 10) |

[11] | Bitran, G.R.; Yanasse, H.H., Computational complexity of the capacitated lot size problem, Management science, 28, 10, 1174-1186, (1982) · Zbl 0502.90046 |

[12] | N. Brahimi, S. Dauzère-Pérès, N. Najid, A. Nordli, A Lagrangian relaxation heuristic for the capacitated single item lot sizing problem with time windows, in: Sixth Workshop on: Models and Algorithms for Planning and Scheduling Problems, Aussois, 2003, pp. 105-106 |

[13] | Cattrysse, D.; Maes, J.; Van Wassenhove, L.N., Set partitioning and column generation heuristics for capacitated dynamic lot-sizing, European journal of operational research, 46, 38-48, (1990) · Zbl 0711.90019 |

[14] | Chen, H.D.; Hearn, D.; Lee, C.Y., A new dynamic programming algorithm for the single item capacitated dynamic lot size model, Journal of global optimization, 4, 285-300, (1994) · Zbl 0812.90037 |

[15] | Chen, W.H.; Thizy, J.M., Analysis of relaxations for the multi-item capacitated lot-sizing problem, Annals of operations research, 26, 29-72, (1990) · Zbl 0709.90030 |

[16] | Cho, K.K.; Kim, K.H.; Kim, C.S., A heuristic lot sizing algorithm for a gt cell, Computers and industrial engineering, 26, 1, 1-9, (1994) |

[17] | Chung, C.; Lin, C.H.M., An O(T^2) algorithm for the NI/G/NI/ND capacitated lot size problem, Management science, 34, 420-426, (1988) · Zbl 0668.90015 |

[18] | Chung, C.S.; Flynn, J.; Lin, C.-H., An effective algorithm for the capacitated single item lot size problem, European journal of operational research, 75, 427-440, (1994) · Zbl 0806.90054 |

[19] | Covert, R.P.; Philip, G.C., An EOQ model for items with Weibull distribution deterioration, AIIE transactions, 5, 323-326, (1973) |

[20] | S. Dauzère-Pérès, N. Brahimi, N. Najid, A. Nordli, The single-item lot sizing problem with time windows, Technical Report 02/4/AUTO, Ecole des Mines de Nantes, France, April 2002 |

[21] | S. Dauzère-Pérès, J.B. Lasserre, An Integrated Approach in Production Planning and Scheduling, Lecture Notes in Economics and Mathematical Systems, vol. 411, Springer Verlag, Berlin, 1994 · Zbl 0816.90070 |

[22] | Dauzère-Pérès, S.; Lasserre, J.B., Integration of lot sizing and scheduling decisions in a job-shop, European journal of operational research, 75, 413-426, (1994) · Zbl 0806.90062 |

[23] | Dauzère-Pérès, S.; Lasserre, J.B., On the importance of sequencing decisions in production planning and scheduling, International transactions in operational research, 9, 6, 779-793, (2002) · Zbl 1044.90034 |

[24] | Dellaert, N.; Jeunet, J.; Jonard, N., A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs, International journal of production economics, 68, 241-257, (2000) |

[25] | Diaby, M.; Bahl, H.C.; Karwan, M.H.; Zionts, S., A Lagrangian relaxation approach for very large scale capacitated lot-sizing, Management science, 38, 1329-1339, (1992) · Zbl 0758.90020 |

[26] | Dixon, P.S.; Silver, E.A., A heuristic solution procedure for the multi-item, single-level, limited-capacity, lot-sizing problem, Journal of operations management, 2, 23-39, (1982) |

[27] | Drexl, A.; Kimms, A., Lot sizing and scheduling–survey and extensions, European journal of operational research, 99, 221-235, (1997) · Zbl 0923.90067 |

[28] | O. Du Merle, J.L. Goffin, C. Trouiller, J.P. Vial, A Lagrangian relaxation of the capacitated multi-item lot sizing problem solved with an interior point cutting plane algorithm, in: Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, Kluwer Academic Publishers, 1999 · Zbl 1052.90070 |

[29] | Elmaghraby, S.E., The economic lot scheduling problem (ELSP): review and extensions, Management science, 24, 587-598, (1978) · Zbl 0376.90051 |

[30] | Eppen, G.D.; Gould, F.J.; Pashigian, B.P., Extensions of the planning horizon theorem in the dynamic lot size problem, Management science, 15, 268-277, (1969) · Zbl 0172.44102 |

[31] | Eppen, G.D.; Martin, R.K., Solving multi-item lot-sizing problems using variable redefinition, Operations research, 35, 832-848, (1987) · Zbl 0639.90046 |

[32] | Evans, J.R., An efficient implementation of the wagner-whitin algorithm for dynamic lot-sizing, Journal of operations management, 5, 2, 229-235, (1985) |

[33] | 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, Management science, 37, 909-925, (1991) · Zbl 0748.90011 |

[34] | Fleischmann, B., The discrete lot-sizing and scheduling problem, European journal of operational research, 44, 337-348, (1990) · Zbl 0689.90043 |

[35] | Florian, M.; Klein, M., Deterministic production planning with concave costs and capacity constraints, Management science, 18, 12-20, (1971) · Zbl 0273.90023 |

[36] | Florian, M.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Deterministic production planning: algorithms and complexity, Management science, 26, 669-679, (1980) · Zbl 0445.90025 |

[37] | Friedman, Y.; Hoch, Y., A dynamic lot-size model with inventory deterioration, Infor, 16, 183-188, (1978) · Zbl 0385.90042 |

[38] | Gavish, B.; Johnson, R.E., A fully polynomial approximation scheme for single-product scheduling in a finite capacity facility, Operations research, 38, 70-83, (1990) · Zbl 0714.90050 |

[39] | Ghare, P.M.; Shrader, G.F., A model for exponentially decaying inventories, Journal of industrial engineering, 14, 238-243, (1963) |

[40] | Golany, B.; Yang, J.; Yu, G., Economic lot-sizing with remanufacturing options, IIE transactions, 33, 995-1003, (2001) |

[41] | Gopalakrishnan, M.; Ding, K.; Bourjolly, J.M.; Mohan, S., A tabu-search heuristic for the capacitated lot-sizing problem with set-up carryover, Management science, 47, 6, 851-863, (2001) · Zbl 1232.90181 |

[42] | S.C. Graves, Manufacturing planning and control, available from: <http://web.mit.edu/sgraves/www/ProdPlanCh.PDF>, 1999 |

[43] | E. Gutiérrez, W. Hernandez, G.A. Süer, Genetic algorithms in capacitated lot sizing decisions, in: Computer Research Conference, 2001 |

[44] | Gutiérrez, J.; Sedeno-Noda, A.; Colebrook, M.; Sicilia, J., A new characterization for the dynamic lot size problem with bounded inventory, Computers and operations research, 30, 3, 383-395, (2001) · Zbl 1029.90006 |

[45] | K. Haase, U. Kohlmorgen, Parallel genetic algorithm for the capacitated lot-sizing problem, in: Operations Research Proceedings, Springer-Verlag, 1995, pp. 370-375 |

[46] | Hanssmann, F., Operations research in production and inventory control, (1962), John Wiley · Zbl 0115.38203 |

[47] | Hariga, M., Optimal EOQ models for deteriorating items with time-varying demand, Journal of operations research society, 47, 1228-1246, (1996) · Zbl 0871.90028 |

[48] | Harris, F.W., How many parts to make at once, The magazine of management, 10, 135-136, (1913) |

[49] | Hindi, K.S., Solving the single-item, capacitated dynamic lot-sizing problem with startup and reservation costs by tabu search, Computers and industrial engineering, 28, 4, 701-707, (1995) |

[50] | Hsu, V.N., Dynamic economic lot size model with perishable inventory, Management science, 46, 8, 1159-1169, (2000) · Zbl 1232.90059 |

[51] | Hsu, W.L., On the general feasibility test of scheduling lot sizes for several products on one machine, Management science, 29, 93-105, (1983) · Zbl 0508.90050 |

[52] | Karimi, B.; Fatemi Ghomi, S.M.T.; Wilson, J.M., The capacitated lot sizing problem: A review of models and algorithms, Omega, 31, 5, 365-378, (2003) |

[53] | Katok, E.; Lewis, H.S.; Harrison, T.P., Lot sizing in general assembly systems with setup costs, setup times and multiple constrained resources, Management science, 44, 859-877, (1998) · Zbl 0989.90047 |

[54] | Kimms, A., A genetic algorithm for multi-level, multi-machine lot sizing and scheduling, Computers and operations research, 26, 829-848, (1999) · Zbl 0957.90026 |

[55] | J. Krarup, O. Bilde, Plant location, set covering and economic lot size: An O(mn)-algorithm for structured problems, in: International Series of Numerical Mathematics, vol. 36, Birkhaeuser Verlag, 1977, pp. 155-186 · Zbl 0364.90067 |

[56] | Kuik, R.; Solomon, M.; Van Wassenhove, L.N., Batching decisions: structure and models, European journal of operational research, 75, 243-263, (1994) |

[57] | Lambrecht, M.R.; Vanderveken, H., Heuristic procedures for the single operation multi-item loading problem, AIIE transactions, 11, 319-326, (1979) |

[58] | Lasserre, J.B., An integrated model for job-shop planning and scheduling, Management science, 38, 1201-1211, (1992) · Zbl 0761.90062 |

[59] | Lee, C.Y.; Çetinkaya, S.; Wagelmans, A.P., A dynamic lot-sizing model with demand time windows, Management science, 47, 10, 1384-1395, (2001) · Zbl 1232.90189 |

[60] | Leung, J.M.; Magnanti, T.L.; Vachani, R., Facets and algorithms for capacitated lot sizing, Mathematical programming, 45, 331-359, (1989) · Zbl 0681.90060 |

[61] | M. Loparic, H. Marchand, L.A. Wolsey, Dynamic knapsack sets and capacitated lot-sizing, Technical Report 47, Catholique de Louvain, Center for Operations Research and Economics, 2000 · Zbl 1030.90102 |

[62] | Lopez, M.A.; Kingsmans, B.G., The economic lot scheduling problem: theory and practice, International journal of production economics, 23, 147-164, (1991) |

[63] | Lotfi, V.; Yoon, Y.-S., An algorithm for the single-item capacitated lot-sizing problem with concave production and holding costs, Journal of operational research society, 45, 8, 934-941, (1994) · Zbl 0809.90064 |

[64] | Love, S.F., Bounded production and inventory models with piecewise concave costs, Management science, 20, 3, 313-318, (1973) · Zbl 0322.90028 |

[65] | Lozano, S.; Larraneta, J.; Onieva, L., Primal-dual approach to the single level capacitated lot-sizing problem, European journal of operational research, 51, 354-366, (1991) · Zbl 0743.90042 |

[66] | Z. Lu. Planification hièrarchise et optimisation des systèmes logistiques avec flux inverses. Ph.D. thesis, Ecole des Mines de Nantes, France, 2003 |

[67] | Lundin, R.A.; Morton, T.E., Planning horizons for the dynamic lot size model: zabel vs. protective procedures and computational results, Operations research, 23, 711-734, (1975) · Zbl 0317.90028 |

[68] | Maes, J.; McClain, J.O.; Wassenhove, L.V., Multilevel capacitated lotsizing complexity and lp-based heuristics, European journal of operational research, 53, 2, 131-148, (1991) · Zbl 0734.90036 |

[69] | Maes, J.; Van Wassenhove, L.N., Multi-item single-level capacitated dynamic lot-sizing heuristic: A computational comparison (part I: static case), IIE transactions, 18, 114-123, (1986) |

[70] | Maes, J.; Van Wassenhove, L.N., Multi-item single-level capacitated dynamic lot-sizing heuristic: A computational comparison (part II: rolling horizons), IIE transactions, 18, 2, 124-129, (1986) |

[71] | Maes, J.; Van Wassenhove, L.N., Multi-item single-level capacitated dynamic lot-sizing heuristics: A general review, Journal of operational research society, 39, 11, 991-1004, (1988) · Zbl 0655.90018 |

[72] | Manne, A.S., Programming of economic lot sizes, Management science, 4, 115-135, (1958) |

[73] | C. Mercé, H. Hétreux, G. Fontan, Aggregate and Detailed Planning, Concept et Outils pour les Systèmes de Production of Automatisation-Production, Cépadués-Editions, 1997, pp. 23-43 (Chapter 2) |

[74] | Millar, H.H.; Yang, M., Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering, International journal of production economics, 34, 1-15, (1994) |

[75] | Miller, A.J.; Nemhauser, G.L.; Savelsbergh, M.W., On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra, European journal of operational research, 125, 2, 298-315, (2000) · Zbl 0952.90028 |

[76] | A.J. Miller, G.L. Nemhauser, M.W. Savelsbergh, Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut, Technical Report 39, Université Catholique de Louvain–Center for Operations Research and Economics, 2000 |

[77] | A.J. Miller, L.A. Wolsey, Discrete lot-sizing and convex integer programming, Technical Report 8, Université Catholique de Louvain–Center for Operations Research and Economics, 2001 |

[78] | Nahmias, S., Perishable inventory theory: A review, Operations research, 30, 680-708, (1982) · Zbl 0486.90033 |

[79] | Özdamar, L.; Barbarosoglu, G., An integrated Lagrangian relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem, International journal of production economics, 68, 3, 319-331, (2000) |

[80] | Papachristos, S.; Skouri, K., An optimal replenishment policy for deteriorating items with time-varying demand and partial–exponential type–backlogging, Operations research letters, 27, 175-184, (2000) · Zbl 1096.90518 |

[81] | A.S. Pereira, F. Carvalho, J. Pedroso, M. Constantino, Iterated local search and tabu search for a discrete lot sizing and scheduling problem, in: Proceeding of the Fourth Meta-heuristics International Conference, 2001, pp. 697-701 |

[82] | Pochet, Y.; Wolsey, L.A., Lot-size models with backlogging: strong reformulations and cutting planes, Mathematical programming, 40, 317-335, (1988) · Zbl 0663.90038 |

[83] | Pochet, Y.; Wolsey, L.A., Solving multiitem lotsizing problems using strong cutting planes, Management science, 37, 53, (1991) · Zbl 0727.90034 |

[84] | Pochet, Y.; Wolsey, L.A., Polyhedra for lot-sizing with wagner-whitin costs, Mathematical programming, 67, 297-323, (1994) · Zbl 0822.90049 |

[85] | T. Qian, P.C. Jones, Y. Ye, Worst case analysis of forward Wagner-Whitin algorithm with rolling horizons, available from: http://citeseer.nj.nec.com/qian96worst.html, 1996 |

[86] | Rajagopalan, S., Deterministic capacity expansion under deterioration, Management science, 38, 525-539, (1992) · Zbl 0825.90337 |

[87] | Richter, K.; Sombrutzki, M., Remanufacturing planning for the reverse wagner/whitin models, European journal of operational research, 121, 304-315, (2000) · Zbl 0951.91034 |

[88] | Rogers, J., A computational approach to the economic lot scheduling problem, Management science, 4, 264-291, (1958) |

[89] | M. Salomon, Deterministic Lot Sizing Models for Production Planning, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, New York, 1991 · Zbl 0761.90054 |

[90] | Salomon, M.; Kroon, L.G.; Kuik, R.; Van Wassenhove, L.N., Some extensions of the discrete lotsizing and scheduling problem, Management science, 37, 801-812, (1991) · Zbl 0742.90039 |

[91] | Salomon, M.; Kuik, R.; Van Wassenhove, L.N., Statistical search methods for lot-sizing problems, Annals of operations research, 41, 453-468, (1993) · Zbl 0778.90017 |

[92] | M. Sambasivam, C.P. Schmidt, A solution procedure to solve uncapacitated lot sizing for multi-plant, multi-period problems with inter-plant transfers, Technical report, University of Putra Malaysia, Faculty of Economics and Management, 2000 |

[93] | Sandbothe, R.A.; Thompson, G.L., A forward algorithm for the capacitated lot size model with stockouts, Operations research, 38, 3, 474-486, (1990) · Zbl 0727.90031 |

[94] | Shaw, D.X.; Wagelmans, A.P., An algorithm for single-item capacitated economic lot sizing with piecewise linear production costs and general holding costs, Management science, 44, 6, 831-838, (1998) · Zbl 0989.90051 |

[95] | Simpson, V.P., Optimum solution structure for a repairable inventory problem, Operations research, 26, 270-281, (1978) · Zbl 0377.90040 |

[96] | A.T. Staggemeier, A.R. Clark, A survey of lot-sizing and scheduling models, in: 23rd Annual Symposium of the Brazilian Operational Research Society (SOBRAPO), Campos do Jordao SP, Brazil, 2001, pp. 938-947 |

[97] | Tempelmeier, H.; Derstroff, M., A Lagrangian-based heuristic for dynamic multilevel multi-item constrained lotsizing with setup times, Management science, 42, 738-757, (1996) · Zbl 0881.90045 |

[98] | Thizy, J.M.; Van Wassenhove, L.N., A subgradient algorithm for the multi-item capacitated lot-sizing problem, IIE transactions, 18, 114-123, (1986) |

[99] | Trigeiro, W.W.; Thomas, L.J.; McClain, J.O., Capacitated lot sizing with set-up times, Management science, 35, 353-366, (1989) |

[100] | C.A. Van Eijl, A polyhedral approach to the discrete lot-sizing and scheduling problem, Ph.D. thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology, 1996 |

[101] | Van Hoesel, C.P.; Wagelmans, A.P., An O(T3) algorithm for the economic lot-sizing problem with constant capacities, Management science, 42, 142-150, (1996) · Zbl 0851.90058 |

[102] | Van Hoesel, C.P.; Wagelmans, A.P., Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems, Mathematics of operations research, 26, 2, 339-357, (2001) · Zbl 1082.90532 |

[103] | Van Hoesel, S.; Kuik, R.; Salomon, M.; Van Wassenhove, L.N., The single item discrete lot-sizing and scheduling problem: optimization by linear and dynamic programming, Discrete mathematics, 48, 289-303, (1994) · Zbl 0793.90018 |

[104] | Vanderbeck, F., Lot-sizing with start-up times, Management science, 44, 10, 1409-1425, (1998) · Zbl 0989.90069 |

[105] | Wagelmans, A.; Van Hoesel, S.; Kolen, A., Economic lot sizing: an O\((n \log n)\) that runs in linear time in the wagner-whitin case, Operations research, 40, 1, S145-S156, (1992) · Zbl 0771.90031 |

[106] | Wagner, H.M.; Whitin, T.M., Dynamic version of the economic lot size model, Management science, 5, 1, 89-96, (1958) · Zbl 0977.90500 |

[107] | Wolsey, L.A., Progress with single-item lot-sizing, Journal of operational research, 86, 395-401, (1995) · Zbl 0914.90105 |

[108] | Yao, M.J.; Elmaghraby, S.E., The economic lot scheduling problem under power-of-two policy, Computers and mathematics with applications, 41, 1379-1393, (2001) · Zbl 0980.90030 |

[109] | Zabel, E., Some generalizations of an inventory planning horizon theorem, Management science, 10, 465-471, (1964) |

[110] | Zangwill, W., A backlogging model and a multi-echelon model of a dynamic economic lot size production system- a network approach, Management science, 15, 506-527, (1969) · Zbl 0172.44603 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.