IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v28y2022i1d10.1007_s10732-021-09486-w.html
   My bibliography  Save this article

Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs

Author

Listed:
  • Sandra Ulrich Ngueveu

    (Université de Toulouse, CNRS, INP)

  • Christian Artigues

    (Université de Toulouse, CNRS)

  • Nabil Absi

    (Mines Saint-Etienne and UMR CNRS 6158 LIMOS)

  • Safia Kedad-Sidhoum

    (CNAM-CEDRIC)

Abstract

This paper considers the problem of scheduling a set of time- and energy-constrained preemptive tasks on a discrete time horizon. At each time period, the total energy required by the tasks that are in process can be provided by two energy sources: a reversible one and a non-reversible one. The non-reversible energy source can provide an unlimited amount of energy for a given period but at the expense of a time-dependent piecewise linear cost. The reversible energy source is a storage resource. The goal is to schedule each task preemptively inside its time window and to dispatch the required energy to the sources at each time period, while satisfying the reversible source capacity constraints and minimizing the total cost. We propose a mixed integer linear program of pseudo-polynomial size to solve this NP-hard problem. Acknowledging the limits of this model for problem instances of modest size, we propose an iterative decomposition matheuristic to compute an upper bound. The method relies on an efficient branch-and-price method or on a local search procedure to solve the scheduling problem without storage. The energy source allocation problem for a fixed schedule can in turn be solved efficiently by dynamic programming as a particular lot-sizing problem. We also propose a lower bound obtained by solving the linear programming relaxation of a new extended formulation by column generation. Experimental results show the quality of the bounds compared to the ones obtained using mixed integer linear program.

Suggested Citation

  • Sandra Ulrich Ngueveu & Christian Artigues & Nabil Absi & Safia Kedad-Sidhoum, 2022. "Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs," Journal of Heuristics, Springer, vol. 28(1), pages 93-120, February.
  • Handle: RePEc:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-021-09486-w
    DOI: 10.1007/s10732-021-09486-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-021-09486-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-021-09486-w?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. Sourd, Francis & Rogerie, Jerome, 2005. "Continuous filling and emptying of storage systems in constraint-based scheduling," European Journal of Operational Research, Elsevier, vol. 165(2), pages 510-524, September.
    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. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    4. Klaus Neumann & Christoph Schwindt, 2003. "Project scheduling with inventory constraints," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 56(3), pages 513-533, January.
    5. Dong X. Shaw & Albert P. M. Wagelmans, 1998. "An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs," Management Science, INFORMS, vol. 44(6), pages 831-838, June.
    6. Meng, Lexuan & Sanseverino, Eleonora Riva & Luna, Adriana & Dragicevic, Tomislav & Vasquez, Juan C. & Guerrero, Josep M., 2016. "Microgrid supervisory controllers and energy management systems: A literature review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 60(C), pages 1263-1273.
    7. Olatomiwa, Lanre & Mekhilef, Saad & Ismail, M.S. & Moghavvemi, M., 2016. "Energy management strategies in hybrid renewable energy systems: A review," Renewable and Sustainable Energy Reviews, Elsevier, vol. 62(C), pages 821-835.
    8. Zia, Muhammad Fahad & Elbouchikhi, Elhoussin & Benbouzid, Mohamed, 2018. "Microgrids energy management systems: A critical review on methods, solutions, and prospects," Applied Energy, Elsevier, vol. 222(C), pages 1033-1055.
    9. Ahmet B. Keha & Ismael R. de Farias & George L. Nemhauser, 2006. "A Branch-and-Cut Algorithm Without Binary Variables for Nonconvex Piecewise Linear Optimization," Operations Research, INFORMS, vol. 54(5), pages 847-858, October.
    Full references (including those not matched with items on IDEAS)

    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. Leonori, Stefano & Martino, Alessio & Frattale Mascioli, Fabio Massimo & Rizzi, Antonello, 2020. "Microgrid Energy Management Systems Design by Computational Intelligence Techniques," Applied Energy, Elsevier, vol. 277(C).
    2. Roslan, M.F. & Hannan, M.A. & Ker, Pin Jern & Uddin, M.N., 2019. "Microgrid control methods toward achieving sustainable energy management," Applied Energy, Elsevier, vol. 240(C), pages 583-607.
    3. Sadaqat Ali & Zhixue Zheng & Michel Aillerie & Jean-Paul Sawicki & Marie-Cécile Péra & Daniel Hissel, 2021. "A Review of DC Microgrid Energy Management Systems Dedicated to Residential Applications," Energies, MDPI, vol. 14(14), pages 1-26, July.
    4. Danny Espín-Sarzosa & Rodrigo Palma-Behnke & Oscar Núñez-Mata, 2020. "Energy Management Systems for Microgrids: Main Existing Trends in Centralized Control Architectures," Energies, MDPI, vol. 13(3), pages 1-32, January.
    5. Polimeni, Simone & Moretti, Luca & Martelli, Emanuele & Leva, Sonia & Manzolini, Giampaolo, 2023. "A novel stochastic model for flexible unit commitment of off-grid microgrids," Applied Energy, Elsevier, vol. 331(C).
    6. Younes Zahraoui & Ibrahim Alhamrouni & Saad Mekhilef & M. Reyasudin Basir Khan & Mehdi Seyedmahmoudian & Alex Stojcevski & Ben Horan, 2021. "Energy Management System in Microgrids: A Comprehensive Review," Sustainability, MDPI, vol. 13(19), pages 1-33, September.
    7. Manzano, J.M. & Salvador, J.R. & Romaine, J.B. & Alvarado-Barrios, L., 2022. "Economic predictive control for isolated microgrids based on real world demand/renewable energy data and forecast errors," Renewable Energy, Elsevier, vol. 194(C), pages 647-658.
    8. Katja Sirviö & Kimmo Kauhaniemi & Aushiq Ali Memon & Hannu Laaksonen & Lauri Kumpulainen, 2020. "Functional Analysis of the Microgrid Concept Applied to Case Studies of the Sundom Smart Grid," Energies, MDPI, vol. 13(16), pages 1-31, August.
    9. Raya-Armenta, Jose Maurilio & Bazmohammadi, Najmeh & Avina-Cervantes, Juan Gabriel & Sáez, Doris & Vasquez, Juan C. & Guerrero, Josep M., 2021. "Energy management system optimization in islanded microgrids: An overview and future trends," Renewable and Sustainable Energy Reviews, Elsevier, vol. 149(C).
    10. Luis Fernando Grisales-Noreña & Carlos Andrés Ramos-Paja & Daniel Gonzalez-Montoya & Gerardo Alcalá & Quetzalcoatl Hernandez-Escobedo, 2020. "Energy Management in PV Based Microgrids Designed for the Universidad Nacional de Colombia," Sustainability, MDPI, vol. 12(3), pages 1-24, February.
    11. Zia, Muhammad Fahad & Elbouchikhi, Elhoussin & Benbouzid, Mohamed, 2018. "Microgrids energy management systems: A critical review on methods, solutions, and prospects," Applied Energy, Elsevier, vol. 222(C), pages 1033-1055.
    12. Mischa Ahrens & Fabian Kern & Hartmut Schmeck, 2021. "Strategies for an Adaptive Control System to Improve Power Grid Resilience with Smart Buildings," Energies, MDPI, vol. 14(15), pages 1-29, July.
    13. Shanmugarajah Vinothine & Lidula N. Widanagama Arachchige & Athula D. Rajapakse & Roshani Kaluthanthrige, 2022. "Microgrid Energy Management and Methods for Managing Forecast Uncertainties," Energies, MDPI, vol. 15(22), pages 1-22, November.
    14. Daniel J. Sambor & Michelle Wilber & Erin Whitney & Mark Z. Jacobson, 2020. "Development of a Tool for Optimizing Solar and Battery Storage for Container Farming in a Remote Arctic Microgrid," Energies, MDPI, vol. 13(19), pages 1-18, October.
    15. Álex Omar Topa Gavilema & José Domingo Álvarez & José Luis Torres Moreno & Manuel Pérez García, 2021. "Towards Optimal Management in Microgrids: An Overview," Energies, MDPI, vol. 14(16), pages 1-25, August.
    16. Yamashita, Daniela Yassuda & Vechiu, Ionel & Gaubert, Jean-Paul, 2020. "A review of hierarchical control for building microgrids," Renewable and Sustainable Energy Reviews, Elsevier, vol. 118(C).
    17. Konneh, Keifa Vamba & Adewuyi, Oludamilare Bode & Gamil, Mahmoud M. & Fazli, Agha Mohammad & Senjyu, Tomonobu, 2023. "A scenario-based multi-attribute decision making approach for optimal design of a hybrid off-grid system," Energy, Elsevier, vol. 265(C).
    18. Fontenot, Hannah & Dong, Bing, 2019. "Modeling and control of building-integrated microgrids for optimal energy management – A review," Applied Energy, Elsevier, vol. 254(C).
    19. Ou, Jinwen & Feng, Jiejian, 2019. "Production lot-sizing with dynamic capacity adjustment," European Journal of Operational Research, Elsevier, vol. 272(1), pages 261-269.
    20. Konneh, Keifa Vamba & Masrur, Hasan & Konneh, David A. & Senjyu, Tomonobu, 2022. "Independent or complementary power system configuration: A decision making approach for sustainable electrification of an urban environment in Sierra Leone," Energy, Elsevier, vol. 239(PD).

    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:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-021-09486-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.