SCHEDULING PARA MINIMIZAR EL TIEMPO DE TERMINACION:
ALGORITMOS DE APROXIMACION
EN LINEA Y FUERA DE LINEA.

Objetivo : Presentar la comprobación de los algoritmos de aproximacion-r Fuera-de-linea y En-linea propuestos para diversos modelos de Scheduling en la obtención de la minimizacion del peso total en tiempo de terminación.

Algunas definiciones importantes:

Se dice que un algoritmo A es un algoritmo de aproximacion-r si, para cada instancia de un modelo I, A(I) esta dentro de un factor de r del valor optimo. [Lenstra].

Algoritmo en Línea: Se construye la asignación de trabajos como un producto del tiempo, y no se conoce la existencia del trabajo hasta su tiempo tiempo de salida para ser procesado.

Algoritmo Fuera de Línea: Todos los trabajos se conocen al inicio de la asignación (tratados en este articulo en su mayoría).

Para obtener cotas superiores con respecto a la solución optima[Beasley]: Esencialmente es a través de métodos heurísticos (Simulated Annealing, Tabu Search, Ga, Artificial Neural Networks, etc.).

Para obtener cotas inferiores con respecto a la solución optima[Beasley]: La Relajación LP. Consiste en tomar un entero o mezclas de enteros en la formulacion de programación del problema para relajar los requerimientos de integridad de las variables. Esto da un programa lineal que se puede resolver por algún algoritmo lineal (ej. simpex). Ejemplo: Dado un problema P