secuenciacionn

Seis alcaldes de pueblo acuden juntos a la capital de la provincia para visitar las delegaciones de Industria y Hacienda, según la siguiente tabla.

Alcalde
1ª Delegación
2ª DelegaciónVillamochuelos
Hacienda (60 min)
Industria (25 min)
Valdealpargatas
Industria (20 min)
Hacienda (40 min)
Cañaveras
Hacienda (70 min)

Montaraces
Industria (25 min)
Hacienda (60 min)
Conejera deArriba
Industria (30 min)

Belloteros de Abajo
Hacienda (52 min)
Industria (30 min)

¿Cómo se organizan para volver cuanto antes a sus pueblos, sabiendo que los alcaldes no pueden ser atendidossimultáneamente en la misma Delegación y que han de volver juntos? ¿Cuánto tiempo pasarán en la capital? ¿Cuándo podrán los funcionarios de las respectivas delegaciones irse a comer por haber acabado deatenderles? Representar en un diagrama la secuencia sobre cada una de las delegaciones.
solucion
Se trata de un problema de secuenciación de tareas en dos máquinas. Suponemos que la máquina 1 es laDelegación de Industria y la 2 la de Hacienda. Luego los trabajos se pueden clasificar en estos tipos


Alcalde
Tipo
Máquina 1
Máquina 2



Industria
Hacienda
1
Villamochuelos
D
25
60
2Valdealpargatas
C
20
40
3
Cañaveras
B

70
4
Montaraces
C
25
60
5
Conejera de Arriba
A
30

6
Belloteros de Abajo
D
30
52

Se deben secuenciar los trabajos de cada uno de lostipos independientemente. Sólo los tipos C y D tienen más de un trabajo luego requieren secuenciación. Los de tipo C se ordenan según el algoritmo de Johnson y los de tipo D por el mismo algoritmo perointercambiando la posición de las máquinas.

Máquina 1
Industria
2, 4, 5, 6, 1
Valdealpargatas, Montaraces, Conejera,
Belloteros, Villamochuelos
Máquina 2
Hacienda
6, 1, 3, 2, 4
Belloteros,Villamochuelos, Cañaveras,
Valdealpargatas, Montaraces

Industria
2
2
2
2







4
4
4
4
4




5
5
5
5
5
5...