Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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

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 MSC 90B05 MSC 90B30 MSC 90C39 MSC 90C59
Complete list of metadata
Contributor : Sandra Ulrich Ngueveu <>
Submitted on : Wednesday, September 8, 2021 - 11:18:39 AM
Last modification on : Thursday, September 16, 2021 - 4:48:10 PM


Files produced by the author(s)


  • HAL Id : hal-03337821, version 1


Sandra Ulrich Ngueveu, Christian Artigues, Nabil Absi, Safia Kedad-Sidhoum. Lower and upper bounds for scheduling energy-consuming tasks with storage resources and piecewise linear costs. 2021. ⟨hal-03337821⟩



Record views


Files downloads