Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions

Abstract : We consider a cumulative scheduling problem where a task duration and resource consumption are not fixed. The consumption profile of the task, which can vary continuously over time, is a decision variable of the problem to be determined and a task is completed as soon as the integration over its time window of a non-decreasing and continuous processing rate function of the consumption profile has reached a predefined amount of energy. The goal is to find a feasible schedule, which is an NP-hard problem. For the case where functions are concave and piecewise linear, we present two propagation algorithms. The first one is the adaptation to concave functions of the variant of the energetic reasoning previously established for linear functions. Furthermore, a full characterization of the relevant intervals for time-window adjustments is provided. The second algorithm combines a flow-based checker with time-bound adjustments derived from the timetable disjunctive reasoning for the cumulative constraint. Complementarity of the algorithms is assessed via their integration in a hybrid branch-and-bound and computational experiments on small-size instances.
Document type :
Journal articles
Complete list of metadatas

Cited literature [14 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01546131
Contributor : Margaux Nattaf <>
Submitted on : Friday, June 23, 2017 - 2:27:31 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Wednesday, January 10, 2018 - 10:10:15 PM

File

submission_constraint.pdf
Files produced by the author(s)

Identifiers

Citation

Margaux Nattaf, Christian Artigues, Pierre Lopez. Cumulative scheduling with variable task profiles and concave piecewise linear processing rate functions. Constraints, Springer Verlag, 2017, 22 (4), pp.530-547. ⟨10.1007/s10601-017-9271-4⟩. ⟨hal-01546131⟩

Share

Metrics

Record views

282

Files downloads

263