Solución Inicial
Para plantear la solución inicial se observó que las tareas y los procesadores son los que afectan el procesamiento, y el acomodo de cada tarea hará que sea más eficiente los procesadores.
En el código anterior solo agregamos dos funciones, una que es la función objetivo que encuentra el tiempo desde que empiezan a ejecutarse las tareas hasta que termina su ejecución la ultima, este representa el tiempo total invertido en todas las tareas y el tiempo que necesitamos minimizar.
La segunda función genera soluciones iniciales, recorriendo cada tarea y asignándola de forma aleatoria a cada procesador.
Código:
-#! /usr/bin/python
import sys
import random
class Heuristico:
"""Las soluciones son vectos donde [] la primera dimension son los procesadores y la segunda las tareas"""
def __init__(self, nameOfFile, nProcessors):
"""Funcion que recibe como parametros el nombre del archivo donde se encuentran las instancias iniciales y el numero de procesadores, luego crea un vector donde se encuentran todas las tareas"""
self.tasks = []
self.nProcessors = nProcessors
for line in open(nameOfFile,'r'):
self.tasks.append( float(line.replace("\n", "")) )
def cota_superior(self):
suma = 0
solucion = []
for i in range(self.nProcessors):
solucion.append([])
for i in range(len(self.tasks)):
solucion[0].append(self.tasks[i])
suma = suma + self.tasks[i]
return solucion, suma
def cota_inferior(self):
inferior = self.tasks[0]
solucion = []
for i in range(self.nProcessors):
solucion.append([])
for i in range(len(self.tasks)):
if self.tasks[i] > inferior:
inferior = self.tasks[i]
solucion[0].append(inferior)
return solucion, inferior
def funcion_objetivo(self, solucion):
longitud = 0.0
temp = 0.0
for i in solucion:
temp = 0.0
for j in i:
temp = temp + j
if temp > longitud:
longitud = temp
return longitud
def instancia_inicial(self):
"""Soluciones vector[procesadores][tareas]"""
solInicial = []
for i in range(self.nProcessors):
solInicial.append([])
for i in self.tasks:
solInicial[random.randint(0, self.nProcessors-1)].append(i)
return solInicial
h = Heuristico(sys.argv[1], int(sys.argv[2]))
inicial = h.instancia_inicial()
print "Solucion Inicial:"
print "Fmin = ", h.funcion_objetivo(inicial)
fl = open("plot.dat", "w")
for i in range(len(inicial)):
fl.write("Procesador"+str(i+1)+": ")
suma = 0
for j in inicial[i]:
suma = suma + j
fl.write(str(j)+"|")
fl.write(" -> Tiempo total: "+str(suma)+"\n\n")
Estos fueron los resultados que arrojo el programa: Cada fila representa un procesador y cada tarea asignada a dicho procesador se muestra separada por una linea "|" y al final imprime el tiempo total que tarda este procesador.
Procesador1: 82.6730338949|88.5098812114|133.114417016|193.742993448|17.8844210663|397.967016649|0.625573697983|206.509612532|21.2331895565|192.385443689|122.680952065|105.572325168|295.343485267|74.4373243836|67.3253267158|417.877046369|100.016062755| -> Tiempo total: 2517.89810548 Procesador2: 50.1900656323|45.2364871263|501.435654212|156.826235205|68.0613220146|124.878988739|240.168034439|124.243130917|188.26251933|66.8062495319|0.685172859901|9.70212752867|237.068343631|16.1943798738|25.3845034891| -> Tiempo total: 1855.14321453 Procesador3: 97.5661722589|85.130908261|6.44171775684|19.681811607|54.3277066299|321.622916841|151.642044294| -> Tiempo total: 736.413277649 Procesador4: 109.550956153|31.6725286583|112.76430841|176.160778285|46.9829315479|378.606136424|200.742421697| -> Tiempo total: 1056.48006118 Procesador5: 89.1675721906|380.381785216|170.88656808|1.93082496016|333.823004928|27.798345494|16.0587368224|69.6818875605|40.5405267045| -> Tiempo total: 1130.26925196 Procesador6: 257.426424518|49.9528757956|159.601674772|31.8352432621|76.9735249074|100.394197317|18.4899061317|5.9345714234|12.2049573076|65.3802528633|212.73218059|36.3658561913|165.705060906|218.683521092| -> Tiempo total: 1411.68024708 Procesador7: 60.8471047844|7.93916119733|95.1301746115|338.60360794|53.8125172849|28.1703730432|181.529508799|15.6773794346|60.4739027566|173.498164461|588.803885191|261.327070364|151.60996291|217.646039444| -> Tiempo total: 2235.06885222 Procesador8: 126.723901703|5.63484238619|200.66907298|90.2361737493|165.064902193|66.9650391754|84.701835441|442.919265815|54.7314964044|46.0815272418|79.7944566786|6.81583321219|110.439347826| -> Tiempo total: 1480.77769481 Procesador9: 178.798944704|76.1234733668|134.857982216|95.4862728934|39.7916708402|36.2357803112|346.422854166| -> Tiempo total: 907.716978498 Procesador10: 45.4570873715|92.8011630612|12.140667911|20.9653566492|124.091179449|87.1899264758|91.8984680757|15.1706044026|11.9033520346|105.738497739|17.7300061189|162.081247148| -> Tiempo total: 787.167556437
Esto fue lo que imprimió la función objetivo, que es el tiempo total que tardo la solución anterior que como se puede observar es el tiempo que tardo el sexto procesador.
Esta grafica muestra otra ejecución del problema con 20 procesadores y todas las tareas que hicieron en su ejecución en milisegundos.
