IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v28y1982i3p260-275.html
   My bibliography  Save this article

Using Lagrangean Techniques to Solve Hierarchical Production Planning Problems

Author

Listed:
  • Stephen C. Graves

    (Massachusetts Institute of Technology)

Abstract

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
    DOI: 10.1287/mnsc.28.3.260
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.28.3.260
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.28.3.260?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Citations

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


    Cited by:

    1. 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.
    2. 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.
    3. Awi Federgruen & Michal Tzur, 1993. "The dynamic lot‐sizing model with backlogging: A simple o(n log n) algorithm and minimal forecast horizon procedure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 459-478, June.
    4. Long Gao & Jim (Junmin) Shi & Michael F. Gorman & Ting Luo, 2020. "Business Analytics for Intermodal Capacity Management," Manufacturing & Service Operations Management, INFORMS, vol. 22(2), pages 310-329, March.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Ichimura, Takaya, 1996. "The elements and functions of hierarchical scheduling system of order production," International Journal of Production Economics, Elsevier, vol. 44(1-2), pages 73-81, June.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. Yongjian Li & Xiaoqiang Cai & Lei Xu & Wenxia Yang, 2016. "Heuristic approach on dynamic lot-sizing model for durable products with end-of-use constraints," Annals of Operations Research, Springer, vol. 242(2), pages 265-283, July.
    19. 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.
    20. 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.
    21. Schneewei[beta], Christoph, 1995. "Hierarchical structures in organisations: A conceptual framework," European Journal of Operational Research, Elsevier, vol. 86(1), pages 4-31, October.
    22. 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.
    23. 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.
    24. 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.

    Corrections

    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.

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

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.