Skip to Main content Skip to Navigation
Reports

2-cover definition for a coupled-tasks scheduling problem

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 : This paper presents a scheduling problem with coupled-tasks in presence of a compatibility graph on a mono processor. We investigate a specific configuration, in which the coupled-tasks possess an idle time equal to 2. The complexity of these problems will be studied according to the presence or absence of triangles in the compatibility graph. As an extended matching, we propose a polynomial-time algorithm which consists in minimizing the number of non-covered vertices, by covering vertices with edges or paths of length two in the compatibility graph. This type of covering will be denoted 2-cover technique. According on the compatibility graph type, the 2-cover technique provides an 13/12-approximation or 10/9-approximation algorithm.
Document type :
Reports
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00355048
Contributor : Gilles Simonin <>
Submitted on : Wednesday, January 21, 2009 - 5:28:33 PM
Last modification on : Monday, February 11, 2019 - 11:50:15 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 6:33:56 PM

File

2-recouvrement_Rapport.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00355048, version 1

Citation

Gilles Simonin, Rodolphe Giroudeau, Jean-Claude König. 2-cover definition for a coupled-tasks scheduling problem. RR-09003, 2009. ⟨lirmm-00355048v1⟩

Share

Metrics

Record views

20

Files downloads

11