Algorithms to compute the energetic lower bounds of the cumulative scheduling problem

Jacques Carlier (), Antoine Jouglet () and Abderrahim Sahli ()
Additional contact information
Jacques Carlier: Sorbonne Universités, Université de Technologie de Compiègne
Antoine Jouglet: Sorbonne Universités, Université de Technologie de Compiègne
Abderrahim Sahli: Univ Gustave Eiffel, ESIEE Paris, COSYS/GRETTIA

Annals of Operations Research, 2024, vol. 337, issue 2, No 8, 683-713

Abstract: Abstract The aim of this paper is to propose efficient algorithms for computing the energetic lower bounds of the cumulative sheduling problem. So we have to schedule in a minimal makespan a set of non preemptive tasks on a resource with a given capacity. A task has a release date, a processing time and a tail and requires a given amount of the resource capacity during its processing. The energetic lower bound is the largest value of the makespan such that the energetic reasoning check cannot detect unfeasability. We report some algorithms to practically compute this lower bound with efficient complexity. These algorithms rely on iterative augmentations of $$C_{max}$$ C max until the cumulative constraint or the energetic constraint is satisfied. Our Computational results show their practical efficiencies.

Keywords: Scheduling; Energetic reasoning; Lower bounds; Algorithms (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05596-9 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:annopr:v:337:y:2024:i:2:d:10.1007_s10479-023-05596-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05596-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().