El problema de ordenación lineal es un problema combinatorio NP-duro con un gran número de aplicaciones. A diferencia de otro problema muy popular de la misma categoría, el problema del viajante de comercio, hasta ahora se ha dedicado relativamente poco espacio en la literatura al problema de ordenación lineal. Esto es particularmente cierto para la cuestión de desarrollar buenos algoritmos heurísticos que resuelvan este problema.
En el artículo proponemos un nuevo algoritmo heurístico que resuelve el problema de ordenación lineal. En este algoritmo hacemos uso de la ordenación por patrón de inserción así como de la operación de inversión de permutaciones. El efecto sorprendentemente positivo de la operación de inversión, justificado en parte teóricamente y confirmado en ejemplos computacionales, parece ser el resultado de una propiedad única del problema, llamada en el trabajo la simetría del problema de ordenación lineal. Esta propiedad consiste en el hecho de que si una permutación dada es una solución óptima del problema con la función criterio siendo maximizada, entonces la permutación invertida es una solución del problema con la misma función criterio siendo minimizada.