Polyhedral results and valid inequalities for the Continuous Energy-Constrained Scheduling Problem - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2019

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

Résumé

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.
Fichier principal
Vignette du fichier
rapport_LAAS.pdf (342.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01391403 , version 1 (03-11-2016)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More