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

The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations

Author

Listed:
  • Gabriel R. Bitran

    (Alfred P. Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02138)

  • Hirofumi Matsuo

    (Graduate School of Business, University of Texas, Austin, Texas 78712)

Abstract

We discuss an approximation scheme for the multi-item lot size problem. It is based on an optimal basic solution of a linear programming problem derived from the original problem. The approximate solution is obtained by taking a linear convex combination of the optimal solution of the linear programming problem. We express error bounds of the approximation as a function of some parameters that can be easily estimated in practice. When set-up times are positive, the approximation may result in an infeasible solution. We take the same approach to show that the infeasibility of the approximation is small. The analysis is extended to a variable capacity problem with overtime. As an auxiliary result, we provide a bound on the duality gap of the Lagrangian dual problem.

Suggested Citation

  • Gabriel R. Bitran & Hirofumi Matsuo, 1986. "The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations," Management Science, INFORMS, vol. 32(3), pages 350-359, March.
    • Handle: RePEc:inm:ormnsc:v:32:y:1986:i:3:p:350-359
    DOI: 10.1287/mnsc.32.3.350
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.32.3.350
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.32.3.350?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. Marshall Fisher & Kamalini Ramdas & Yu-Sheng Zheng, 2001. "Ending Inventory Valuation in Multiperiod Production Scheduling," Management Science, INFORMS, vol. 47(5), pages 679-692, May.
    2. Drexl, Andreas & Haase, Knut, 1992. "A new type of model for multi-item capacitated dynamic lotsizing and scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 286, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Kimms, A., 1996. "Multi-level, single-machine lot sizing and scheduling (with initial inventory)," European Journal of Operational Research, Elsevier, vol. 89(1), pages 86-99, February.
    4. 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.
    5. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-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.
    6. Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    7. Haase, Knut & Kimms, Alf, 1996. "Lot sizing and scheduling with sequence dependent setup costs and times and efficient rescheduling opportunities," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 393, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    8. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    9. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    10. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    11. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    12. Riane, F. & Artiba, A. & Iassinovski, S., 2001. "An integrated production planning and scheduling system for hybrid flowshop organizations," International Journal of Production Economics, Elsevier, vol. 74(1-3), pages 33-48, December.
    13. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    14. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    15. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.

    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:32:y:1986:i:3:p:350-359. 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.