Skip to main content
SpringerLink
Log in

Analysis of relaxations for the multi-item capacitated lot-sizing problem

  • Production Planning
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C.H. Aikens, The optimal design of a physical distribution system on a multicommodity multiechelon network, Ph.D. Thesis, The University of Tennessee, Knoxville, TN (1982).

    Google Scholar 

  2. C.H. Aikens, Facility location models for distribution planning, Eur. J. Oper. Res. 22(1985)263–279.

    Article  Google Scholar 

  3. A.I. Ali, R.V. Helgason, J.L. Kennington and H. Hall, Computational comparison among three multicommodity network flow algorithms, Oper. Res. 23(1980)995–1000.

    Article  Google Scholar 

  4. A.I. Ali, D. Barnett, K. Farhangian, J. Kennington, B. McCarl, B. Patty, B. Shetty and P. Wong, Multicommodity network problems: Applications and computations, IIE Trans. 16 (2) (1984)127–134.

    Article  Google Scholar 

  5. D. Atkins, A survey of lower bounding methodologies for production/inventory model, Ann. Oper. Res., this volume.

  6. H.C. Bahl, Column generation based heuristic algorithm for multi-item scheduling, AIIE Trans. 15 (2) (1983)136–141.

    Google Scholar 

  7. H.C. Bahl and L.P. Ritzman, A cyclical scheduling heuristic for lot sizing with capacity constraints, Int. J. Prod. Res. 22(1984)791–800.

    Article  Google Scholar 

  8. I. Barany, T.J. Van Roy and L.A. Wolsey, Strong formulations for multi-item capacitated lot sizing. Manag. Sci. 30 (10) (1984)1255–1261.

    Article  Google Scholar 

  9. D.P. Bertsekas and P. Tseng, Relaxation methods for minimum cost network flow problems, Technical Report LIDS-P-1339, MIT, Cambridge, MA (1983).

    Google Scholar 

  10. D.P. Bertsekas and E.M. Gafni, Projected Newton methods and optimization of multicommodity flows, IEEE Trans. Automatic Control AC28 (12) (1983) 1090–1096.

    Article  Google Scholar 

  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. G.R. Bitran and H.H. Yanasse, Computational complexity of the capacitated lot size problem, Manag. Sci. 28(1982)1174–1186.

    Article  Google Scholar 

  14. G.R. Bitran and H. Matsuo, The multi-item capacitated lot size problem: Error bounds of Manne's formulations, Manag. Sci. 32(1986)350–359.

    Article  Google Scholar 

  15. J.D. Blackburn and R.A. Millen, Heuristic lot-sizing performance in a rolling-schedule environment, Decision Sci. 11(1980)691–701.

    Article  Google Scholar 

  16. E.H. Bowman, Production scheduling by the transportation method of linear programming, Oper. Res. 4(1956)100–103.

    Article  Google Scholar 

  17. G. Cornuéjols, M.L. Fisher and G.L. Nemhauser, Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms, Manag. Sci. 23(1977)789–810.

    Article  Google Scholar 

  18. G.B. Dantzig and R.M. Van Slyke, Generalized upper bounding techniques, J. Comp. Syst. Sci. 1(1967)213–226.

    Article  Google Scholar 

  19. P. Dixon and E.A. Silver, A heuristic solution procedure for the multi-item, single-level, limited capacity, lot-sizing problem, J. Oper. Management 2 (1) (1981)23–39.

    Article  Google Scholar 

  20. A. Dogramaci, J.C. Panayiotopoulos and N.R. Adam, The dynamic lot-sizing problem for multiple items under limited capacity, AIIE Trans. 13 (4) (1981)294–303.

    Article  Google Scholar 

  21. B.P. Dzielinski and R.E. Gomory, Optimal programming of lot sizes, inventories, and labor allocations, Manag. Sci. 11 (9) (1965)874–890.

    Article  Google Scholar 

  22. G.D. Eppen and R.K. Martin, Solving multi-item capacitated lot-sizing problems using variable redefinition, Oper. Res. 35 (6) (1987)832–848.

    Article  Google Scholar 

  23. J.R. Evans, Network-based optimization algorithms for the capacitated multi-item lot sizing problem, Comp. Ind. Eng. 9 (3) (1985)297–305.

    Article  Google Scholar 

  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. M. Florian, J.K. Lenstra and A.H.G. Rinnooy Kan, Deterministic production planning: Algorithms and complexity, Manag. Sci. 26 (7) (1980)669–679.

    Article  Google Scholar 

  26. M. Florian and M. Klein, Deterministic production planning with concave costs and capacity constraints, Manag. Sci. 18 (1) (1971)12–20.

    Article  Google Scholar 

  27. M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Res. Logist. Quart. 3 (2) (1956)95–110.

    Article  Google Scholar 

  28. H. Gabbay, Multi-stage production planning, Manag. Sci. 25(1979)1138–1148.

    Article  Google Scholar 

  29. M.R. Garey and D.S. Johnson, Strong NP-completeness results: Motivation, examples and implications, J. ACM 25(1978)499–508.

    Article  Google Scholar 

  30. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

    Google Scholar 

  31. A.M. Geoffrion, Lagrangian relaxation for integer programming, Math. Progr. Study 2(1974)82–114.

    Article  Google Scholar 

  32. A.M. Geoffrion and G.W. Graves, Multicommodity distribution system design by Benders decomposition, Manag. Sci. 20 (5) (1974)822–844.

    Article  Google Scholar 

  33. A.M. Geoffrion, Better distribution planning with computer models, Harvard Business Rev. 54 (4) (1976)92–99.

    Google Scholar 

  34. F. Glover, J. Hultz, D. Klingman and J. Stutz, Generalized networks: A fundamental computer-based planning tool, Manag. Sci. 24 (12) (1978)1209–1220.

    Article  Google Scholar 

  35. S.C. Graves, Using Lagrangian techniques to solve hierarchical production planning systems, Manag. Sci. 28 (3) (1982)260–275.

    Article  Google Scholar 

  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).

  37. D.W. Hearn, S. Lawphongpanich and J.A. Ventura, Finiteness in restricted simplicial decomposition, Oper. Res. Lett. 4 (3) (1985)125–130.

    Article  Google Scholar 

  38. M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization, Math. Progr. 6 (1) (1974)62–88.

    Article  Google Scholar 

  39. C.A. Holloway, An extension of the Frank and Wolfe method of feasible directions, Math. Progr. 6(1974)14–27.

    Article  Google Scholar 

  40. J.L. Kennington, A survey of linear cost multicommodity network flows, Oper. Res. 26(1978)209–236.

    Article  Google Scholar 

  41. J.L. Kennington and R.V. Helgason,Algorithms for Network Programming (Wiley, New York, 1980).

    Google Scholar 

  42. P.R. Kleindorfer and E.F.P. Newson, A lower bounding structure for lot-sizing scheduling problems, Oper. Res. 23 (2) (1975)299–311.

    Article  Google Scholar 

  43. J.G. Klincewicz, A large-scale distribution and location model. AT&T Tech. J. 64 (7) (1985) 1705–1730.

    Article  Google Scholar 

  44. M.R. Lambrecht and H. Vanderveken, Heuristic procedures for the single operation, mulyi-item loading problem, AIIE Trans. 11 (4) (1979)319–326.

    Article  Google Scholar 

  45. L.S. Lasdon and R.C. Terjung, An efficient algorithm for multi-item scheduling, Oper. Res. 19 (4) (1971)946–969.

    Article  Google Scholar 

  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. A.S. Manne, Programming of economic lot sizes, Manag. Sci. 4 (2) (1958)115–135.

    Article  Google Scholar 

  48. R.K. Martin, Generating alternative mixed integer programming models using variable redefinition, Oper. Res. 35 (6) (1987)820–831.

    Article  Google Scholar 

  49. Y. Pochet and L.A. Wolsey, Lot-size models with backlogging: Strong reformulations and cutting planes, Technical Report, Université Catholique de Louvain, Belgium (1986).

    Google Scholar 

  50. Y.-S. Shan, A dynamic multicommodity network flow model for real time optimal rail freight car management, Ph.D. Thesis, Civil Engineering Department, Princeton University, Princeton, NJ (1985).

    Google Scholar 

  51. V. Srinivasan and G.L. Thompson, Benefit-cost analysis of coding techniques for the primal transportation algorithm. J. ACM 20(1973)194–213.

    Article  Google Scholar 

  52. J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions I, Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen, Band 163 (Springer, New York, 1970).

    Book  Google Scholar 

  53. J.-M. Thizy and L.N. Van Wassenhove, Lagrangian relaxation for the multi-item capacitated lotsizing: A heuristic implementation, IIE Trans. 17 (4) (1985)308–313.

    Article  Google Scholar 

  54. J.-M. Thizy, Analysis of Lagrangian decomposition for the multi-item capacitated lot-sizing problem, INFOR, to appear.

  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. B. Von Hohenbalken, Simplicial decomposition in nonlinear programming algorithms, Math. Progr. 13(1977)49–68.

    Article  Google Scholar 

  57. H.M. Wagner and T. Whitin, Dynamic version of the economic lot size model, Manag. Sci. 5 (1) (1958)89–96.

    Article  Google Scholar 

  58. W.I. Zangwill, A backlogging model and a multi-echelon model of a dynamic economic lot size production system: A network approach, Manag. Sci. 15 (9) (1969)506–527.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Business and Economics, Washington State University, 99163, Pullman, Washington, USA

    W. -H. Chen & J. -M. Thizy

  2. Faculty of Administration, University of Ottawa, K1N 6N5, Ottawa, Ontario, Canada

    W. -H. Chen & J. -M. Thizy

Authors
  1. W. -H. Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. -M. Thizy
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Supported by NSF Grant ECS-8518970 and NSERC Grant OGP 0042197.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, W.H., Thizy, J.M. Analysis of relaxations for the multi-item capacitated lot-sizing problem. Ann Oper Res 26, 29–72 (1990). https://doi.org/10.1007/BF02248584

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02248584

Keywords

Search

Navigation