Polyhedral results and valid inequalities for the continuous energy-constrained scheduling problem

Abstract : This paper addresses a scheduling problem involving a continuously-divisible cumulative resource with limited capacity. During its processing, each task requests 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 an increasing and pseudo-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 metadatas

https://hal.laas.fr/hal-01977452
Contributor : Christian Artigues <>
Submitted on : Thursday, January 10, 2019 - 5:09:29 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM

Links full text

Identifiers

Citation

Margaux Nattaf, Markó Horváth, 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-01977452⟩

Share

Metrics

Record views

73