Tetraheurística sistémica (THS) para el TSP

Systemic tetraheuristics for TSP

Este documento presenta un novedoso método, basado en elementos del pensamiento sistémico, para solucionar instancias del problema del vendedor viajero (travelling salesman problem, TSP), el cual es comparado en términos de eficacia y eficiencia con los métodos  del vecino más cercano (nearest neighbour), la inserción más barata (cheapest insertion), la mejora por el intercambio de dos vías (two-way exchange improvement) y ramificación y poda (branch and bound).

El primer apartado introduce la optimización combinatoria. El segundo ofrece un marco de referencia. El tercero presenta la metodología empleada. El cuarto muestra el desarrollo de la tetraheurística sistémica, seguido del análisis de varianza y de rangos de Duncan para los factores método y cantidad de ciudades; este apartado finaliza con el análisis del comportamiento de la proporción de “fracasos” del algoritmo propuesto a medida que aumenta la complejidad del TSP.

Heuristic solution method for the stochastic flow shop problem

Método de solución heurístico para el problema estocástico de secuenciación de tareas

Se investigó el problema estocástico de secuenciación de tareas (stochastic flow shop problem) con m máquinas y distribuciones generales para tiempos de procesamiento. No existen métodos analíticos para resolver este problema; por ello, los autores se remitieron a los métodos heurísticos. Se concibieron tres procedimientos constructivos con requerimientos computacionales modestos, cada uno basado en enfoques que han sido exitosos al resolver la contraparte determinística. Se comparó el desempeño de estos procedimientos de forma experimental sobre un conjunto de problemas de prueba y se encontró que todos ellos lograron un comportamiento cercano al óptimo.