Algoritmos Computacionales: Proyecto #2

Hola compañeros de clase y profesora aqui les dejo mi proyecto #2, el problema que escogi fue el de programacion de horario (sheduling) .

Es un problema muy amplio del cual se pueden derivar distintos subproblemas según sean las restricciones que se consideren en cada caso y según sean las del caso.

La mayoría de estos problemas son problemas NP Completos.

Considere un servidor (cajero de banco, una caja de supermercado ó procesador ) para atender a una secuencia de clientes ( tareas ). Además supongamos que conocemos por adelantado cuanto tiempo se necesita para atender a cada cliente. Si nuestro objetivo es minimizar el tiempo de espera de cada cliente, entonces una estrategia voraz consiste en atender a los clientes en orden no decreciente de tiempo de atención.

Este es un algoritmo voraz:

Supongamos que hay tres clientes etiquetados C1, C2, C3 que necesitan 8, 4
y 6 unidades de tiempo para ser atendidos, el tiempo total de atención para estos clientes 8 + 4 +6 = 18 unidades. En la siguiente tabla calculamos el tiempo medio que resulta para cada una de las seis secuencias de atención.

La solución óptima para este ejemplar del problema se obtiene atendiendo a C2 primero
luego a C3 y finalmente a C1 lo que arroja un tiempo medio de atención de 10.7 . Esta es la
secuencia que escoge la estrategia voraz

Fuente: http://chavez.gerenciadeproyectos.org/algoIII/sem10/UNMSM-AG3-PRD-10.pdf

Este es un ejemplo del problema en terminos matematicos:

Codificacion de problema de optimizacion
Dada una maquina y 5 trabajos que hay que realizar en ella, en cualquier orden, se dispone del tiempo de ejecucion de cada trabajo

y del tiempo de ajuste de la maquina para pasar de ejecutar el trabajo i(fila) a ejecutar el trabajo j (columna)

Resolver el problema para determinar cual es el menor tiempo posible para completar los 5 trabajos y como hacerlo. Se considera un ciclo de trabajo cerrado, que se repite y vuelve a comenzar.

*La segunda formulacion evita subciclos de parejas de trabajos
SETS
I trabajos que se van a ejecutar / TR1 * TR5 /
ALIAS (i,j)
TABLE C (i,j) tiempo de ajuste para pasar del trabajo i al trabajo j

VARIABLES
X(i,j) paso del trabajo i al trabajo j
TT tiempo total en completar los trabajos

BINARY VARIABLE X
EQUATIONS
TIEMPO tiempo total de trabajo
ANTERIOR(i) de cada trabajo se parte una vez
POSTERIOR(j) a cada trabajo se llega una vez
PAREJAS(i,j) suma de los trabajos por parejas ;

TIEMPO ..TT=E= SUM[(i,j) $(NOT SAME AS (i,j)), C(i,j)*X(i,j)] ;
ANTERIOR(i) ..SUM[j $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
POSTERIOR(j) ..SUM[i $(NOT SAME AS (i,j)), X(i,j)] =E= 1 ;
PAREJAS(i,j) $(ORD(i) < l="1" href="http://www.gams.com/docs/contributed/modelado_en_gams.pdf">http://www.gams.com/docs/contributed/modelado_en_gams.pdf

Aqui otro tipo del problema donde se puede apreciar en forma matematica con su grafica:

Dado un conjunto de productos J=[1....n] y un conjunto de secadores M=[1.....m] en paralelo, se debe programar y secuenciar cada producto en el conjunto de secadores M, respetando las restricciones del probleama.

1): Un secador i ∈M puede procesar solo un producto j∈J a la vez.

2):En una hora de programacion, la suma de los consumos de vapor en cada secador i en paralelo no debe exceder el recurso de vapor maximo Vmax. Esto debe cumplirse para cada hora de programacion en la totalidad de los secadores y en toda la programacion.

3):Debido a condiciones tecnologicas del proceso del secado, algunos productos, j'∈J' siendo J⊂J
no pueden ser programados en ciertos secadores i∈M

4): Se debe cumplir con las fechas de entrega estipuladas para cada producto j∈J