APLICACIÓN DE LA HEURISTICA DE DANNENBRING EN LA SECUENCIACIÓN DE N TAREAS EN M MÁQUINAS:
Enviado por javieramaya20 • 13 de Agosto de 2014 • 860 Palabras (4 Páginas) • 465 Visitas
APLICACIÓN DE LA HEURISTICA DE DANNENBRING EN LA SECUENCIACIÓN DE N TAREAS EN M MÁQUINAS:
En un taller se tienen 10 tareas y estas se deben secuenciar en 5 máquinas diferentes. Se ha optado por solucionar este problema de secuenciación por la solución heurística de Dannenbring. Esta heurística es un método en el cual trata de combinar las heurísticas de Palmer y CDS. Su idea es construir dos (2) maquinas en las que se pueda aplicar el algoritmo de Johnson, pero en consecución de los tiempos de proceso reflejen el comportamiento como el índice máximo de Palmer:
Para la maquina 1 tenemos:
a_j: Total de la sumatoria de el numero de maquinas menos la etapa mas uno y multiplicado por el tiempo de ejecución de la tarea j en la maquina i.
m: Número total de máquinas en las que se van a realizar los trabajos j.
i: Máquina en la que se realiza el trabajo j.
P_ij: Tiempo de ejecución del trabajo j en la maquina i.
Los siguientes datos son los que corresponden al tiempo de ejecución de un trabajo j en una maquina i:
M1
M2
M3
M4 M5
P1 1
1
8
4 15
P2 9
11 6 12 6
P3 5 6 2 9 9
P4 6 15 10 15 2
P5 3 8
7 5 3
P6 12 9 5 3 15
P7 4 3 12 15 1
P8 2 5 13 2 12
P9 15 8 1 11 8
P10 9 2 5
8 7
Para:
a_1=[(5-1+1)*1]+[(5-2+1)*1]+[(5-3+1)*8]+[(5-4+1)*4]+[(5-5+1)*15]
a_1=56
Calculando a_2:
M1
M2
M3
M4 M5
P1 1
1 8 4 15
P2 9
11
6
12 6
P3 5 6 2 9 9
P4 6 15 10 15 2
P5 3 8 7 5 3
P6 12
9 5 3 15
P7 4 3 12 15 1
P8 2 5 13 2 12
P9 15 8 1 11 8
P10 9 2 5 8 7
Para:
a_2=[(5-1+1)*9]+[(5-2+1)*5]+[(5-3+1)*6]+[(5-4+1)*12]+[(5-5+1)*6]
a_2=137
Y así sucesivamente hasta hallar todos los a_j
A continuación se presenta una tabla resumen:
a_j
a_1 56
a_2 137
a_3 82
a_4 152
a_5 81
a_6 132
a_7 99
a_8 85
a_9 140
a_10 91
LUEGO HACEMOS LOS CALCULOS PARA LA SEGUNDA MAQUINA DE ACUERDO A LA HEURISTICA:
DONDE:
b_j: Total de la sumatoria de la maquina i multiplicado por el tiempo de ejecución de la tarea j en la maquina i.
i: Tipo de maquina en la que se realizan los trabajos.
P_ij: Tiempo de ejecución del trabajo j en la maquina i.
M1
M2
M3
M4 M5
P1 1
1
8
4 15
P2 9 11 6 12 6
P3 5 6 2 9 9
P4 6 15 10 15 2
P5 3 8
7 5 3
P6 12 9 5 3 15
P7 4 3 12 15 1
P8 2 5 13 2 12
P9 15 8 1 11 8
P10 9 2 5
8 7
Para b_1:
b_1=[1*1]+[2*1]+[3*8]+[4*4]+[5*15]
b_1=118
Calculando b_2 :
M1
M2
M3
M4 M5
P1 1 1 8 4 15
P2 9
11
6
12 6
P3 5 6 2 9 9
P4 6 15 10 15 2
P5 3 8 7 5 3
P6 12 9 5 3 15
P7 4 3 12 15 1
P8 2 5 13 2 12
P9 15 8 1 11 8
P10 9 2 5 8 7
b_2=[1*9]+[2*11]+[3*6]+[4*12]+[5*6]
b_2=127
Y así sucesivamente hasta hallar todos los b_j
A continuación se presenta una tabla resumen:
b_j
b_1 118
b_2 127
b_3 104
b_4 136
b_5 75
b_6 132
b_7 111
b_8 119
b_9 118
b_10 95
SECUENCIACIÓN POR ALGORITMO DE JOHNSON
Obteniendo los resultados de la aplicación de la heurística de Palmer, se procede a realizar la secuenciación mediante el algoritmo de Johnson, recordando las reglas de secuenciación de este algoritmo:
El algoritmo de Johnson se puede expresar así:
Sea k y l dos contadores. k=1 inicialmente y creciendo
...