thesis

Algorithmes d'approximation pour des problèmes d'ordonnancement bicritères : application à un problème d'accès au réseau

Defense date:

Jan. 1, 2005

Edit

Institution:

Evry-Val d'Essonne

Disciplines:

Computer sciences

Authors:

Directors:

Abstract EN:

Inspired by a network access problem, we study the following problem. In K identical and independent machines, we have to chedule tasks with release dates and deadlines maximizing simultaneously the number (number of scheduled tasks) and the weight (sum of the weights of the scheduled tasks). We propose generic algorithms (using as sub-routine good mono-criterion algorithms), often arameterisable and having non trivial approximation (or competitive) ratios that are sometimes optimal. We specifically study the following models of tasks : - Sequential tasks and intervals (execution time equal to the difference between the release date and the deadline) - Temporally degradable sequential intervals (the scheduler can shorten the execution time of a task) - Spatially degradable parallel tasks (task can be executed on less machines than requested) - Non degradable parallel tasks.

Abstract FR:

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.