Scheduling a sequence of tasks with general completion costs

F. Sourd

LIP6 2002/013: Rapport de Recherche LIP6 / LIP6 research reports
14 pages - Mai/May 2002 - Document en anglais.

Get it : 222 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Systèmes d'Aide à la Décision et à la Formation

Titre français : Ordonnancer une séquence de tâches au moindre coût
Titre anglais : Scheduling a sequence of tasks with general completion costs

Résumé : Ordonnancer une séquence de tâches, c'est-à-dire trouver les dates d'exécution, n'est pas un problème trivial quand le critère d'optimisation n'est pas régulier tels dans les problèmes avec coûts d'avance et de retard. Cet article présente un algorithme de programmation dynamique efficace pour résoudre le problème avec des coûts qui sont fonction des dates d'exécution, des coûts d'inactivité et des durées dépendant aussi des dates d'exécution des tâches. L'algorithme marche également lorsque le graphe de précédence est un arbre et il peut être adapté pour déterminer pour chaque tâches les fenêtres de temps d'exécution possibles lorsque le coût total est borné.

Abstract : Scheduling a sequence of tasks - in the acceptation of finding the execution times - is not a trivial problem when the optimization criterion is irregular as for instance in earliness-tardiness problems. This paper presents an efficient Dynamic Programming algorithm to solve the problem with general cost functions depending on the end time of the tasks, idle time costs and variable durations also depending in the execution time of the tasks. The algorithm is also valid when the precedence graph is a tree and it can be adapted to determine the possible execution windows for each task not to exceed a maximum fixed cost.

Mots-clés : Ordonnancement, Juste-à-temps, Programmation dynamique

Key-words : Scheduling, Just-in-time, Dynamic Programming

Publications internes LIP6 2002 / LIP6 research reports 2002

Responsable Éditorial / Editor :nicole.nardy@lip6.fr