EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2224. More powerful energetic reasoning using redundant resources for the Cumulative Scheduling Problems

Invited abstract in session TC-60: Advanced heuristics for machine scheduling, stream Project Management and Scheduling.

Tuesday, 12:30-14:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Kristina Kumbria
Laboratoire Heudiasyc, Université de Technologie de Compiègne
2. Jacques Carlier
Laboratoire Heudiasyc, Université de Technologie de Compiègne
3. Antoine Jouglet
Université de Technologie de Compiègne, Heudiasyc UMR CNRS 7253
4. Abderrahim SAHLI
UGE, ESIEE Paris

Abstract

In this presentation, we are dealing with the Cumulative Scheduling Problems(CuSP). In the CuSP-decision, we are given a set I of n non-preemptive tasks, meaning that once a task begins execution, it cannot be interrupted until completion. A constant amount m of a given resource is available over the time horizon to process the tasks. Each task i has a release date r_i, a processing time p_i, and a deadline d_i. The task i must be executed within its time window [r_i, d_i], and throughout its execution it requires a constant known amount c_i of resources. The objective of this decision problem is to detect infeasibility. Until now, for this problem, the most efficient algorithm is based on energy reasoning. We have already proposed a more powerful energetic reasoning by solving a tripartition problem and built a checker by using a Dynamic Programming method.
In the CuSP-optimization, the deadline d_i is replaced by the tail q_i which is equal to C_max-d_i and the objective is to find the minimal makespan C_max. The energetic lower bound corresponds to the minimal value for which infeasibility may not be detected. We can solve this problem by using the checker already proposed for the CuSP-decision. We also improved the efficiency of the method by introducing redundant resources. Computation results confirm the efficiency of the proposed methods.

Keywords

Status: accepted

Back to the list of papers