Obtención y generación de instancias reales y artificiales

Pare empezar a generar soluciones, primero empezamos por construir un programa que generara instancias iniciales para el problema que nos sirvan para probar nuestro heurístico e instancias iniciales que nos sirvan para comprobar el correcto funcionamiento de nuestro algoritmo.

Para generar el numero de tareas que llegan al procesador en cierto momento, utilizamos un generador con distribución Poisson que toma como parámetro el promedio de tareas que podrían llegar en cierto periodo de tiempo. Para generar la longitud de tiempo de cada tarea utilizamos un generador con distribución Exponencial. Todo se guarda en un archivo que nos sera útil mas adelante.



instancias.py

#! /usr/bin/python
import math
import random
import sys

def poisson(lamb):
    acumulador = exponencial( lamb)
    contador = 0
    while( acumulador < 1):
        acumulador = acumulador + exponencial( lamb)
        contador+=1
    return contador


def exponencial(lamb):
    return (-1*math.log( random.random() ))/lamb

fl = open(sys.argv[1], "w")

for i in range(poisson(float(sys.argv[2]))):
    fl.write(str(exponencial(1.0/float(sys.argv[3])))+"\n")

El programa siguiente se encarga de leer la longitud de cada tarea y le asigna un lugar en un vector a cada longitud y después genera una tabla con el número de procesadores como filas y las columnas cada tarea.

leer.py

#! /usr/bin/python
import sys


class Heuristico:
    def __init__(self, nameOfFile, nProcessors):
        self.tasks = []
        self.solucion = []

        for line in open(nameOfFile,'r'):
            self.tasks.append( float(line.replace("\n", "")) )
        for j in range(nProcessors):
            self.solucion.append([])
            for i in range(len(self.tasks)):
                self.solucion[j].append(0)

h = Heuristico(sys.argv[1], int(sys.argv[2]))
print h.tasks

BenchMarks
Estos nos serviran para comprobar el correcto funcionamiento de nuestro algoritmo, como benchmark encontramos los siguientes:

Algunos resultados del benchark encontrado son los siguientes: La tabla muestra fue encontrada en el archivo del primer hiper-vinculo y el segundo hiper-vínculo tiene mas benchmarks que nos parecen útiles. El rango de valores que serían aceptables con las instancias mostradas.

BENCHMARKS FOR BASIC SCHEDULING PROBLEMS
E. TAILLARD
ORWP89/21 Dec. 1989
http://bit.ly/Mwory2

Benchmark-Problem Instances for Static Schedulingof Task Graphs with Communication Delays on Homogeneous Multiprocessor Systems
Tatjana Davidovi
August 17, 2004
http://www.mi.sanu.ac.rs/~tanjad/bench04.pdf

Referencias:
http://webcache.googleusercontent.com/search?q=cache:c8t-8DY30Q0J:citeseerx.ist.psu.edu/viewdoc/download?doi%3D10.1.1.75.3540%26rep%3Drep1%26type%3Dpdf+&hl=es&gl=mx
http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
http://en.wikipedia.org/wiki/Exponential_distribution