El algoritmo de Johnson

El algoritmo de Johnson se usa en teoría de grafos, aunque también se utiliza para minimizar el tiempo total necesario para lograr la producción o cualquier otro objetivo. Si tenéis curiosidad, podéis revisar este artículo de la Wikipedia. Yo voy a exponer un par de ejemplos de uso en el área de la empresa y economía.

Ejemplo 1

Un laboratorio de pruebas tiene 7 muestras para analizar, de las mismas propiedades todas ellas. Cada prueba consta de dos partes que tienen que seguir el mismo orden, ya que las muestras se destruyen al finalizar las correspondientes pruebas. Tenemos, además, las siguientes restricciones:

• La muestra es sometida a la prueba 1 en primer lugar.
• El laboratorio tiene solamente una máquina del tipo requerido para cada parte de la prueba.

Basándonos en los tiempos de prueba indicados a continuación, tenemos que determinar el orden en el que deben ser analizadas las muestras a fin de minimizar el tiempo total necesario para analizar las 7 muestras.

Muestras	Prueba 1	Prueba 2
1	2 (1º)	3
2	7 (3º)	9
3	10	8(5º)
4	5	2(7º)
5	6(2º)	11
6	4	3(6º)
7	8(4º)	11

• Buscamos el menor tiempo de la prueba 1 y de la prueba 2.
• Si el menor tiempo está en la prueba 1, la muestra a la que corresponde se coloca en primer lugar; por el contrario, si el menor tiempo está en la prueba 2, su correspondiente muestra se coloca en el último lugar

Siguiendo este razonamiento, el orden debería ser el siguiente:

1 - 5 - 2 - 7- 3-6-4

Ejemplo 2

Cinco vehículos de las casas X1, X2, X3, X4 y X5 son llevados a un taller donde son petroleados, engrasados y lavados. Una vez en el taller, los vehículos no pueden adelantarse unos a otros. ¿En qué orden deben entrar los coches?

	Petrolear	Engrasar	Lavado
X1	130	95	105
X2	80	100	140
X3	160	55	150
X4	105	85	115
X5	130	80	130

Si en un problema de este tipo se ponen 3 o más columnas, hay que reducirlo a dos, sumando los tiempos. Por ejemplo, en la tabla de abajo la columna A es igual a la suma de los tiempos de petrolear y engrasar; y la columna B es igual a la suma de tiempos de engrasar y lavado:

	A	B
X1	225	200
X2	180	240
X3	215	205
X4	190	200
X5	210	210

Aplicando el algoritmo de Johnson, explicado en el primer ejemplo, tenemos el siguiente orden:

X2-X4-X5-X3-X1