Complexity and Approximation for Scheduling Problem for Coupled-Tasks in Presence of Compatibility Tasks

Gilles Simonin 1 Rodolphe Giroudeau 1 Jean-Claude König 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper, we study a scheduling problem with compled-tasks in presence of incompatible constraint. We give complexity results and a polynomial-time approximation for a specific problem when the compatibility graph has different topologies.
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00488279
Contributor : Gilles Simonin <>
Submitted on : Tuesday, June 1, 2010 - 4:22:32 PM
Last modification on : Monday, February 11, 2019 - 11:50:15 AM
Long-term archiving on: Friday, September 17, 2010 - 11:42:17 AM

File

PMS2010-Simonin.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00488279, version 1

Collections

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König. Complexity and Approximation for Scheduling Problem for Coupled-Tasks in Presence of Compatibility Tasks. PMS: Project Management and Scheduling, Apr 2010, Tours, France. pp.371-374. ⟨lirmm-00488279⟩

Share

Metrics

Record views

234

Files downloads

242