Abstract FR:

Ordonnancement avance-retard sur machines parallèles La problématique de cette thèse est ``l'ordonnancement avance-retard’’ : les tâches doivent s'exécuter sur des machines, de telle sorte à minimiser la somme des coûts d'avance et de retard. Ce type de problème est souvent NP-difficile. Nous définissons un nouveau voisinage de taille exponentielle et proposons un algorithme de programmation dynamique pour déterminer le meilleur ordonnancement du voisinage. Ainsi, une borne supérieure est obtenue pour le cas à une seule date d'échéance commune restrictive. En résolvant en temps polynomial un problème d'ordonnancement pour lequel les tâches ont des coûts de position, nous proposons une borne inférieure au problème d'ordonnancement juste-à-temps sur machines parallèles identiques. Finalement, nous proposons une méthode exacte basée sur la relaxation continue de reformulations convexes d'un programme quadratique en 0-1 sous contraintes linéaires.