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.
Type de document :
Communication dans un congrès
PMS: Project Management and Scheduling, Apr 2016, Valencia, Spain. 15th International Conference on Project Management and Scheduling, pp.94-97, 2016
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01313722
Contributeur : Rodolphe Giroudeau <>
Soumis le : mercredi 7 juin 2017 - 10:35:32
Dernière modification le : jeudi 26 octobre 2017 - 13:44:08
Document(s) archivé(s) le : vendredi 8 septembre 2017 - 12:27:36

Fichiers

PMS16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01313722, version 1
  • ARXIV : 1706.02200

Collections

Citation

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. 15th International Conference on Project Management and Scheduling, pp.94-97, 2016. 〈lirmm-01313722〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

42