IDEAS home Printed from
   My bibliography  Save this article

Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems


  • Stephen C. Graves

    (Massachusetts Institute of Technology)


This paper proposes and tests a procedure for decomposing a large scale production planning problem modeled as a mixed-integer linear program. We interpret this decomposition in the context of Hax and Meal's hierarchical framework for production planning. The procedure decomposes the production planning problem into two subproblems which correspond to the aggregate planning subproblem and a disaggregation subproblem in the Hax-Meal framework. The linking mechanism for these two subproblems is an inventory consistency relationship which is priced out by a set of Lagrange multipliers. The best values for the multipliers are found by an iterative procedure which may be interpreted as a feedback mechanism in the Hax-Meal framework. At each iteration, the procedure finds both a lower bound on the optimal value to the production planning problem and a feasible solution from which an upper bound is obtained. Our computational tests show that the best feasible solution found from this procedure is very close to optimal. For thirty-six test problems the percentage deviation from optimality never exceeds 4.4%, and the average percentage deviation is 2.2%. In addition, these best feasible solutions dominate the corresponding solutions obtained by a hierarchical procedure.

Suggested Citation

  • Stephen C. Graves, 1982. "Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems," Management Science, INFORMS, vol. 28(3), pages 260-275, March.
  • Handle: RePEc:inm:ormnsc:v:28:y:1982:i:3:p:260-275

    Download full text from publisher

    File URL:
    Download Restriction: no


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. Xue, Guisen & Felix Offodile, O. & Zhou, Hong & Troutt, Marvin D., 2011. "Integrated production planning with sequence-dependent family setup times," International Journal of Production Economics, Elsevier, vol. 131(2), pages 674-681, June.
    2. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    3. Peiling Wu & Joseph C. Hartman & George R. Wilson, 2005. "An Integrated Model and Solution Approach for Fleet Sizing with Heterogeneous Assets," Transportation Science, INFORMS, vol. 39(1), pages 87-103, February.
    4. Caridi, Maria & Sianesi, Andrea, 2000. "Multi-agent systems in production planning and control: An application to the scheduling of mixed-model assembly lines," International Journal of Production Economics, Elsevier, vol. 68(1), pages 29-42, October.
    5. Wang, Wei & Wang, Dingwei & Ip, W. H., 1999. "JIT production planning approach with fuzzy due date for OKP manufacturing systems," International Journal of Production Economics, Elsevier, vol. 58(2), pages 209-215, January.
    6. Diaby, Moustapha, 2000. "Integrated batch size and setup reduction decisions in multi-product, dynamic manufacturing environments," International Journal of Production Economics, Elsevier, vol. 67(3), pages 219-233, October.
    7. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    8. Huang, Hai-Jun & Xu, Gang, 1998. "Aggregate scheduling and network solving of multi-stage and multi-item manufacturing systems," European Journal of Operational Research, Elsevier, vol. 105(1), pages 52-65, February.
    9. repec:spr:annopr:v:242:y:2016:i:2:d:10.1007_s10479-013-1526-x is not listed on IDEAS
    10. Lee, L. H. & Chew, E. P. & Ng, T. S., 2005. "Production planning with approved vendor matrices for a hard-disk drive manufacturer," European Journal of Operational Research, Elsevier, vol. 162(2), pages 310-324, April.
    11. Ng, T.S. & Lee, L.H. & Chew, E.P., 2006. "Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1117-1140, December.
    12. Jaya Singhal & Kalyan Singhal, 2008. "A Noniterative Algorithm for the Linear-Quadratic Profit-Maximization Model for Smoothing Multiproduct Production," INFORMS Journal on Computing, INFORMS, vol. 20(2), pages 169-178, May.
    13. Xu, Haoxuan & Gong, Yeming (Yale) & Chu, Chengbin & Zhang, Jinlong, 2017. "Dynamic lot-sizing models for retailers with online channels," International Journal of Production Economics, Elsevier, vol. 183(PA), pages 171-184.
    14. Samaddar, Subhashish & Rabinowitz, Gad & Zhang, Guoqiang Peter, 2005. "An experimental analysis of solution performance in a resource sharing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 165(1), pages 139-156, August.
    15. Selcuk, B. & Fransoo, J.C. & De Kok, A.G., 2006. "The effect of updating lead times on the performance of hierarchical planning systems," International Journal of Production Economics, Elsevier, vol. 104(2), pages 427-440, December.
    16. Tom Vogel & Bernardo Almada-Lobo & Christian Almeder, 2017. "Integrated versus hierarchical approach to aggregate production planning and master production scheduling," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 193-229, January.
    17. Schneewei[beta], Christoph, 1995. "Hierarchical structures in organisations: A conceptual framework," European Journal of Operational Research, Elsevier, vol. 86(1), pages 4-31, October.
    18. Kopanos, Georgios M. & Méndez, Carlos A. & Puigjaner, Luis, 2010. "MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry," European Journal of Operational Research, Elsevier, vol. 207(2), pages 644-655, December.
    19. Shapiro, Jeremy F., 1939-, 1998. "Bottom-up vs. top-down approaches to supply chain management and modeling," Working papers WP 4017-98., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    20. Fumero, Francesca & Vercellis, Carlo, 1997. "Integrating distribution, machine assignment and lot-sizing via Lagrangean relaxation," International Journal of Production Economics, Elsevier, vol. 49(1), pages 45-54, March.
    21. Barbarosoglu, Gulay & Ozgur, Demet, 1999. "Hierarchical design of an integrated production and 2-echelon distribution system," European Journal of Operational Research, Elsevier, vol. 118(3), pages 464-484, November.


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:28:y:1982:i:3:p:260-275. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.