Note publique d'information : Cette thèse est consacrée aux problèmes d’ordonnancement sur machines parallèles identiques.
Les travaux développés portent sur l’un des critères les plus difficiles de la théorie
de l’ordonnancement, à savoir la minimisation du temps total pondéré de séjour. Dans
un premier temps, nous avons considéré le problème où tous les poids des tâches sont
identiques. Ensuite, nous nous sommes intéressés au cas où les poids des tâches sont
quelconques. Pour ces deux critères, nous avons considéré des contraintes assez fréquentes
en entreprise à savoir les temps de changement entre les tâches et les dates d’arrivée
différentes des tâches. Nous avons développé des méthodes exactes de type Branch-and-Bound
pour la minimisation du temps total de séjour, avec des disponibilités des tâches
et avec ou sans temps de changement, sur machines parallèles, et également la minimisation
du temps total pondéré de séjour avec des disponibilités des tâches sur une seule
machine. Nous avons démontré pour chaque problème, des propriétés de dominance, des
bornes inférieures et supérieures. Les tests numériques ont montré l’efficacité de
nos algorithmes. Pour le problème de la minimisation de la somme pondérée du temps
total de séjour avec des disponibilités des tâches, sur des machines parallèles, nous
avons démontré de nouvelles bornes inférieures. Nous avons aussi construit une méthode
approchée dont l’efficacité a été établie par des expérimentations numériques
Note publique d'information : This thesis is devoted to the identical parallel machines scheduling problems. It
concerns one of the most difficult criteria of the scheduling theory, that is, the
minimization of the total weighted completion time. First we consider the problem
where all the weights of the jobs are identical. Then we deal with the case where
the weights of the jobs are arbitrary. For these two cases we consider quite frequent
constraints in enterprises, such as, setup times and job release dates. We develop
exact Branch-and-Bound methods for minimizing total completion time, with different
release dates and with or without setup times on parallel machines, and also total
weighted completion time with different release dates on one machine. For each problem,
we show dominance properties, lower and upper bounds. Numerical tests show the efficiency
of our algorithms. For the minimization of the weighted completion time with different
release dates on parallel machines, we establish new lower bounds. We have also introduce
an approximate method which the efficiency is established by numerical experimentations
paprika.idref.fr
data.idref.fr
Documentation
