Exponential Algorithms for Scheduling Problems - Université de Tours Accéder directement au contenu
Rapport Année : 2014

Exponential Algorithms for Scheduling Problems

Résumé

This report focuses on the challenging issue of designing exponential algorithms for scheduling problems. Despite a growing literature dealing with such algorithms for other combinatorial optimization problems, it is still a recent research area in scheduling theory and few results are known. An exponential algorithm solves optimaly an NP-hard optimization problem with a worst-case time, or space, complexity that can be established and, which is lower than the one of a brute-force search. By the way, an exponential algorithm provides information about the complexity in the worst-case of solving a given NP-hard problem. In this report, we provide a survey of the few results known on schduling problems as well as some techniques for deriving exponential algorithms. In a second part we focus on some basic scheduling problems for which we propose exponential algorithms.
Fichier principal
Vignette du fichier
RRExpAlgoScheProb.pdf (526.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00944382 , version 1 (10-02-2014)

Identifiants

  • HAL Id : hal-00944382 , version 1

Citer

Christophe Lenté, Mathieu Liedloff, Ameur Soukhal, Vincent t'Kindt. Exponential Algorithms for Scheduling Problems. 2014. ⟨hal-00944382⟩
346 Consultations
926 Téléchargements

Partager

Gmail Facebook X LinkedIn More