Le problème d’ordonnancement linéaire est un problème combinatoire NP-dur avec un grand nombre d’applications. Contrairement à un autre problème très populaire de la même catégorie, le problème du voyageur de commerce, relativement peu d’espace dans la littérature a été consacré au problème de l’ordre linéaire jusqu’à présent. Ceci est particulièrement vrai pour la question du développement de bons algorithmes heuristiques résolvant ce problème.
Dans cet article, nous proposons un nouvel algorithme heuristique résolvant le problème d’ordonnancement linéaire. Dans cet algorithme, nous avons fait usage du motif de tri par insertion ainsi que de l’opération d’inversion de permutation. L’effet positif surprenant de l’opération d’inversion, justifié en partie théoriquement et confirmé par des exemples de calcul, semble être le résultat d’une propriété unique du problème, appelée dans l’article la symétrie du problème d’ordre linéaire. Cette propriété consiste dans le fait que si une permutation donnée est une solution optimale du problème avec la fonction critère maximisée, alors la permutation inversée est une solution du problème avec la même fonction critère minimisée.