Download or read book Algorithmes d'approximation pour des problèmes d'ordonnancement bicritères written by Fabien Baille and published by . This book was released on 2005 with total page 138 pages. Available in PDF, EPUB and Kindle. Book excerpt: Inspirés par un problème d'accés réseau, nous traitons le problème suivant. Dans k machines identiques et indépendantes, sont à placer des tâches avec des dates d'arrivée et d'échéance en maximisant simultanément le nombre (nombre de tâches ordonnancées) et le poids (somme des poids des tâches ordonnancées). Nous proposons des algorithmes génériques (utilisant comme sous-routine de bons algorithmes mono-critères), souvent paramètrables et ayant de bons rapports d'approximation (ou de compétitivité) parfois optimaux. Spécifiquement ces modèles de tâches sont traités : - les intervalles (durée d'exécution égale à la différence entre la date d'arrivée et la date d'échéance) et les tâches séquentiels. - les intervalles séquentiels temporellement dégradables (l'ordonnanceur peut raccourcir la durée d'exécution d'un intervalle). - les tâches parallèles spatialement dégradables (une tâche peut être exécutée sur moins de machines que demandé). - les tâches parallèles non dégradables.