viernes, 29 de junio de 2012

Construcción de soluciones Iniciales

Para la evaluar los objetivos de nuestro problema de Scheduling hicimos un programa que generará las posibles soluciones iniciales y nos dieron posibles resultados que eran factibles a la solución.

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.



1 comentario:

  1. Pongan una subrutina para checar si una solución es factible. 9 pts para este avance.

    ResponderEliminar