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

Sandra Ulrich Ngueveu (), Christian Artigues, Nabil Absi and Safia Kedad-Sidhoum
Additional contact information
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

Journal of Heuristics, 2022, vol. 28, issue 1, No 4, 93-120

Abstract: 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.

Keywords: Energy-aware scheduling; Piecewise linear costs; Storage resources; Matheuristic; Column generation; Lot sizing; Mixed integer programming; 90B05; 90B30; 90C39; 90C59 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-021-09486-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-021-09486-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-021-09486-w

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().