David Rivreau, Christian Artigues, Pierre Lopez, Margaux Nattaf, Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Laboratoire d'Ingéniérie des Systèmes Automatisés (LISA), Université d'Angers (UA), Université Catholique de l'Ouest (UCO), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), and Université de Toulouse (UT)
International audience; This paper addresses a scheduling problem with a continuously-divisible, cumulative 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 and continuous function. The goal is to find a feasible schedule, which is already NP-complete, and then to minimize the resource consumption. For the case where all functions are linear, we present two new Mixed Integer Linear Programs (MILP), as well as improvements of an existing formulation. We also present a detailed version of the adaptation of the well-known "left-shift/right-shift" satisfiability test for the cumulative constraint and the associated time-window adjustments to our problem. For this test, three ways of computing relevant intervals are described. Finally, a hybrid branch-and-bound using both the satisfiability test and the MILP is presented with a new heuristic for choosing the variable on which the branching is done. Computational experiments on randomly generated instances are reported in order to compare all of these solution methods.