Bounds and approximation results for scheduling coupled-tasks with compatibility constraints - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2016

Bounds and approximation results for scheduling coupled-tasks with compatibility constraints

Abstract

This article is devoted to propose some lower and upper bounds for the coupled-tasks scheduling problem in presence of compatibility constraints according to classical complexity hypothesis ($\mathcal{P} \neq \mathcal{NP}$, $\mathcal{ETH}$). Moreover, we develop an efficient polynomial-time approximation algorithm for the specific case for which the topology describing the compatibility constraints is a quasi split-graph.
Fichier principal
Vignette du fichier
PMS16.pdf (121.53 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01313722 , version 1 (07-06-2017)

Identifiers

Cite

Rodolphe Giroudeau, Jean-Claude König, Benoit Darties, Gilles Simonin. Bounds and approximation results for scheduling coupled-tasks with compatibility constraints. PMS: Project Management and Scheduling, Apr 2016, Valencia, Spain. pp.94-97. ⟨lirmm-01313722⟩
176 View
125 Download

Altmetric

Share

Gmail Facebook X LinkedIn More