Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions

Margaux Nattaf (), Christian Artigues (), Pierre Lopez () and David Rivreau ()
Additional contact information
Margaux Nattaf: CNRS, LAAS
Christian Artigues: CNRS, LAAS
Pierre Lopez: CNRS, LAAS
David Rivreau: LUNAM Université, Université Catholique de l’Ouest, LISA

OR Spectrum: Quantitative Approaches in Management, 2016, vol. 38, issue 2, No 8, 459-492

Abstract: Abstract 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.

Keywords: Continuous scheduling; Continuous resources; Linear efficiency functions; Energy constraints; Energetic reasoning; Branching scheme; Mixed-integer programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s00291-015-0423-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:orspec:v:38:y:2016:i:2:d:10.1007_s00291-015-0423-x

Ordering information: This journal article can be ordered from
http://www.springer. ... research/journal/291

DOI: 10.1007/s00291-015-0423-x

Access Statistics for this article

OR Spectrum: Quantitative Approaches in Management is currently edited by Rainer Kolisch

More articles in OR Spectrum: Quantitative Approaches in Management from Springer, Gesellschaft für Operations Research e.V.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().