Skip to Main content Skip to Navigation
Journal articles

Polyhedral results and valid inequalities for the Continuous Energy-Constrained Scheduling Problem

Abstract : This paper addresses a scheduling problem with a cumulative, continuously-divisible and renewable resource with limited capacity. During its processing, each task consumes a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with a non-decreasing, continuous and linear efficiency function. The goal is to minimize the resource consumption. The paper focuses on an event based mixed integer linear program, providing several valid inequalities which are used to improve the performance of the model. Furthermore, we give a minimal description of the polytope of all feasible assignments to the on/off binary variable for a single activity along with a dedicated separation algorithm. Computational experiments are reported in order to show the effectiveness of the results.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01391403
Contributor : Margaux Nattaf Connect in order to contact the contributor
Submitted on : Thursday, November 3, 2016 - 11:44:30 AM
Last modification on : Monday, July 4, 2022 - 10:12:25 AM
Long-term archiving on: : Saturday, February 4, 2017 - 1:27:30 PM

File

rapport_LAAS.pdf
Files produced by the author(s)

Identifiers

Citation

Margaux Nattaf, Tamás Kis, Christian Artigues, Pierre Lopez. Polyhedral results and valid inequalities for the Continuous Energy-Constrained Scheduling Problem. Discrete Applied Mathematics, Elsevier, 2019, 258, pp.188-203. ⟨10.1016/J.DAM.2018.11.008⟩. ⟨hal-01391403⟩

Share

Metrics

Record views

187

Files downloads

196