Complexity and Approximation for Scheduling Problem for Coupled-Tasks in Presence of Compatibility Tasks - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2010

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

Gilles Simonin
Methods, Algorithms for Operations REsearch
Rodolphe Giroudeau
Methods, Algorithms for Operations REsearch
CV
Jean-Claude König
Methods, Algorithms for Operations REsearch
CV

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.

Domains

Operations Research [math.OC]
Fichier principal
Vignette du fichier
PMS2010-Simonin.pdf (121.64 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Gilles Simonin  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00488279

Submitted on : Tuesday, June 1, 2010-4:22:32 PM

Last modification on : Friday, March 24, 2023-2:52:53 PM

Long-term archiving on : Friday, September 17, 2010-11:42:17 AM

Download

Dates and versions

lirmm-00488279 , version 1 (01-06-2010)

Identifiers

  • HAL Id : lirmm-00488279 , version 1

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS MAORE LIRMM MIPS UNIV-MONTPELLIER
133 View
149 Download

Share

More