Propagation of Idle Times Costs for Fixed Job Scheduling

Ruixin Wang 1 Nicolas Barnier 1
1 ENAC - Ecole Nationale de l'Aviation Civile
Abstract : —We present a new global constraint to propagate idle times costs for the Fixed Job Scheduling (FJS) problem, in particular to minimize their variance so as to optimize the robustness of solutions w.r.t. schedule deviations. The propagation of this constraint is based on the computation of the shortest path in the compatibility directed acyclic graph of each resource to obtain an exact lower bound. It ensures Bound Consistency on the resource cost in polynomial time, as well as the filtering of the resource variables associated with compatible tasks. We show on tailored FJS problems and real instances of the airport Gate Allocation Problem (a variant of the FJS problem) that this new constraint provides significant improvements in terms of number of backtracks and computation time, up to orders of magnitude in some cases.
Keywords : robustness optimization constraint Fixed job scheduling
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download
https://hal-enac.archives-ouvertes.fr/hal-01859777
Contributor : Nicolas Barnier <>
Submitted on : Wednesday, August 22, 2018 - 3:45:16 PM
Last modification on : Sunday, February 10, 2019 - 4:14:44 PM
Long-term archiving on: Friday, November 23, 2018 - 6:23:56 PM

File

ictai2018.pdf
Files produced by the author(s)

Identifiers

Collections

ENAC | OPTIM

Citation

Ruixin Wang, Nicolas Barnier. Propagation of Idle Times Costs for Fixed Job Scheduling. ICTAI 2018, 30th International Conference on Tools with Artificial Intelligence, Nov 2018, Volos, Greece. pp.ISBN: 978-1-5386-7450-5, ⟨10.1109/ICTAI.2018.00113⟩. ⟨hal-01859777⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

133

Files downloads

62