Proof of NP-completeness for a scheduling problem with coupled-tasks and compatibility graph

Gilles Simonin

Reports

Proof of NP-completeness for a scheduling problem with coupled-tasks and compatibility graph

Gilles Simonin ¹

1 APR - Algorithmes et Performance des Réseaux

LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier

Résumé : Preuve de NP-complétude d'un problème d'ordonnancement avec tâches-couplées et graphe de compatibilité.

Keywords : compatibility graph coupled-tasks complexity scheduling operational research

Document type :

Reports

Domain :

Computer Science [cs] / Operations Research [cs.RO]

Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00262286
Contributor : Gilles Simonin <>
Submitted on : Tuesday, March 11, 2008 - 12:17:20 PM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on: : Friday, May 21, 2010 - 12:09:32 AM

Proof of NP-completeness for a scheduling problem with coupled-tasks and compatibility graph

File

Identifiers

Collections

Citation

Export

Metrics

250

140

Proof of NP-completeness for a scheduling problem with coupled-tasks and compatibility graph

File

Identifiers

Collections

Citation

Export

Share

Metrics

250

140