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) • 444 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
...