IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v203y2018icp254-263.html
   My bibliography  Save this article

Energy-aware lot sizing problem: Complexity analysis and exact algorithms

Author

Listed:
  • Rapine, Christophe
  • Goisque, Guillaume
  • Akbalik, Ayse

Abstract

The single-item lot sizing problem under a periodic energy limitation is considered in this paper. Identical and parallel capacitated machines constitute the production system, each one consuming a certain amount of energy when being switched on, when reserved, and when producing. We consider a cost for starting-up the machines, a reservation cost to keep the machines ready for production, in addition to classical lot sizing costs, such as, joint setup cost, unit production cost and unit holding cost, all being time-dependent. Besides the classical lot sizing decisions of how much and in which periods to produce, we have to decide the number of machines to switch on and to switch off in each period. We show that this problem is NP-hard even under restricted conditions. In contrast, assuming stationary energy parameters, we propose two polynomial time dynamic programming algorithms to solve the problem to optimality. The first algorithm is proposed for the case with null setup cost, null reservation cost and null reservation energy consumption, and runs in O(M5T4) time, with M being the number of machines and T the number of periods. We show that we can extend this algorithm to solve the generalized version of the problem in time complexity O(M6T6).

Suggested Citation

  • Rapine, Christophe & Goisque, Guillaume & Akbalik, Ayse, 2018. "Energy-aware lot sizing problem: Complexity analysis and exact algorithms," International Journal of Production Economics, Elsevier, vol. 203(C), pages 254-263.
    • Handle: RePEc:eee:proeco:v:203:y:2018:i:c:p:254-263
    DOI: 10.1016/j.ijpe.2018.06.020
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527318302640
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2018.06.020?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Oussama Masmoudi & Alice Yalaoui & Yassine Ouazene & Hicham Chehade, 2017. "Lot-sizing in a multi-stage flow line production system with energy consideration," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1640-1663, March.
    2. Margaux Nattaf & Christian Artigues & Pierre Lopez & David Rivreau, 2016. "Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 459-492, March.
    3. Waldemarsson, Martin & Lidestam, Helene & Rudberg, Martin, 2013. "Including energy in supply chain planning at a pulp company," Applied Energy, Elsevier, vol. 112(C), pages 1056-1065.
    4. Gahm, Christian & Denz, Florian & Dirr, Martin & Tuma, Axel, 2016. "Energy-efficient scheduling in manufacturing companies: A review and research framework," European Journal of Operational Research, Elsevier, vol. 248(3), pages 744-757.
    5. Ozdamar, Linet & Birbil, Sevket Ilker, 1999. "A hierarchical planning system for energy intensive production environments," International Journal of Production Economics, Elsevier, vol. 58(2), pages 115-129, January.
    6. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    7. Uday S. Karmarkar & Sham Kekre & Sunder Kekre, 1987. "The Dynamic Lot-Sizing Problem with Startup and Reservation Costs," Operations Research, INFORMS, vol. 35(3), pages 389-398, June.
    8. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    9. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    10. Biel, K. & Glock, C. H., 2016. "Systematic literature review of decision support models for energy-efficient production planning," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 83071, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    11. Gabriel R. Bitran & Horacio H. Yanasse, 1982. "Computational Complexity of the Capacitated Lot Size Problem," Management Science, INFORMS, vol. 28(10), pages 1174-1186, October.
    12. Rapine, Christophe & Penz, Bernard & Gicquel, Céline & Akbalik, Ayse, 2018. "Capacity acquisition for the single-item lot sizing problem under energy constraints," Omega, Elsevier, vol. 81(C), pages 112-122.
    13. 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.
    14. Artigues, Christian & Lopez, Pierre & Haït, Alain, 2013. "The energy scheduling problem: Industrial case-study and constraint propagation techniques," International Journal of Production Economics, Elsevier, vol. 143(1), pages 13-23.
    15. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    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. Markus Hilbert & Andreas Dellnitz & Andreas Kleine, 2023. "Production planning under RTP, TOU and PPA considering a redox flow battery storage system," Annals of Operations Research, Springer, vol. 328(2), pages 1409-1436, September.
    2. Suzanne, Elodie & Absi, Nabil & Borodin, Valeria, 2020. "Towards circular economy in production planning: Challenges and opportunities," European Journal of Operational Research, Elsevier, vol. 287(1), pages 168-190.
    3. Hajo Terbrack & Thorsten Claus & Frank Herrmann, 2021. "Energy-Oriented Production Planning in Industry: A Systematic Literature Review and Classification Scheme," Sustainability, MDPI, vol. 13(23), pages 1-32, December.

    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. Rapine, Christophe & Penz, Bernard & Gicquel, Céline & Akbalik, Ayse, 2018. "Capacity acquisition for the single-item lot sizing problem under energy constraints," Omega, Elsevier, vol. 81(C), pages 112-122.
    2. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    3. Hajo Terbrack & Thorsten Claus & Frank Herrmann, 2021. "Energy-Oriented Production Planning in Industry: A Systematic Literature Review and Classification Scheme," Sustainability, MDPI, vol. 13(23), pages 1-32, December.
    4. Pan, Zhendong & Tang, Jiafu & Liu, Ou, 2009. "Capacitated dynamic lot sizing problems in closed-loop supply chain," European Journal of Operational Research, Elsevier, vol. 198(3), pages 810-821, November.
    5. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    6. Hnaien, Faicel & Afsar, Hasan Murat, 2017. "Robust single-item lot-sizing problems with discrete-scenario lead time," International Journal of Production Economics, Elsevier, vol. 185(C), pages 223-229.
    7. Jean-Philippe Gayon & Guillaume Massonnet & Christophe Rapine & Gautier Stauffer, 2017. "Fast Approximation Algorithms for the One-Warehouse Multi-Retailer Problem Under General Cost Structures and Capacity Constraints," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 854-875, August.
    8. Berk, Emre & Toy, Ayhan Ozgur & Hazir, Oncu, 2008. "Single item lot-sizing problem for a warm/cold process with immediate lost sales," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1251-1267, June.
    9. 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.
    10. Önal, Mehmet & van den Heuvel, Wilco & Dereli, Meryem Merve & Albey, Erinç, 2023. "Economic lot sizing problem with tank scheduling," European Journal of Operational Research, Elsevier, vol. 308(1), pages 166-182.
    11. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    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. Suzanne, Elodie & Absi, Nabil & Borodin, Valeria, 2020. "Towards circular economy in production planning: Challenges and opportunities," European Journal of Operational Research, Elsevier, vol. 287(1), pages 168-190.
    14. 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.
    15. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    16. Yevgenia Mikhaylidi & Hussein Naseraldin & Liron Yedidsion, 2015. "Operations scheduling under electricity time-varying prices," International Journal of Production Research, Taylor & Francis Journals, vol. 53(23), pages 7136-7157, December.
    17. Fink, Jiří & Hurink, Johann L., 2015. "Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses," European Journal of Operational Research, Elsevier, vol. 242(2), pages 644-650.
    18. Goisque, Guillaume & Rapine, Christophe, 2017. "An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels," European Journal of Operational Research, Elsevier, vol. 261(3), pages 918-928.
    19. Zhang, Zhi-Hai & Jiang, Hai & Pan, Xunzhang, 2012. "A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 140(1), pages 249-255.
    20. van Hoesel, C.P.M. & Romeijn, H.E. & Romero Morales, M.D. & Wagelmans, A., 2002. "Polynomial time algorithms for some multi-level lot-sizing problems with production capacities," Research Memorandum 018, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).

    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:eee:proeco:v:203:y:2018:i:c:p:254-263. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/ijpe .

    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.