Emilie Danna
ILOG

Comparaison de deux nouvelles heuristiques pour des problèmes linéaires
quelconques en nombres entiers : application au problème de job-shop
avec coûts d'avance et retard.

Pour certains problèmes linéaires en nombres entiers, le branch and
bound ne réussit pas à trouver rapidement de bonnes solutions entières.
Pour ce faire, il est alors indispensable de combiner le branch and
bound avec des heuristiques. Il existe peu d'heuristiques génériques,
c'est-à-dire qui ne s'appuient pas sur la connaissance a priori de la
structure de haut niveau du problème. Récemment sont apparues deux
nouvelles heuristiques génériques et efficaces : le "local branching" et
le "relaxation guided large neighborhood search" (RGLNS). Nous
présenterons ces deux heuristiques et nous donnerons des résultats
expérimentaux sur divers problèmes très difficiles, notamment des
problèmes de job-shop avec coûts d'avance et retard (formulation
disjonctive d'Applegate et Cook, 1991) provenant de la littérature sur
l'ordonnancement par des algorithmes génétiques. Sur environ la moitié
de notre base de problèmes, le local branching et le RGLNS sont
d'efficacité comparable. Mais, seul le RGLNS améliore considérablement
les performances du MIP sur ces problèmes d'ordonnancement, ce qui a
permis d'améliorer les meilleures solutions connues sur quelques
problèmes.