Scheduling under non-reversible energy sources

Abstract : In this paper, we address a preemptive scheduling problem involving multiple non-reversible energy sources. To the classical scheduling issue, an additional decision level is added regarding the selection of the energy source used to satisfy the total power demand of tasks processed at each instant. Different non-reversible energy sources are available, with different characteristics in terms of efficiency and power range. The objective is to identify the best combination between scheduling and energy resource utilization that minimizes the total energy cost of the project. Non-linear efficiency functions used to compute energy costs are bounded from above and below by two piecewise-linear curves, yielding two instances of a scheduling problem with a piecewise-linear objective that can be solved separately. For the piecewise-linear scheduling problem, we show that the problem involving multiple sources is equivalent to a single-source problem, the particular case of a linear function is polynomially solvable, and the case with a piecewise-linear function with two pieces is NP-hard. A pseudo-polynomial size time-indexed mixed-integer linear formulation of the problem and its Dantzig-Wolfe decomposition yielding an extended formulation are presented. A branch-and-price procedure is proposed to solve the extended formulation. The formulations are compared on a set of scheduling instances, considering partly realistic efficiency functions.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01163925
Contributor : Sandra Ulrich Ngueveu <>
Submitted on : Monday, June 15, 2015 - 5:21:59 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Tuesday, April 25, 2017 - 8:24:39 AM

File

ArticlePGMO.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01163925, version 1

Citation

Sandra Ulrich Ngueveu, Christian Artigues, Pierre Lopez. Scheduling under non-reversible energy sources. Discrete Applied Mathematics, Elsevier, 2016, 208, pp. 98-113. ⟨hal-01163925⟩

Share

Metrics

Record views

691

Files downloads

833