Approximation algorithm for constrained coupled-tasks scheduling problem

Abstract : We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01101208
Contributor : Rodolphe Giroudeau <>
Submitted on : Thursday, January 8, 2015 - 10:17:37 AM
Last modification on : Friday, June 14, 2019 - 6:31:06 PM

Identifiers

Citation

Gilles Simonin, Benoit Darties, Jean-Claude König, Rodolphe Giroudeau. Approximation algorithm for constrained coupled-tasks scheduling problem. CoDIT: Control, Decision and Information Technologies, Nov 2014, Metz, France. pp.110-112, ⟨10.1109/CoDIT.2014.6996877⟩. ⟨lirmm-01101208⟩

Share

Metrics

Record views

422