IDEAS home Printed from https://ideas.repec.org/p/ems/eureir/37650.html
   My bibliography  Save this paper

The Economic Lot-Sizing Problem with an Emission Constraint

Author

Listed:
  • Retel Helmrich, M.
  • Jans, R.F.
  • van den Heuvel, W.
  • Wagelmans, A.P.M.

Abstract

We consider a generalisation of the lot-sizing problem that includes an emission constraint. Besides the usual financial costs, there are emissions associated with production, keeping inventory and setting up the production process. Because the constraint on the emissions can be seen as a constraint on an alternative cost function, there is also a clear link with bi-objective optimisation. We show that lot-sizing with an emission constraint is NP-hard and propose several solution methods. First, we present a Lagrangian heuristic to provide a feasible solution and lower bound for the problem. For costs and emissions for which the zero inventory property is satisfied, we give a pseudo-polynomial algorithm, which can also be used to identify the complete Pareto frontier of the bi-objective lot-sizing problem. Furthermore, we present a fully polynomial time approximation scheme (FPTAS) for such costs and emissions and extend it to deal with general costs and emissions. Special attention is paid to an efficient implementation with an improved rounding technique to reduce the a posteriori gap, and a combination of the FPTASes and a heuristic lower bound. Extensive computational tests show that the Lagrangian heuristic gives solutions that are very close to the optimum. Moreover, the FPTASes have a much better performance in terms of their gap than the a priori imposed performance, and, especially if the heuristic’s lower bound is used, they are very fast.

Suggested Citation

  • Retel Helmrich, M. & Jans, R.F. & van den Heuvel, W. & Wagelmans, A.P.M., 2012. "The Economic Lot-Sizing Problem with an Emission Constraint," Econometric Institute Research Papers EI 2011-41, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
  • Handle: RePEc:ems:eureir:37650
    as

    Download full text from publisher

    File URL: https://repub.eur.nl/pub/37650/EI2012-41.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Heuvel, Wilco van den & Borm, Peter & Hamers, Herbert, 2007. "Economic lot-sizing games," European Journal of Operational Research, Elsevier, vol. 176(2), pages 1117-1130, January.
    2. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    3. Nimrod Megiddo, 1979. "Combinatorial Optimization with Rational Objective Functions," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 414-424, November.
    Full references (including those not matched with items on IDEAS)

    Citations

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


    Cited by:

    1. Harpreet Kaur & Surya Prakash Singh, 2019. "Sustainable procurement and logistics for disaster resilient supply chain," Annals of Operations Research, Springer, vol. 283(1), pages 309-354, December.
    2. Akbalik, Ayse & Rapine, Christophe, 2013. "The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases," European Journal of Operational Research, Elsevier, vol. 229(2), pages 353-363.
    3. H. Edwin Romeijn & Dolores Romero Morales & Wilco Van den Heuvel, 2014. "Computational complexity of finding Pareto efficient outcomes for biobjective lot‐sizing models," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(5), pages 386-402, August.
    4. Palak, Gökçe & Ekşioğlu, Sandra Duni & Geunes, Joseph, 2014. "Analyzing the impacts of carbon regulatory mechanisms on supplier and mode selection decisions: An application to a biofuel supply chain," International Journal of Production Economics, Elsevier, vol. 154(C), pages 198-216.
    5. Harpreet Kaur & Surya Prakash Singh, 2019. "Flexible dynamic sustainable procurement model," Annals of Operations Research, Springer, vol. 273(1), pages 651-691, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. van Hoesel, C.P.M. & Wagelmans, A., 2006. "On the p-coverage problem on the real line," Research Memorandum 044, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Wilco van den Heuvel & Semra Ağralı & Z. Caner Taşkın, 2023. "A Decomposition Algorithm for Single and Multiobjective Integrated Market Selection and Production Planning," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1439-1453, November.
    3. van den Heuvel, W. & Wagelmans, A.P.M., 2007. "Four equivalent lot-sizing models," Econometric Institute Research Papers EI 2007-30, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Wilco van den Heuvel & Albert P.M. Wagelmans, 2002. "A Note on Ending Inventory Valuation in Multiperiod Production Scheduling," Tinbergen Institute Discussion Papers 02-067/4, Tinbergen Institute.
    5. Siao-Leu Phouratsamay & Safia Kedad-Sidhoum & Fanny Pascual, 2021. "Coordination of a two-level supply chain with contracts," 4OR, Springer, vol. 19(2), pages 235-264, June.
    6. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    7. Steffen Rebennack & Ashwin Arulselvan & Lily Elefteriadou & Panos M. Pardalos, 2010. "Complexity analysis for maximum flow problems with arc reversals," Journal of Combinatorial Optimization, Springer, vol. 19(2), pages 200-216, February.
    8. Bart Smeulders & Laurens Cherchye & Bram De Rock & Frits C. R. Spieksma, 2013. "The Money Pump as a Measure of Revealed Preference Violations: A Comment," Journal of Political Economy, University of Chicago Press, vol. 121(6), pages 1248-1258.
    9. Bouchery, Yann & Hezarkhani, Behzad & Stauffer, Gautier, 2022. "Coalition formation and cost sharing for truck platooning," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 15-34.
    10. van den Heuvel, Wilco & Gutiérrez, José Miguel & Hwang, Hark-Chin, 2011. "Note on "An efficient approach for solving the lot-sizing problem with time-varying storage capacities"," European Journal of Operational Research, Elsevier, vol. 213(2), pages 455-457, September.
    11. Zhili Zhou & Yongpei Guan, 2013. "Two-stage stochastic lot-sizing problem under cost uncertainty," Annals of Operations Research, Springer, vol. 209(1), pages 207-230, October.
    12. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    13. 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.
    14. Hassin, Refael & Sarid, Anna, 2018. "Operations research applications of dichotomous search," European Journal of Operational Research, Elsevier, vol. 265(3), pages 795-812.
    15. J. Drechsel & A. Kimms, 2010. "The subcoalition-perfect core of cooperative games," Annals of Operations Research, Springer, vol. 181(1), pages 591-601, December.
    16. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.
    17. Karla E. Bourland & Candace Arai Yano, 1996. "Lot sizing when yields increase during the production run," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(8), pages 1035-1047, December.
    18. Martel, Alain & Gascon, Andre, 1998. "Dynamic lot-sizing with price changes and price-dependent holding costs," European Journal of Operational Research, Elsevier, vol. 111(1), pages 114-128, November.
    19. Pursals, Salvador Casadesús & Garzón, Federico Garriga, 2009. "Optimal building evacuation time considering evacuation routes," European Journal of Operational Research, Elsevier, vol. 192(2), pages 692-699, January.
    20. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.

    More about this item

    Keywords

    lot-sizing;

    Statistics

    Access and download statistics

    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:ems:eureir:37650. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: RePub (email available below). General contact details of provider: https://edirc.repec.org/data/feeurnl.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.