CAPTULO 4 ALTERNATIVAS DE SOLUCIN Y CASOS DE APLICACIN SIMILARES.

En el siguiente apartado se muestran los diferentes procedimientos de solucin para

la programacin de mquinas en paralelo, as mismo, se explica brevemente el

funcionamiento de cada uno de ellos. Por otra parte se presentan casos de

aplicacin similares y por ltimo un anlisis de las alternativas de solucin.

4.1 ALTERNATIVAS DE SOLUCIN

En el siguiente punto se muestran los procedimientos matemticos y heursticos para

la solucin de problemas de programacin de maquinas en paralelo.

4.1.1 Procedimientos de solucin para el problema de programacin de n tareas en m mquinas en paralelo idnticas.

Pinedo M. L. (2005) propone los siguientes procedimientos para la solucin de

programacin de n tareas en m mquinas en paralelo idnticas, dentro de los

cuales se pueden encontrar los de programacin matemtica y los mtodos

heursticos. A continuacin se desglosan cada uno de ellos.

1. Programacin Matemtica.

a) Programacin Lineal Entera Binaria

2. Mtodos Heursticos.

a) Reglas de Despacho Bsicas

Regla SPT, seleccin del trabajo con menor tiempo de proceso, para solucionar problemas Pm| | Cj.

Regla WSPT, Seleccin del trabajo con tiempo de proceso ms corto, resultante de la divisin entre wj / Cj, para la solucin de

problemas Pm| | wjCj.

Regla LPT, seleccin del trabajo con mayor tiempo de proceso, para la solucin de problemas Pm| |Cmax.

Regla CP, regla del camino critico, para la solucin de problemas Pm|prec|Cmax.

Regla LNS, mayor numero de sucesores primero, para la solucin de problemas Pm|prec|Cmax.

Regla LFJ, el trabajo menos flexible primero, para solucionar problemas Pm|Mj| Cmax

Algoritmo de McNaughtons. El algoritmo de McNoughtons resuelve problemas P|pmtn|Cmax, donde un conjunto de tareas

independientes, son programadas en orden en maquinas

idnticas, para minimizar el tiempo de terminacin.

4.1.2 Programacin lineal entera binaria.

Segn Mocholi Arce & Sala Garrido (1993), los problemas de programacin lineal

entera, aparecen cuando en los problemas lineales estudiados hasta ahora todas o

algunas de las variables slo pueden tomar valores enteros, es decir, se abandona la

hiptesis de perfecta divisibilidad de las variables.

En un sentido estricto, todo problema de programacin entera tendra que ser

definido como problema de programacin no lineal, dado que la funcin objetivo del

problema estar definida nicamente para valores discretos de las variables. No

obstante en programacin entera, se dice que un problema es de programacin lineal

entera (PLE), si prescindiendo de las condiciones de integridad de las variables, el

problema resultante es lineal. Esta clasificacin resulta sumamente interesante, por

cuanto los algoritmos de resolucin de los problemas lineales enteros estn basados

directamente o indirectamente en la versin continua de estos problemas (Mocholi

Arce & Sala Garrido, 1993).

Un modelo de programacin lineal entera es aquel en el cual algunas de las variables

o todas, son nmeros enteros no negativos. En situaciones reales, con frecuencia, el

analista se enfrenta a decisiones s o no, las que pueden representarse con

variables llamadas binarias, por ejemplo 0 y 1. As la K-sima decisin s o no puede

representarse por Xk, tal que

Xk= 1; si la decisin k es s.

0; si la decisin k es no

Cuando solo es necesario que algunas de las variables sean enteras y el resto

continuas, el modelo recibe el nombre de problema de Programacin Lineal Entera

Mixta. Dentro de esta clasificacin, se incluyen aquellos modelos que, adems de

tener variables enteras no negativas y variables continuas, tienen tambin variables

binarias (Cornejo Snchez & Meja Puente, 2005).

En particular para la programacin de mquinas en paralelo se tiene el siguiente

modelo matemtico:

Se tienen n tratamientos a programar y k mquinas disponibles. Tratamientos: Conjunto de tratamientos i tratamientos Mquinas: Conjunto de mquinas k mquinas. As mismo, los parmetros:

ti: duracin del tratamiento i [horas]. Capk: tiempo disponible de la mquina k [horas]. Seti: tiempo de preparacin en horas [horas]. Ci: tiempo de terminacin del tratamiento i [horas]. (1) Tiempo de proceso total del tratamiento i

Pi = ti + Seti (1)

Variables de decisin: Variable binaria que indica si el tratamiento i se realiza antes que el tratamiento j en

la mquina k

Se define makespan como el tiempo total en el cual todos los tratamientos han

terminado su ejecucin. Para el modelo matemtico se minimiza el makespan Cmax

De esta forma:

Yik = 1 si el tratamiento i se realiza en la mquina k

0 de lo contrario

Xijk = 1 si el tratamiento i se realiza antes que j en la mquina k

0 de lo contrario

Restricciones:

=mquinask

ikY 1 i tratamientos (2)

Cj Ci Pj M(1-Xijk) i, j tratamientos, k mquinas

(3a)

Cj Ci Pj M(1-Xijk) (1Yik Yjk) i, j tratamientos, k mquinas (3b) Xijk Yik i, j tratamientos, k mquinas

(4)

Xijk Yjk i, j tratamientos, k mquinas

(5)

ostratamienti

kiki CapYP k mquinas (6)

(7)

Ci Makespan i tratamientos

La ecuacin (2) indica que un tratamiento se debe asignar exactamente a 1 y solo a

1 mquina. La desigualdad (3a) establece que la secuenciacin de los tratamientos

asignados a una misma mquina slo se cumple si el procedimiento i est antes que

el procedimiento j en una mquina k determinada. Es importante aclarar que el

parmetro M es un parmetro de penalizacin que corresponde a un nmero grande,

que tambin se ve reflejado en la desigualdad 3.b, la cual indica que dos

procedimientos se deben realizar asignndose a la mquina k si Yik = 1 y Yjk = 1. Por

su parte, Las inecuaciones (4) y (5) son restricciones que relacionan variables de

secuenciacin con variables de asignacin, garantizado as que el tratamiento i no

inicie antes de j cuando i est despus j de , siempre que tanto i como j pertenezcan

a una misma mquina. La desigualdad (6) restringe la capacidad horaria de las

mquinas, bajo el supuesto de no dejar holguras innecesarias.

Finalmente, la desigualdad (7) indica que el tiempo de terminacin del tratamiento i

debe ser menor o igual al Makespan. La funcin objetivo consiste en minimizar el

Makespan.

4.1.3 Algoritmos heursticos existentes para la programacin de mquinas paralelas idnticas con tareas Independientes.

A continuacin se presentan los diferentes algoritmos heursticos para la

programacin de mquinas en paralelo idnticas con tareas independientes, para el

caso de Pm| |Cmax

4.1.3.1 Un procedimiento Heurstico para minimizar F (Mean Flow time) SPT.

La regla SPT (Shortest Processing Time o tiempo de procesamiento ms corto)

selecciona el primer trabajo que tenga el tiempo esperado de procesamiento ms

corto. Esta regla se realiza para reducir los tiempos medios de flujo (Pinedo M. ,

2008).

El algoritmo SPT se puede adaptar a varias mquinas en paralelo si se hace una

programacin para cada mquina. Es decir, se programan las tareas mquina a

mquina de acuerdo al algoritmo seleccionado (Veloza et al. 2008).

El algoritmo SPT, arroja muy buenos resultados con respecto al Makespan, y de

hecho una programacin para el problema de mquinas en paralelo es ptima si y

slo si es una programacin de acuerdo a SPT o a LPT (Pinedo M. , 2008).

ste algoritmo se utiliza para minimizar F (Mean Flow time o tiempos promedios de

flujo) en mquinas paralelas idnticas, los pasos a seguir son los siguientes:

1. Construir un orden SPT para todos los trabajos.

2. A la mquina con menos cantidad de procesos asignados, asignar el trabajo

que sigue en la lista ordenada de trabajos.

A excepcin de los vnculos, ste algoritmo produce una programacin nica y por

supuesto, ser una de las programaciones que pueda ser producida por los m-

trabajos-en-un-tiempo aproximado. Mas sin embargo ste algoritmo tiene dos

virtudes especiales. Primeramente el algoritmo es un procedimiento de envi, para

poder ejecutar la decisin de programacin en el orden que estn hechos. En

segundo lugar, el algoritmo se puede ampliar de una manera obvia a los problemas

deterministas que implican llegadas intermitentes y a los problemas estocsticos que

implican llegadas al azar. Ninguna de las dos caractersticas se sostiene para el

procedimiento de m-trabajos-en-un-tiempo.

Por el contrario no se ha desarrollado ningn algoritmo directo para construir una

programacin ptima cuando wF

es el criterio. Las formulaciones de la

programacin dinmica son posibles, pero en este caso el " curso de la dimensin"

hace un procedimiento de programacin dinmica imprctico para los problemas,

incluso en los de tamao moderado.

4.1.3.2 Un procedimiento Heurstico para minimizar M (Makespan o tiempo de terminacin) LPT.

La regla LPT (Longest processing time o tiempo de procesamiento ms largo) se usa

para minimizar el Makespan (Tiempo de terminacin) organizando los trabajos desde

su tiempo de procesamiento ms largo. Para el caso del algoritmo LPT, se deben

programar todas las tareas en un tiempo igual a cero, e iniciar por aquella que tome

ms tiempo. Esta heurstica propone ubicar aquellas tareas de menor duracin (o las

ms sencillas) hacia el final del da, balanceando as la carga en las mquinas,

(Sewell & Lawrence, 1997). Formalmente, el algoritmo LPT se puede describir de la

siguiente manera: a cualquier hora en la que una mquina est disponible para

operar, se programa el trabajo disponible con el mayor tiempo de procesamiento. Si

no hay mquinas disponibles, se espera al a siguiente llegada.

El algoritmo LPT se puede adaptar a varias mquinas en paralelo si se hace una

programacin para cada mquina. Es decir, se programan las tareas mquina a

mquina de acuerdo al algoritmo seleccionado (Veloza et al. 2008). ste algoritmo es

un procedimiento heurstico para minimizar M (makespan), los pasos a seguir son los

siguientes:

1. Construir un orden LPT de los trabajos.

2. Programe los trabajos en orden, asigne un trabajo en la mquina con menor

cantidad de procesamientos ya asignados.

4.1.3.3 Algoritmo de McNaughtons

El algoritmo de McNoughtons resuelve problemas P|pmtn|Cmax, donde un

conjunto de tareas independientes, son programadas en orden en mquinas

idnticas, para minimizar el tiempo de terminacin. Este algoritmo considera

semiprocesados (preemption) en las tareas y el resultado de la programacin es

ptimo. El tiempo mximo de la tarea programada podra ser definido por el mximo

de estos dos valores: Max(Pj); (Pj)/m, donde m significa el nmero de mquinas y

Pj es el tiempo de procesamiento del trabajo j en cualquier mquina cuando todas

son idnticas (Baewicz et al. 2001).

Este algoritmo se utiliza para minimizar M (makespan) con m mquinas paralelas

idnticas, los pasos a seguir son los siguientes:

1. Seleccione algn trabajo para empezar en la mquina 1, en el tiempo cero.

2. Elija cualquier trabajo no programado, y progrmelo lo ms temprano posible

en la misma mquina. Repita este paso hasta que una mquina se ocupe ms

all del tiempo M* (o hasta que todos los trabajos sean programados).

3. Reasigne el proceso programado mas all de M* a la siguiente mquina en el

lugar de otro, comenzando en el tiempo cero. Vuelva al paso 2.

Es importante mencionar que ste problema generalmente no tiene una nica

solucin, y el mtodo desarrollado produce solamente una solucin potencial de

muchas programaciones optimas. Particularmente el mtodo no hace ningn intento

de minimizar el nmero de interrupciones en el proceso de trabajo. A medida que

un pequeo setup podra estar involucrado en la interrupcin de los procesos de

trabajo, el mtodo desarrollado tendra que ser modificado para encontrar la

programacin optima.

A continuacin se analizan distintas investigaciones respecto a la programacin de

mquinas paralelas idnticas, donde se utilizaron algoritmos heursticos para la

solucin de los problemas.

4.2 CASOS DE APLICACIN RESPECTO A LA PROGRAMACIN DE MQUINAS PARALELAS IDNTICAS.

A continuacin se hace un anlisis de distintas investigaciones en las cuales se llevo

a cabo la programacin de tareas en mquinas paralelas idnticas.

4.2.1 Programacin de Cirugas en un Hospital de Bogot.

Este estudio fue realizado en las salas de ciruga de un hospital privado de Bogot,

Colombia, donde se analizaron un conjunto de algoritmos heursticos que permiten,

de manera prctica, realizar una asignacin de turnos de operacin en las salas de

ciruga. Se utiliz una herramienta desarrollada en VBA Excel a travs de la cual se

ilustra la aplicacin de los algoritmos analizados por (Veloza et al. 2008), donde se

compara el desempeo de dos reglas de despacho en el algoritmo de mquinas en

paralelo para programar cirugas independientes, en salas idnticas, asumiendo

tiempos de operacin determinsticos. Mediante la aplicacin de un algoritmo

heurstico se busca mejorar la situacin actual, en la cual, la programacin de

cirugas es manual y se realiza bajo la poltica FIFO primeras entradas primeras

salidas.

Existen varios tipos de mquinas en paralelo: mquinas en paralelo idnticas,

mquinas en paralelo uniformes y mquinas en paralelo sin relacin. Para este caso

fue necesario basarse en la regla de mquinas en paralelo idnticas, ya que cada

sala est equipada con los mismos recursos es decir son idnticas.

As mismo en ste trabajo, se parti de dos supuestos: el primero es la

homogeneidad de las salas; es decir, las salas tienen los mismos equipos y cualquier

ciruga se puede realizar en cualquier sala. Tambin es de suponer que los tiempos

de duracin de cada ciruga son conocidos, que cada ciruga se realiza en un paso

es decir, no hay precedencia entre cirugas), que no hay reprocesos en las cirugas,

que hay disponibilidad continua de las salas, que no hay interrupciones de las

cirugas en ejecucin (preemptions), y de la misma forma, el tiempo de

procesamiento se da por la suma del tiempo de preparacin, el tiempo de duracin

de la ciruga y el tiempo de anestesia.

Por su carcter prctico, el objetivo tambin es disear una herramienta

computacional en la cual sea posible asignar turnos a las salas de cirugas, de modo

que se estandarice el mtodo de programacin de las salas. Las soluciones

obtenidas se evalan bajo tres medidas de desempeo que son: utilizacin de las

salas, el nmero de trabajos tardos y el tiempo en que finaliza la ltima ciruga

(Makespan) para cada da de operacin. Con base en lo anterior, se realizan

simulaciones con base en los algoritmos clsicos de mquinas en paralelo: LPT

(Longest Processing Time) y SPT (Shortest Processing Time).

Como ya se ha dicho, todos los tiempos de procedimiento (anestesia, ciruga y

limpieza) son independientes de la sala y de la secuencia de procedimientos

programados en ella. Es importante resaltar que los tiempos de ciruga, para una

misma ciruga, difieren en funcin de la complejidad de la operacin y del cirujano,

para ste caso se asumir que la duracin estimada por los cirujanos es correcta y

no se hace necesario analizar la correlacin entre los mdicos y el paciente, de

acuerdo al tipo de procedimiento.

Como variables de decisin ellos modelaron tres tipos de variables para el problema

enunciado: unas variables binarias que indican si la ciruga i se realiza antes que la

ciruga j en la sala k. Otras variables binarias que indican si la ciruga i se realiza en

la sala k. Finalmente se define el Makespan como el tiempo total en el cual todas las

cirugas han terminado su ejecucin.

Los algoritmos considerados para la programacin de las mquinas fueron el

algoritmo o poltica SPT, la cual selecciona el primer trabajo que tenga el tiempo

esperado de procesamiento ms corto. Esta regla se realiza para reducir los tiempos

medios de flujo (Pinedo M. , 2008). En contraste a SPT, la regla LPT se usa para

minimizar el Makespan organizando los trabajos desde su tiempo de procesamiento

ms largo. Para el caso del algoritmo LPT, se deben programar todas las cirugas en

un tiempo igual a cero e iniciar por aquella que tome ms tiempo. Esta heurstica

propone ubicar aquellas cirugas de menor duracin (o las ms sencillas) hacia el

final del da, balanceando as la carga en las salas (Lawrence, 1997).

Tanto el algoritmo SPT como el algoritmo LPT se pueden adaptar a varias mquinas

en paralelo si se hace una programacin para cada sala. Por su parte el algoritmo

SPT, arroja muy buenos resultados con respecto al Makespan, y de hecho una

programacin para el problema de mquinas en paralelo es ptima si y slo si es una

programacin de acuerdo a SPT o a LPT (Pinedo M. , 2008).

La herramienta que ellos utilizaron para resolver el problema de la programacin fue

la utilizacin de macros en Microsoft Excel, debido a que es la herramienta que

actualmente se maneja en el hospital para realizar las programaciones.

Para ver el funcionamiento del nuevo sistema a implementar, se tomaron muestras

diarias de un conjunto de cirugas obtenidas a partir de los datos histricos

correspondientes a Agosto del ao 2008 con el fin de caracterizar el sistema.

As mismo, se pudo probar que la utilizacin promedio de las salas segn las reglas

utilizadas, que fueron la LPT es de 86,5% y para la regla SPT es de 77,7%. En base

a estos experimentos realizados se pudo constatar que los algoritmos LPT y SPT son

muy similares, pero en cuanto a su desempeo, es mejor el LPT dado que arroj

mejores resultados para el Makespan en un 52,31%, mientras que para la regla SPT,

el Makespan fue mejor en un 47,69%. Del mismo modo, se puede ver que para los

datos histricos no hay trabajos tardos, pues al hacer la asignacin de acuerdo al

algoritmo LPT siempre hay espacio para programar incluso ms cirugas.

Como se puede observar las herramientas de secuenciacin no solo son aplicables

en procesos industriales, sino que hoy en da son de gran utilidad, y sirven como

apoyo para realizar otro tipo de programaciones que no tienen nada que ver con el

sector industrial, en ste caso se han utilizado algunos algoritmos de secuenciacin

para la programacin de cirugas en un hospital privado, lo cual demuestra que stas

herramientas son adaptables a procesos semejantes a los de la industria.

4.2.2 Estudio experimental de un taller cermico de mquinas paralelas con secuenciacin dinmica.

El estudio realizado por (Gmez et al. 2006), se realiz tomando como referencia el

subsistema productivo de una industria cermica, donde se hizo una particularizacin

a un taller con tres etapas para la simulacin experimental. Estas etapas son prensas

y lneas de esmaltado, con cuatro mquinas, horno tnel, con tres hornos, y

clasificado y embalaje, con tres mquinas.

El estudio experimental consisti en la simulacin del comportamiento de la etapa

productiva de prensas-secado, asumindose que la llegada de trabajos al taller es

dinmica con fechas de entradas desconocidas a priori. As mismo los tiempos de

proceso y de cambio de partida se suponen conocidos en el momento de iniciar el

proceso de secuenciacin. Se ha realizando el anlisis de dos medidas de eficiencia

regular: La media del flujo F y la varianza del mismo F.

Los factores a considerar fueron el setup, las fechas de entrega, tasa de llegada de

trabajo y las reglas de despacho u algoritmos que se utilizaron fueron las reglas: Regla Descripcin

SPT Selecciona el trabajo con menor tiempo de proceso.

LPT Selecciona el trabajo con mayor tiempo de proceso

AT-RPT Esta regla es una combinacin entre FIFO y la regla AT, donde el trabajo con fecha de llegada ms temprana es seleccionado.

EDD Asigna la prioridad ms alta al trabajo en espera con fecha de entrega ms temprana.

MDD Calcula la fecha de entrega modificada como el mximo entre la fecha de entrega y la fecha de finalizacin. Selecciona el trabajo con menor fecha de entrega modificada.

FIFO Selecciona el trabajo que ha llegado antes a la cola.

LIFO Selecciona el trabajo que ha llegado ltimo a la cola.

RANDOM Selecciona el trabajo aleatoriamente de la cola de espera Tabla 4.1 Tabla de descripcin de reglas de despacho. Fuente: (Gmez et al. 2006)

En base a los resultados obtenidos se observa claramente que los mejores

resultados se obtienen en la utilizacin de las reglas de despacho LPT y AT-RPT

que incluyen en sus clculos los tiempos de setup de forma explcita, las cuales

superan a la regla SPT, que presenta mejores resultados cuando no se considera el

tiempo de setup. Por otra parte se observa que las dems reglas se comportan de

una manera muy similar.

4.2.3 Estudio de algoritmos dinmicos para el problema de secuenciacin de trabajos en una mquina simple.

Montoya Torres et al. (2006), estudian el problema de secuenciacin on-line de

tareas en un recurso nico y se presenta el estudio de las reglas SPT (Shortest

Processing Time) y FIFO (First In, First Out). stas reglas son inicialmente

analizadas con respecto a su competitividad para el peor de los casos y,

posteriormente se desarrolla una serie de experimentos de simulacin para verificar

dichos postulados y comparar las reglas aplicndolas a diferentes instancias de

trabajo.

En ste estudio se consideran un conjunto de n tareas (o trabajos) diferentes para

las cuales se debe encontrar una secuencia admisible de ejecucin en una mquina

simple. Cada tarea es denotada por Jj, la cual tiene un tiempo de procesamiento pj y

est disponible en el sistema a partir del instante rj, con j = 1, 2., n. No se autoriza

la interrupcin de la tarea actualmente en ejecucin en mquina (preemption), y sta

ltima siempre est disponible a lo largo del horizonte del trabajo (no existen fallas ni

actividades de mantenimiento preventivo o reactivo). Puesto que solo se considera

una mquina en el taller, sta puede representar el recurso cuello de botella o una

agregacin de todos los recursos en el sistema.

El objetivo es optimizar el nivel de inventario de producto en proceso, puesto que

esto permite disminuir los costos asociados a la manutencin de capital inmovilizado,

as como los resultados globales de la cadena logstica.

Este objetivo est representado por la minimizacin del tiempo total de terminacin

de las tareas (es decir, suma de los instantes en los cuales las tareas son

terminadas), Cj, donde Cj representa el instante de terminacin de la tarea Jj. Esta

funcin objetivo tambin es equivalente a la minimizacin tanto del tiempo total (o

promedio) de flujo de las tareas, Fj, como del tiempo total o promedio de las tareas

(Pinedo M. , 2008).

En el estudio experimental se evalu el desempeo de las reglas de secuenciacin

SPT y FIFO en contexto on-line utilizando instancias generadas aleatoriamente. El

desarrollo de estos experimentos pretende ir ms all de los resultados tericos

tradicionalmente presentados en la literatura, a travs del anlisis de las reglas de

secuenciacin sobre una amplia variedad de instancias.

Los tiempos operatorios de las entidades se determinaron de manera aleatoria segn

una distribucin uniforme entre 1 y 12. Cuando el tiempo entre llegadas de tareas a

la mquina sigue una distribucin normal, el valor de la desviacin estndar se tom

como el 5% del valor de la media. Se diseo entonces un experimento con factores

mltiples. Se efectuaron tres repeticiones para cada combinacin, lo que arroja un

total de 1,296 instancias (3x3x3x16x3), en el experimento tambin se considero la

regala de secuenciacin LPT (Longest Processing Time).

Se puede observar en la figura 4.1 los valores obtenidos para el makespan no varan

cuando se cambia la regla de secuenciacin o la de distribucin para los tiempos

entre llegadas, para un tamao de instancia dado. Esto explica el hecho de que los

algoritmos implementados (SPT, LPT y FIFO) son todos conservadores (Montoya

Torres et al. 2006).

Figura 4.1 Makespan en funcin del tamao de instancia Fuente: (Montoya Torres et al. 2006)

Tambin se observa en la figura 4.2 el comportamiento del porcentaje de utilizacin

del recurso a medida que se incrementa el nmero de tareas en el sistema,

aprecindose un decrecimiento en el porcentaje de utilizacin de la maquinaria a

medida que aumenta el nmero de tareas (Montoya Torres et al. 2006).

Figura 4.2 Nivel de utilizacin de la mquina en funcin del tamao de la instancia. Fuente: (Montoya Torres et al. 2006)

Se tiene como resultado que al analizar la diferencia de los promedios dados en las

tablas, se observa que con la estrategia LPT el flujo de entidades es mayor en

1.7415 unidades de tiempo que con la estrategia SPT. Con la utilizacin de la

estrategia FIFO, el flujo de las entidades es 0.8167 unidades de tiempo mayor que

con la estrategia SPT (Montoya Torres et al. 2006).

Se realiz una prueba de comparacin mltiple para determinar la diferencia entre

las estrategias, y con base en esta prueba se concluye que para el indicador del

tiempo promedio de flujo s existe diferencia significativa entre las estrategias SPT y

LPT. Sin embargo, no se encuentra diferencia significativa entre las estrategias FIFO

y SPT y entre FIFO y LPT.

Vale la pena aclarar que, si bien no se encuentran diferencias estadsticamente

significativas entre las reglas SPT y FIFO para el valor del tiempo de flujo, el valor

obtenido aplicando la regla SPT siempre ser inferior o igual al valor obtenido

aplicando FIFO, para cualquier instancia (es decir, SPT siempre domina a FIFO).

Este resultado terico se verifica experimentalmente puesto que SPT tiene un mejor

desempeo que FIFO en el 75% de los casos, mientras que en el restante 25% SPT

y FIFO arrojan valores solucin iguales para el tiempo de flujo promedio (y, por

consiguiente, para el tiempo total de terminacin).

Finalmente se concluye que la regla SPT arroja la mejor solucin para el tiempo de

flujo que las reglas FIFO y LPT, mientras que los valores del makespan y de la

utilizacin del recurso resultan iguales bajo las tres reglas (Montoya Torres et al.

2006).

De acuerdo a las investigaciones analizada, se puede observar que los algoritmos

heursticos ms utilizados para la programacin de mquinas en paralelo, en

diferentes sectores donde se manejan ste tipo de mquinas, son los algoritmos

SPT, donde la asignacin de tareas es hecha en base al acomodo de tareas por su

tiempo de procesamiento ms corto, y el algoritmo LPT que se basa en asignar

tareas por su tiempo de procesamiento ms largo, ya que estos algoritmos

proporcionan soluciones muy cercanas optimas en la programacin de mquinas en

paralelo, as mismo se ha demostrado en las investigaciones analizadas

anteriormente que se obtienen buenos resultados con la utilizacin de stos

algoritmos.

4.3 ANLISIS DE LAS ALTERNATIVAS DE SOLUCIN.

En el caso de los procedimientos de programacin matemtica, debido a la tipo de

problema que se tiene, que se clasifica como NP-hard segn (Pinedo M. , 2008).

Para obtener una solucin mediante ste procedimiento, es necesario el uso de

software y de personal con conocimientos sobre programacin matemtica, para

realizar la programacin de pacientes mediante la alimentacin de variables y

restricciones en el software. Por otra parte, se requiere de una persona dedicada

nica y exclusivamente para la programacin de pacientes, debido al tiempo que se

requiere para estar realizando las reprogramaciones cada vez que sea necesario.

En el caso de los mtodos heursticos, stos son ms sencillos de implementar y

explicar al personal encargado de la programacin de pacientes, no requiere de

software ni de personal especializado en su uso, con la capacitacin adecuada es

ms que suficiente para que el personal aprenda a manejarlos. As mismo han

arrojado buenos resultados en su aplicacin en centros hospitalarios, en la

asignacin de turnos de operacin en salas de ciruga realizados por (Veloza et al.

2008). Por lo que se consider necesario utilizar un mtodo heurstico de

programacin debido a su sencillez y a las limitaciones que se tienen de no invertir

en personal capacitado, hardware y software.

Dentro de los mtodos heursticos se consider utilizar el algoritmo LPT, ya que es el

algoritmo que ms se adapta al tipo de problema que se desea resolver, debido a

que est diseado para solucionar problemas de programacin de tareas en

mquinas en paralelo idnticas, donde no se permite semiprocesado (preemptions),

y las tareas no siguen alguna precedencia.