Proyecto fin de Carrera 2014
i
Proyecto Fin de Carrera Ingeniero Industrial (Plan 98)
Estudio de heurísticas para problemas de Scheduling con máquinas en paralelo.
Autor: Ricardo Pérez-Ventana Muñoz
Tutor: José Manuel García Sánchez
Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería
Universidad de Sevilla
Sevilla, 2014
Proyecto fin de Carrera 2014
ii
Proyecto Fin de Carrera
Ingeniero Industrial (Plan 98)
Estudio de heurísticas para problemas de Scheduling con máquinas en paralelo
Autor:
Ricardo Pérez-Ventana Muñoz
Tutor:
José Manuel García Sánchez
Dpto. de Organización Industrial y Gestión de Empresas I
Escuela Técnica Superior de Ingeniería
Universidad de Sevilla
Sevilla, 3 de Septiembre de 2014
Proyecto fin de Carrera 2014
iii
Proyecto fin de Carrera
Autor: Ricardo Pérez-Ventana Muñoz Tutor: José Manuel García Sánchez
El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros:
Presidente:
Vocales:
Secretario:
Acuerdan otorgarle la calificación de:
Sevilla, 2014 El Secretario del Tribunal
Proyecto fin de Carrera 2014
iv
ÍNDICE
1. INTRODUCCIÓN Y OBJETIVOS DEL PROYECTO ……………1
2. PROBLEMA CON MÁQUINAS EN PARALELO ………………..6 2.1 Introducción …………………………………………………...7 2.2 Secuenciación de trabajos en máquinas ………………………...8
2.2.1 Tipos de arquitectura……………………………………...8 2.2.2 Representación …………………………………………..10 2.2.3 Notación ………………………………………………...11
2.3 Caracterización del problema ………………………………….16
3. MODELO Pm| |Lmax……………………………………………...17 3.1 Introducción …………………………………………………..18 3.2 Definición y objeto de las heurísticas………………………….19 3.3 Heurística EDD&Greedy ……………………………………..21 3.4 Heurística EDD&Conway …………………………………….28 3.5 Comparación entre ambas heurísticas ........................................33
4. MODELO Pm| |ΣUi ………………………………………………..38 4.1 Introducción ………………………………………………….39 4.2 Heurística EDD&Greedy ……………………………………..40 4.3 HEURÍSTICA EDD&CONWAY ……………………………..44 4.4 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS………...48
5. MODELO Qm| |Lmax……………………………………………...54 5.1 Introducción …………………………………………………..55 5.2 Heurística EDD&Greedy ……………………………………..56 5.3 Heurística EDD&Conway …………………………………….61 5.4 Comparación entre ambas heurísticas …………………………66
6. MODELO Qm| |ΣUi ..........................................................................71
6.1 Introducción …………………………………………………..72 6.2 Heurística EDD&Greedy ……………………………………..73 6.3 Heurística EDD&Conway …………………………………….78 6.4 Comparación entre ambas heurísticas …………………………83
Proyecto fin de Carrera 2014
v
7. MODELO Pm| |ΣTi...........................................................................89
7.1 Introducción …………………………………………………..90 7.2 Heurística EDD&Greedy ……………………………………..91 7.3 Heurística EDD&Conway …………………………………….97 7.4 Comparación entre ambas heurísticas ………………………..103
8. GENERACIÓN Y LECTURA……………………………………108
8.1 Introducción ………………………………………………….109 8.2 Descripción de las variables…………………………………. 110 8.3 Generación de los problemas………………………………….111 8.4 Lectura de los problemas……………………………………...113
9. CONCLUSIONES………………………………………………..114
10. BIBLIOGRAFIA…………………………………………………117
11. ANEXOS…………………………………………………………119
Proyecto fin de Carrera 2014
vi
Proyecto fin de Carrera 2014
1
CAPÍTULO 1
INTRODUCCIÓN Y OBJETIVOS DEL PROYECTO
Proyecto fin de Carrera 2014
2
1. INTRODUCCIÓN Y OBJETIVOS DEL PROYECTO
Este proyecto trata de estudiar heurísticamente el comportamiento de diferentes tipos
de problemas con respecto a las variables que influyen en el mismo, especialmente el
número de trabajos, el número de máquinas y la mayor o menor compresibilidad de
los problemas, que viene dada en función a los recursos de los que se dispone, es decir
el número de máquinas, y el tiempo de finalización en el que estos recursos deben
tener ejecutados los trabajos.
En este tipo de trabajos de secuenciación en máquinas, normalmente conocidos como
Scheduling, la asignación en el tiempo de los recursos disponibles con objeto de
determinar su comportamiento óptimo puede responder a diferentes criterios según
lo que sea necesario optimizar, es decir, dependerá de nuestro caso concreto, de
nuestra empresa o nuestra fábrica la necesidad de obtener un valor por encima o por
debajo de uno concreto que nos sea requerido.
A partir de este determinado criterio, se trata de establecer la secuencia para el
procesamiento de una serie de trabajos sobre un conjunto de máquinas.
En nuestro caso particular, nos interesa estudiar un subconjunto de la casi infinidad de
problemas que se pueden estudiar en esta materia con el objeto de descifrar,
mediante estudios heurísticos de los mismos, el mejor procedimiento y algoritmo para
resolverlos. En este sentido, contando con una batería de casos específicos creados
por nuestra cuenta, los pasaremos por un algoritmo de resolución previamente
testado que nos permitirá con los datos de salida conocer cuál de estos se comporta
mejor en la mayoría de los casos.
Trataremos el caso de problemas con máquinas en paralelo en el que varias máquinas
funcionan al mismo tiempo, y deberemos asignar los distintos trabajos a las distintas
máquinas mediante criterios que veremos con posterioridad y que serán la base de
nuestro estudio.
Desde el punto de vista de las máquinas veremos dos tipos que se diferencian
fundamentalmente en una característica, que no tiene poca importancia, y que se
trata de la velocidad con que estas tratan a los trabajos.
Así, en un primer momento trataremos con máquinas que tienen la misma velocidad
de procesamiento de los mismos:
• Máquinas idénticas (Pm)
Para posteriormente tratar el caso de aquellas cuya velocidad de procesamiento es
diferente, pero nunca en un amplio rango, sino en uno que no supere el 50 % de la
velocidad base (rango de velocidades 1 – 1,5):
Proyecto fin de Carrera 2014
3
• Máquinas uniformes (Qm)
Para resolver los problemas hemos utilizado el programa Visual Basic, de
programación C+, con el que primero hemos generado una batería de 570 problemas
para posteriormente resolverlos y compararlos para cada uno de los tipos analizados.
Para asegurarnos de que la resolución de los mismos era correcta, para cada uno de
los casos hemos resuelto a mano tres problemas sencillos, para los que luego hemos
realizado la resolución computacional, asegurándonos de que cada archivo nos
proporcionase no solo el valor óptimo sino el orden del los trabajos y el tiempo de
finalización de las máquinas, con el objeto de asegurar la correcta resolución del
algoritmo.
Con este procedimiento, básicamente, han sido dos los tipos de heurísticas utilizadas,
tanto para máquinas idénticas como para máquinas uniformes. El objeto del trabajo es
comparar dos de los tipos de actuación que pueden dar buenos resultados y que
detallaremos a lo largo de este proyecto. Estos son:
• Asignación Conway: los trabajos seleccionados por un método específico para
cada tipo de problema se asignarán a la máquina menos cargada en ese
momento, para máquinas idénticas, o que se vaya a encontrar menos cargada
después de la operación para máquinas uniformes.
• Asignación Greedy: este carácter de la asignación, que significa avaricioso en
inglés, quiere decir que, al contrario de la anterior forma de actuar,
asignaremos el trabajo a la máquina mas cargada (Pm) o que se vaya a
encontrar más cargada al finalizar la operación (en el caso de Qm).
Por último, vamos a destacar los tipos de problemas utilizados, dentro de la gran
amplitud de los mismos existentes en Scheduling, como comentamos antes. Estos han
sido elegidos debido a la incertidumbre que había sobre la optimalidad de los mismos,
y son:
• Lmax: Se trata del retraso máximo que se produce en las máquinas con
respecto a la fecha de entrega de los trabajos, y lo que busca esta heurística
lógicamente es minimizarla, de forma que los trabajos con menor fecha de
finalización terminen lo antes posible.
• ΣUi: En este caso lo que se busca minimizar es el número de retrasos que se
producen en las máquinas, intentando que el tiempo en el que finalizan los
trabajos no superen al tiempo de finalización de los mismos. A grandes rasgos
comentar que es preferible, como antes, deshacerse cuanto antes de los
trabajos con fechas de finalización tempranas.
• ΣTi: Este último caso, del que solamente haremos el estudio con máquinas
idénticas (por la complejidad del mismo con varias máquinas en paralelo), se
Proyecto fin de Carrera 2014
4
trata de reducir el sumatorio de retrasos producidos en el proceso, por lo que
habrá que ir analizando en cada transición la máquina óptima a asignar.
Con esta combinación de problemas, como se puede observar, el número de casos a
resolver se multiplica. Tanto es así que sin contar con ΣTi, la combinación de estudios a
realizar sería = 8, que sumados a los dos realizados por ΣTi (debido a que en este
caso obviamos las máquinas uniformes), daría un total de 10. Es por ello, que el
número total de problemas a resolver será 570*10 = 5.700, los cuales habrá que
comparar con el objeto de sacar unas conclusiones útiles.
De este modo, este texto que ahora empezamos se estructurará de la siguiente forma
para que el lector pueda comprender paso a paso como se ha realizado el estudio del
mismo y pueda analizar las conclusiones finales con facilidad.
Tras este primer capítulo introductorio, en el segundo introduciremos de forma
genérica el problema de secuenciación de trabajos, estudiando los posibles escenarios
de estudio en función de los distintos parámetros, a fin de que se pueda entender con
claridad los conceptos básicos y las premisas fundamentales sobre las que está basado
este estudio, permitiendo utilizar posteriormente conceptos ya introducidos.
Una vez realizado un análisis global de la situación de la materia, procederemos a
analizar nuestros casos de estudio.
De este modo en el capítulo tercero analizaremos el caso de Pm||Lmax, es decir, el
caso de minimización del retraso máximo para máquinas idénticas, en el que
compararemos la diferencia entre la utilización del algoritmo Conway y el Greedy,
observando cual se comporta mejor.
De la misma forma, en el cuarto apartado observaremos que para el problema
Pm||ΣUi ocurre que hay uno que se comporta igualmente mejor entre los estudiados.
Este es un caso similar al anterior con la diferencia de que se buscará minimizar el
número de retrasos en lugar del retraso mayor.
Para los casos en que se estudien máquinas uniformes se utilizarán los dos siguientes
capítulos. De esta forma el quinto capítulo hablará del problema Qm||Lmax,
analizando de nuevo su comportamiento, mientras que ya el sexto capítulo analizará el
caso de Qm||ΣUi, en el que se podrán ver además las diferencias existentes entre
utilizar o no máquinas idénticas.
Posteriormente, como caso excepcional estudiaremos el comportamiento de Pm||ΣTi,
es decir, el caso de minimización de la suma de retrasos en máquinas pero, como ya
hemos dicho, con máquinas idénticas, en el que de nuevo haremos la comparación
entre Conway y Greedy, viendo cual de los dos se comporta mejor. Esto se verá en el
séptimo capítulo.
Proyecto fin de Carrera 2014
5
Por último en los capítulos octavo y noveno realizaremos y comentaremos la
experimentación de los mismos, así como la generación y lectura de los problemas,
analizando la gran cantidad de ejemplos existentes y la relación entre ellos con el
objeto de sacar, ya en el último y noveno capítulo unas conclusiones efectivas y útiles
del mismo, que sirvan como colofón del texto y ayuden a entender el funcionamiento
de este tipo de problemas a futuros investigadores o alumnos que traten con ellos.
Sin más, comenzaremos este trabajo introduciendo conceptos y teorizando sobre las
máquinas en paralelo.
Proyecto fin de Carrera 2014
6
CAPÍTULO 2
PROBLEMAS CON MÁQUINAS EN PARALELO
Proyecto fin de Carrera 2014
7
2. PROBLEMAS CON MÁQUINAS EN PARALELO
2.1 INTRODUCCIÓN
En este capítulo explicaremos los conceptos, y terminología asociados con la
secuenciación de trabajos en máquinas con el objetivo de establecer una base teórica
sobre la que explicar los estudios realizados posteriormente. Una vez establecido el
marco global donde situar el Problema con Máquinas en Paralelo, definiremos de una
forma más concreta nuestro problema.
Proyecto fin de Carrera 2014
8
2.2 SECUENCIACIÓN DE TRABAJOS EN MÁQUINAS
La secuenciación de trabajos en máquinas, universalmente conocido como Scheduling,
se puede definir como la asignación en el tiempo de los recursos disponibles con
objeto de optimizar una determinada medida de comportamiento. A partir de un
determinado criterio, se trata de establecer la secuencia para el procesamiento de una
serie de trabajos sobre un conjunto de máquinas.
Existe un amplio espectro de características que pueden asociarse a los trabajos y al
modo de procesamiento en el sistema
Un problema se determina según 3 factores:
• La arquitectura del taller
• Las características de los trabajos
• El criterio de optimización
2.2.1 TIPOS DE ARQUITECTURA
Respecto a la arquitectura del sistema en relación con la disposición de las máquinas,
se distinguen en una primera clasificación, los sistemas con máquinas en serie y
máquinas en paralelo. En los entornos con máquinas en serie, cada máquina realiza
una operación diferente, del conjunto de operaciones a las que se someten los
trabajos. Cuando hablamos de máquinas en paralelo, se entiende que una
determinada operación sobre un trabajo puede ser procesada sobre una cualquiera de
entre un conjunto de máquinas.
-Máquinas en serie:
Los entornos de máquinas en serie se clasifican en función del modelo o esquema de
paso de los trabajos por las diferentes máquinas:
• Sistemas de flujo uniforme (Flow shop): El modelo de paso es el mismo para
todos los trabajos. Todos los trabajos pasan por cada una de las máquinas del
sistema usando el mismo orden de paso por las mismas. Es decir, todos los
trabajos deben pasar por las mimas máquinas en el mismo orden.
• Sistemas de tipo taller (Job shop): Cada trabajo tiene su propio esquema de
paso por las máquinas, por lo tanto el orden en el que las máquinas deben
Proyecto fin de Carrera 2014
9
actuar de forma óptima para cada trabajo debe ser diferente para cada una de
ellas.
• Sistemas de taller abierto (Open shop): El modelo de paso de cada trabajo por
las máquinas es libre.
-Máquinas en paralelo:
Respecto a los sistemas de máquinas en paralelo se distinguen tres tipos
• Máquinas idénticas: El tiempo de proceso de una operación es idéntico en cada
máquina, o dicho de otra manera, todas las máquinas tardarían lo mismo en
ejecutar un trabajo previamente dado.
• Máquinas uniformes: Cada máquina posee una velocidad de proceso diferente,
independiente de los trabajos, por lo que al contrario que en el caso anterior
cada máquina tardaría un tiempo distinto en ejecutar aquel trabajo
predefinido.
• Máquinas no relacionadas: Cada máquina posee una velocidad de proceso
diferente sobre cada trabajo, de modo que una misma máquina no tardaría lo
mismo en ejecutar dos trabajos que si pudieran tener la misma duración en
una segunda máquina.
Además de los sistemas con máquinas en serie y máquinas en paralelo, también se
distingue un sistema híbrido denominado sistema de flujo uniforme con máquinas en
paralelo (Flexible Flow Shop). Un sistema híbrido es el caso del “Taller flexible”, que
cuenta con m centros o estaciones de máquinas en serie, cada uno de ellas formado
por un conjunto de máquinas en paralelo como el que se representa a continuación:
Proyecto fin de Carrera 2014
10
2.2.2 REPRESENTACIÓN
Para la representación de los trabajos es muy común usar el diagrama de Gantt:
En donde el eje vertical muestra el número de máquinas que disponemos y en el eje
horizontal se muestra el tiempo. J1 y J2 son los trabajos que tienen que pasar por
ambas máquinas. Vemos que hasta que un trabajo no finaliza en una máquina no
puede comenzar a ser procesado en la otra, por lo que resulta muy visual y nos dará
información muy interesante sobre parámetros como la fecha de finalización o el
retraso de los trabajos, que posteriormente compararemos para los distintos modelos.
Proyecto fin de Carrera 2014
11
2.2.3NOTACIÓN
Existen varias formas de representar un problema de secuenciación, aunque una de de
las más usadas, y la que usaremos en este trabajo será la que se describe por la tripleta
α /β /γ.
El campo α indica el entorno de las máquinas, que viene dado por dos caracteres:
número de máquinas y tipo de arquitectura del sistema. El número de máquinas viene
representado en el subíndice y a continuación, de forma genérica lo identificaremos
con la letra m. Por otra parte los tipos de arquitecturas del sistema se designan por
letras mayúsculas y serán descritos a continuación, aunque en este trabajo solo
usaremos la P y la Q.
El campo β describe las características y restricciones de procesamiento de los
trabajos, como algunas opciones de precedencia o rotura de la finalización de los
mismos que pueden afectar considerablemente al resultado final.
El campo γ especifica el objetivo del problema, es decir, la variable o criterio que
queremos, normalmente, minimizar.
• Terminología para los entornos de máquinas (α)
Sea un conjunto de M = {M1, M2,.., Mj, ..., Mm} máquinas, que vendrán caracterizadas
por el subíndice m, existe distintas formas en que las máquinas pueden funcionar,
según lo visto anteriormente:
Fm: Sistema de flujo uniforme (Flow Shop) con m máquinas en serie,
Jm: Sistema de taller (Job Shop) con m máquinas en serie,
Om: Sistema de taller abierto (Open Shop) con m máquinas en serie,
Pm: m máquinas idénticas en paralelo,
Qm: m máquinas uniformes en paralelo,
Rm: m máquinas no relacionadas en paralelo,
Sm: Sistema de flujo uniforme (Flexible Flow Shop) con m centros de máquinas en
paralelo,
• Terminología asociada a los trabajos (β )
Asociada a los trabajos hay todo un conjunto de datos y variables que pasaremos a
explicar, pues serán utilizados posteriormente, así como unas restricciones relativas a
los mismos que serán las que ocuparán el segundo lugar de la tripleta antes
mencionada y que se enumerarán a continuación:
Proyecto fin de Carrera 2014
12
� Datos
Los datos son característicos de un trabajo que vendrán dadas por su propia
idiosincrasia y necesidades y que serán nuestro apoyo para conseguir el objetivo, pues
son los que implementarán nuestro algoritmo para que las variables se minimicen.
Dado un conjunto de J = {J1, J2,.., Ji, .., Jn} trabajos, algunos de los datos relativos a estos
son:
pij : Tiempo de proceso del trabajo Ji en la máquina Mj. (pi para el caso de una sola
máquina), es decir, el tiempo que se tarda en realizar dicho trabajo.
ri : Instante de llegada de Ji al sistema. Cuando todos los trabajos están disponibles al
comienzo del procesamiento, ri = 0. No debe confundirse con el tiempo en que
comienza a ejecutarse el trabajo. Este es un dato que nos marca (para algunos
trabajos) el momento antes del cual el mismo no está disponible.
di : Fecha de entrega del trabajo Ji. Es la fecha antes de la cual, si el trabajo ya está
terminado, no existe retraso en su entrega.
wi : Peso(coste o valor) del trabajo Ji. Se utiliza para ponderarlos en algunas ocasiones,
pero no será utilizado en este estudio.
� Variables
A diferencia de los datos, las variables dependerán de la gestión que nosotros
hagamos de los trabajos, siendo nuestro objetivo llegar a los valores óptimos de las
mismas que optimice nuestro valor objetivo. Destacar que nuestro valor objetivo en sí,
normalmente, también será una de estas variables, de ahí su importancia. Algunas de
las más importantes son:
Ci : Tiempo de finalización de Ji. Cij tiempo de Ji en Mj. Se trata del instante en el que la
máquina que realizaba este trabajo pasa a estar desocupada u ocupada en otro trabajo
debido a la finalización del mismo.
Fi = Ci – ri: Tiempo de permanencia del trabajo en el sistema, que no es más que la
resta del tiempo de finalización menos el tiempo de entrada del trabajo en el sistema,
como es lógico.
Li = Ci – di: Mide la desviación respecto a la fecha de entrega. Si Li<0 (retraso negativo),
|Li| representa las unidades de adelanto. Se trata del retraso que tiene el trabajo con
respecto a la fecha de finalización del mismo y viene dado por la resta de este tiempo
de finalización menos la fecha de entrega del mismo. Se usará en adelante.
Ti = máximo {0, Li}= máximo {0, Ci – di}: Tardanza de Ji o número de instantes de retraso
de Ji. Es una variable parecida a la anterior, con la salvedad de que no cuenta retrasos
Proyecto fin de Carrera 2014
13
negativos, es decir, adelantos, y por lo tanto se convierten en cero. Solo se tendrán en
cuenta los retrasos y no los adelantos. Se utilizará en los últimos capítulos de este
estudio.
Ei = máximo {0, di - Ci}: Número de instantes de adelanto de Ji. Se trata de una variable
parecida a las dos anteriores, pero en este caso, en lugar de no contar los adelantos,
no cuenta los retrasos.
Existen variables booleanas para el control de los trabajos que se retrasan y adelantan,
de modo que nos permiten distinguir si un trabajo ha terminado antes o después de su
fecha de entrega. La lógica de las mismas son:
De manera análoga, se pueden definir variables booleanas para el control de los
trabajos finalizados sin retraso ni adelanto, sino en su tiempo de entrega exacto, como
es:
� Restricciones de procesamiento de los trabajos:
En este apartado destacamos determinadas características que pueden presentarse en
el procesamiento de los trabajos y que pueden ser cruciales en la resolución del
problema, aunque en este estudio no las utilizaremos. Estas son:
Preemption (prmt): Rotura de trabajos. Esta característica hace referencia a la
posibilidad de abandonar el procesamiento de un trabajo en una máquina sin haber
concluido la operación, regresando más tarde para finalizarla.
Restricciones de precedencia (pre): En algunos entornos aparecen relaciones de
precedencia obligada entre pares de trabajos.
No-wait (No-Wait): Aparece en entornos de máquinas en serie en los que los trabajos
deben ser procesados desde su inicio en la primera máquina, hasta su finalización en la
última máquina, sin ninguna interrupción entre máquinas.
1 si
0 en otro caso
i i
i
C dU
>=
1 si
0 en otro caso
i i
i
C dV
<=
Proyecto fin de Carrera 2014
14
Blocking (Block): Esta característica aparece en sistemas de fabricación en serie en los
que no están permitidos los buffers intermedios de un cierto tamaño entre máquinas,
puesto que bloquean el funcionamiento de las mismas.
Tiempos de setup (sik): Tiempo de cambio de procesamiento entre el trabajo i y el
trabajo k.
• Terminología asociada a los objetivos (γ )
Los objetivos o criterios para la búsqueda de soluciones se pueden agrupar en tres
grandes grupos, que definiremos a continuación:
1. Criterios basados en tiempos de finalización de los trabajos:
Se busca minimizar el tiempo en que terminan los trabajos a través de diversas
fórmulas:
ΣCi : Minimizar la suma de los tiempos de finalización de los trabajos, que es
equivalente a minimizar el tiempo de finalización medio.
ΣwiCi : Minimizar el coste total asociado a la finalización de los trabajos. El peso wi se
entiende como un coste de espera o un valor añadido al trabajo Ji. Se trata de un
objetivo parecido al anterior, pero con una ponderación de los trabajos debida a algún
criterio.
Cmax = Max{C1,…,Cn}: Minimizar el tiempo de finalización de todos los trabajos, también
llamado longitud de la programación (makespan). Es equivalente a minimizar el trabajo
máximo, ya que si hacemos el máximo más pequeño, todos finalizarán antes.
2. Criterios basados en fechas de entregas:
Cuando existen una fechas de entregas como datos de los trabajos lo que se busca es
que lo trabajos no se retrasen con respecto a estas, pues suelen conllevar sanciones
para la producción. Será en este tipo de trabajos en los que se enfoque el estudio que
estamos describiendo. En este caso también hay distintas formas de enfocar este
problema:
ΣLi : Minimizar la suma de retrasos o retraso total. Equivalente a minimizar el retraso
medio. De forma análoga al grupo anterior se estudian ΣwiLi y Lmax, que serían la
ponderación y la minimización el retraso máximo de los trabajos, que será
Proyecto fin de Carrera 2014
15
ampliamente utilizado en este trabajo. Se tratan de unos objetivos muy parecidos a los
expuestos anteriormente.
ΣTi : Minimizar la tardanza total, que será utilizado en los últimos bloques de este
estudio. De forma análoga se definen ΣwiTi y Tmax, al igual que en los casos anteriores.
Σ(Ei + Ti): Minimizar la suma de las desviaciones de los instantes de finalización de los
trabajos respecto a sus fechas de entrega di. Cuando se establecen penaltis ui para los
adelantos y vi para los retrasos de cada trabajo, el objetivo viene a ser Σ(uiEi + viTi).
ΣUi : Minimizar el número de trabajos retrasados, que también será de amplio estudio
en este trabajo. También se estudia la minimización del coste de los trabajos
retrasados, representado por ΣwiUi .
Σ(Ui + Vi) : Minimizar el número de trabajos adelantados y retrasados. Igual que
anteriormente, también se plantea el criterio Σwi(Ui + Vi). Este objetivo es equivalente
al de maximizar los trabajos terminados justo en su fecha de entrega (on time).
3. Criterios basados en costes de inventario y utilización de máquinas
Por último nombrar los casos en los que se busca que las máquinas estén desocupadas
el menor tiempo posible mediante las siguientes fórmulas:
ΣIj : Minimizar el tiempo total en que están desocupadas las máquinas, siendo Ij = Cmax
- Σpij , y Σpij la suma de los tiempos de procesado de todos los trabajos sobre la
máquina Mj.
ΣvjIj : Minimizar el tiempo ponderado de desocupación de las máquinas, siendo vj un
peso por unidad de operación.
Proyecto fin de Carrera 2014
16
2.3 CARACTERIZACIÓN DEL PROBLEMA
Una vez definidos la mayoría de conceptos relacionados con la secuenciación de
trabajos, nos queda establecer las características que definen a nuestro problema
objeto de estudio.
Este problema, como su nombre indica, consta de m máquinas en paralelo. En ellas los
trabajos serán procesados con el fin de minimizar las variables que sean de interés a
cada uno de los tipos de problemas. Estas variables serán básicamente tres: Retraso
máximo (Lmax), Número de retrasos (ΣUi ) y Sumatorio de las tardanzas (ΣTi).
Los trabajos poseen unos datos asociados definidos: la duración con la que se procesa
cada uno de ellos y el tiempo de finalización de los mismos. Estos serán generados por
una batería de generación aleatoria.
Estos problemas son de carácter combinatorio (son de clase NP), aunque es cierto que
el número de máquinas con las que trabajemos condicionará en mayor o menor
medida la complejidad del mismo.
Para poder entender mejor el concepto de problema NP, se detalla a continuación la
clasificación según la complejidad computacional para la obtención de una solución
óptima:
• Problemas de Clase P: son aquellos problemas en los que se puede plantear un
algoritmo óptimo, es decir, se suelen dar pocos pasos hasta dar con el óptimo.
Son problemas en los que la consecución de la solución óptima es rápida.
• Problemas de Clase NP: son aquellos problemas que para resolverlos de forma
óptima requieren, al menos, un algoritmo con un número exponencial de
pasos para llegar a la solución. Son problemas muy lentos.
Como hemos dicho anteriormente nuestro problema contará con m máquinas en
paralelo, aunque existirá una diferencia entre los problemas que vamos a tratar:
algunos de ellos trabajarán con máquinas idénticas Pm y en otros casos se estudiará
con máquinas uniformes Qm.
Proyecto fin de Carrera 2014
17
CAPÍTULO 3
MODELO Pm| |Lmax
Proyecto fin de Carrera 2014
18
3. MODELO Pm| |Lmax
3.1 INTRODUCCIÓN
Se trata de resolver un modelo en el que se busca minimizar el valor de Lmax, o lo que
es lo mismo, el retraso máximo existente entre todos los trabajos. Recordamos que en
este tipo de problema las máquinas son idénticas y por tanto sus velocidades de
procesamiento son las mismas, es decir, un trabajo tarda lo mismo en procesarse
independientemente de que lo haga en una máquina o en otra.
Buscaremos implementar diferentes heurísticas sobre este problema con el objetivo
de ver cual se comporta mejor en función de unos determinados valores o variables
que serán de nuestro interés. Por ello, a través de una batería de problemas
previamente creados estudiaremos los resultados para observar cual nos proporciona
un mejor comportamiento. Se resolverán con el programa Visual Basic y básicamente
compararemos el algoritmo Conway con el algoritmo Greedy, que explicaremos a
continuación.
Proyecto fin de Carrera 2014
19
3.2 DEFINICIÓN Y OBJETO DE LAS HEURÍSTICAS
Antes de pasar a explicar las distintas heurísticas, pasamos a explicar el por qué de su
uso.
Dada la dificultad práctica para resolver de forma exacta (simplex, “ramificación y
acotación”, teoría de grafos, …) toda una serie de importantes problemas
combinatorios para los cuales, por otra parte, es necesario ofrecer alguna solución
dado su interés práctico, comenzaron a aparecer algoritmos que proporcionan
soluciones factibles (es decir; que satisfacen las restricciones del problema), las cuales,
aunque no optimicen la función objetivo, se suponen que al menos se acercan al valor
óptimo en un tiempo de cálculo razonable. Podríamos llamarlas en lugar de óptimas,
“satisfactorias”, pues al menos es de suponer que son lo suficientemente buenas para
servirnos.
Este tipo de algoritmos se denominan heurísticas, del griego “heuriskein”, encontrar
(palabra quizá no demasiado afortunada ya que, siendo más exactos, en principio lo
que hacen es buscar). En un primer momento, las heurísticas no eran bien vistas
debido a su escaso rigor matemático, si bien, poco a poco, se les fueron “abriendo las
puertas” debido a la proliferación de resultados.
Una posible definición de estos métodos es la siguiente:
“Son procedimientos simples, a menudo basados en el sentido común, que se supone
ofrecerán una buena solución (no necesariamente la óptima) a problemas difíciles, de
un modo fácil y rápido”.
Las heurísticas se suelen utilizar en las siguientes situaciones:
• Cuando no existe un método exacto de resolución o éste requiere mucho
tiempo de cálculo o memoria, como es nuestro caso, ya que trataremos con
problemas de clase NP.
• Cuando no es realmente necesario la obtención de la solución óptima, basta
con un acercamiento.
• Cuando los datos son poco fiables.
• Cuando existen fuertes limitaciones temporales.
• Dentro de un algoritmo más complejo.
Una importante ventaja que presentan las heurísticas respecto a las técnicas que
buscan soluciones exactas es que, por lo general, permiten una mayor flexibilidad para
el manejo de las características del problema.
Por otra parte, al estar fundamentadas en el sentido común en la mayoría de los casos,
suele ser más fácil de entender (por parte de los directivos de las empresas y gente no
Proyecto fin de Carrera 2014
20
experta en este tipo de problemas) la fundamentación de las heurísticas que los
complejos métodos matemáticos que utilizan la mayoría de las técnicas exactas.
Como ya hemos comentado, en las siguientes resoluciones se utilizarán estas
heurísticas, y no los algoritmos que dan el valor óptimo de los problemas ya que son
inasumibles para aquellos con gran número de máquinas y de trabajos. Precisamente,
el objeto de este estudio es descifrar que heurísticas se comportan mejor, por lo que
este no tendría sentido si fuera asumible el cálculo de la solución óptima. En adelante
se explican las dos heurísticas utilizadas.
Proyecto fin de Carrera 2014
21
3.3 HEURÍSTICA EDD&GREEDY
La heurística que en principio presenta mejores resultados es la de ordenar los
trabajos por la regla EDD (Earliest due date), que consiste en poner los trabajos en un
orden no decreciente de , es decir, de sus fechas de entrega.
Posteriormente estos trabajos deben asignarse a las máquinas según la lógica del
algoritmo de asignación Greedy, es decir, a la máquina que esté libre en el instante
mayor, siguiendo la lógica de que de esta forma se dejará hueco posteriormente para
trabajos en máquinas menos cargada.
Se debe empezar probando en máquinas más cargadas, pero si se superase la fecha de
entrega en un número mayor que el valor vigente de Lmax se debe de ir intentando en
las sucesivamente más cargadas hasta que se asigne o se agoten las máquinas. En el
caso extremo de que se agoten las máquinas se debe asignar el trabajo a la máquina
menos cargada, es decir, mediante el algoritmo Conway, no olvidándonos de
actualizar el valor de Lmax. El algoritmo terminará cuando todos los trabajos hayan
sido asignados.
Esta misma lógica que ha sido expresada con palabras ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo I.
Visto esto realizaremos, como será de costumbre a partir de ahora, tres ejemplos de
ello, que nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Pasaremos a presentar estos ejemplos puesto que serán los mismos para todos los
problemas realizados en este trabajo. Estos han sido creados aleatoriamente y sin
ninguna predisposición inicial con el objetivo de que el resultado sea el más aleatorio
posible, y con la única intención de que trabajen en ellos 3, 4 y 5 máquinas
respectivamente, por tener ejemplos representativos con distintos números de
máquinas.
Para el primer de los tres ejemplos, con tres máquinas, los trabajos que se introducen
en el programa son los de la izquierda, mientras que a la derecha podemos observar
estos mismos ordenados por la regla EDD, con objeto de que sea más visible su
posterior orden dentro de las máquinas:
Proyecto fin de Carrera 2014
22
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
13 20 1 5 3 2
5 3 2 2 5 15
8 16 3 9 8 7
4 24 4 4 9 11
3 31 5 7 11 17
12 30 6 4 15 8
9 8 7 8 16 3
4 15 8 4 18 16
16 29 9 13 20 1
2 21 10 2 21 10
4 9 11 11 22 13
8 31 12 4 24 4
11 22 13 16 29 9
13 34 14 12 30 6
2 5 15 8 31 12
4 18 16 3 31 5
7 11 17 13 34 14
Una vez vistos estos vamos a proceder a mostrar el orden de estos trabajos dentro de
las máquinas, con el tiempo empleado por cada máquina en procesarlos, así como el
mayor retraso producido. Observar que en cada iteración, es decir, cada vez que se
asigna un nuevo trabajo, he dejado el valor anterior del tiempo ocupado por la
máquina así como el del retraso mayor (Lmax), con objeto de que sea más sencilla la
comprobación. Destacar también que en cada cuadro se ha asignado el número del
trabajo que corresponde, no la duración ni la fecha de entrega. De esta forma quedará:
Nºs de los trabajos Tiempos
M1 7 3 13 12 5 9 17 28 36 39
M2 17 1 10 4 6 7 20 22 36 38
M3 2 15 11 8 16 9 14 7 11 15 19 35 48
Lmax 2 6 8 14
Para comprobar si el algoritmo dado en el código es o no correcto he programado un
código que extrae no solo el valor del retraso máximo, como haremos con la colección
de 5700 problemas que es objeto de este estudio, sino otros muchos valores que nos
permite acotar muchísimo el nivel de error del mismo. Si además tenemos en cuenta
Proyecto fin de Carrera 2014
23
que resolveremos a mano otros dos problemas, la probabilidad de que el código esté
equivocado es mínima, por lo que considero que es un estudio de bastante fiabilidad.
De esta forma, la salida del código programado para este problema será:
Lmax sinConway:
Maq. 1:
Trab. 7 Dur. 9; Trab. 3 Dur. 8; Trab. 13 Dur. 11; Trab. 12 Dur. 8; Trab. 5 Dur. 3;
Dur. Total: 39
Maq. 2:
Trab. 17 Dur. 7; Trab. 1 Dur. 13; Trab. 10 Dur. 2; Trab. 4 Dur. 4; Trab. 6 Dur. 12;
Dur. Total: 38
Maq. 3:
Trab. 2 Dur. 5; Trab. 15 Dur. 2; Trab. 11 Dur. 4; Trab. 8 Dur. 4; Trab. 16 Dur. 4; Trab. 9 Dur. 16; Trab. 14 Dur. 13;
Dur. Total: 48
Lmax sinConway: 14
Por lo que se observa que el resultado de ambos problemas es idéntico, lo que supone
una garantía de la exactitud del código.
El segundo de los problemas viene dado por los siguientes datos, donde de nuevo a la
izquierda vemos aquellos que se ingresan en el código, mientras que los que quedan a
la derecha son los mismos ordenados por la regla EDD para mejorar su posterior
visualización:
Proyecto fin de Carrera 2014
24
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
5 13 1 15 6 4
8 10 2 6 8 7
1 12 3 8 10 2
15 6 4 2 11 8
18 32 5 1 12 3
9 14 6 5 13 1
6 8 7 9 14 6
2 11 8 7 21 9
7 21 9 18 32 5
De nuevo, resolviendo estos trabajos conforme al algoritmo indicado anteriormente,
los resultados son los que se muestran a continuación, pudiendo ver tanto el valor de
Lmax como los tiempos empleados por las máquinas, valores comparables con el texto
de salida del código:
Nºs de los trabajos Tiempos
M1 7 2 1 9 6 14 19 26
M2 4 8 3 5 15 17 18 36
M3 6 9
M4
Lmax 9
Y la salida del código del mismo será:
Lmax sinConway:
Maq. 1:
Trab. 7 Dur. 6; Trab. 2 Dur. 8; Trab. 1 Dur. 5; Trab. 9 Dur. 7;
Dur. Total: 26
Maq. 2:
Proyecto fin de Carrera 2014
25
Trab. 4 Dur. 15; Trab. 8 Dur. 2; Trab. 3 Dur. 1; Trab. 5 Dur. 18;
Dur. Total: 36
Maq. 3:
Trab. 6 Dur. 9;
Dur. Total: 9
Maq. 4:
Dur. Total: 0
Lmax sinConway: 9
Por lo que podemos ver de nuevo que el resultado es idéntico, confirmando nuestro
código a la espera del tercer problema.
Por último, para el ejercicio propuesto con 5 máquinas, tenemos como datos
insertados a la izquierda, y ya ordenados mediante EDD a la derecha, los siguientes:
Proyecto fin de Carrera 2014
26
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
1 2 1 1 2 1
4 6 2 4 6 2
8 21 3 5 7 15
5 13 4 5 9 6
9 18 5 2 11 7
5 9 6 5 12 20
2 11 7 5 13 4
13 26 8 4 14 16
9 17 9 11 15 11
4 22 10 5 15 17
11 15 11 9 17 9
9 31 12 9 18 5
8 29 13 8 21 3
7 32 14 4 22 10
5 7 15 14 22 21
4 14 16 7 23 19
5 15 17 13 26 8
8 28 18 8 28 18
7 23 19 8 29 13
5 12 20 9 31 12
14 22 21 7 32 14
Que resueltos de forma manual como los anteriores nos dan el resultado que se
observa a continuación:
Nºs de los trabajos Tiempos
M1 6 17 21 12 5 10 24 33
M2 1 2 7 20 3 1 5 7 12 20
M3 11 8 14 11 24 31
M4 9 5 10 18 9 18 22 30
M5 15 4 16 19 13 5 10 14 21 29
Lmax 2
Por último, la salida del código para este problema será:
Lmax sinConway:
Maq. 1:
Proyecto fin de Carrera 2014
27
Trab. 6 Dur. 5; Trab. 7 Dur. 2; Trab. 20 Dur. 5; Trab. 3 Dur. 8; Trab. 10 Dur. 4; Trab. 12 Dur. 9;
Dur. Total: 33
Maq. 2:
Trab. 1 Dur. 1; Trab. 2 Dur. 4; Trab. 4 Dur. 5; Trab. 16 Dur. 4; Trab. 8 Dur. 13; Trab. 14 Dur. 7;
Dur. Total: 34
Maq. 3:
Trab. 11 Dur. 11; Trab. 18 Dur. 8; Trab. 13 Dur. 8;
Dur. Total: 27
Maq. 4:
Trab. 9 Dur. 9; Trab. 5 Dur. 9; Trab. 19 Dur. 7;
Dur. Total: 25
Maq. 5:
Trab. 15 Dur. 5; Trab. 17 Dur. 5; Trab. 21 Dur. 14;
Dur. Total: 24
Lmax sinConway: 2
En la que aunque vemos que el orden de algunos trabajos y el tiempo de ocupación de
algunas máquinas no son similares, coincide el retraso máximo, que es lo relevante.
Esto es debido a que se repiten algunos tiempos de finalización en los trabajos, como
en los casos del 11 y el 17 y el 10 y el 21, que hace que exista, para la misma heurística,
soluciones alternativas. Por ello la disparidad de opciones no es preocupante y desde
luego no síntoma de la invalidez del código, como veremos en apartados posteriores.
Por tanto podemos dar por buena la realización de esta heurística y pasar a comentar
la siguiente.
Proyecto fin de Carrera 2014
28
3.4 HEURÍSTICA EDD&CONWAY
Esta va a ser la heurística con la que comparemos la anterior, que aunque tienen varios
puntos de coincidencia, como veremos en los resultados finales, da un resultado
diferente.
Al igual que para la heurística Greedy lo que debemos de hacer en primer lugar es
ordenar los trabajos por la regla EDD, es decir, en orden no decreciente de , es decir,
de sus fechas de entrega.
Una vez hecho esto, como hemos realizado en cada uno de los ejemplos vistos
anteriormente, asignaremos cada trabajo en dicho orden mediante el algoritmo
Conway, es decir, a la máquina que este libre en el instante menor.
Dado que siempre que se asigne a la máquina menos ocupada se tratará del caso más
extremo no debemos intentar la asignación con el resto de máquinas, puesto que si
para esta no es posible que el tiempo de ejecución menos la fecha de entrega superen
al Lmax vigente, para las otras máquinas tampoco sucederá.
Si como hemos dicho, se excede del valor de Lmax, debemos pasar de nuevo a asignar
a la máquina menos cargada, al igual que hacíamos en el anterior algoritmo, sin por
supuesto olvidarnos de actualizar el valor de Lmax, que es el que estamos buscando y
el que queremos minimizar.
Esta misma lógica que ha sido expresada con palabras, ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo II.
Visto esto veremos, como hicimos en el apartado anterior, tres ejemplos de ello, que
nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Como ya dijimos anteriormente, los ejemplos realizados son los mismos para todos los
tipos de problemas, por lo que para no repetir aspectos comunes, como pudiera ser
los datos de los trabajos así como su orden con respecto al algoritmo EDD, se han
presentado estos en el Anexo III para que sean de fácil disposición al lector.
Una vez aclarados estos aspectos pasaremos a resolver, tal y como hicimos en el
apartado anterior, los problemas a mano con el objetivo de comprobar la validez del
código.
Empezaremos por el de 3 máquinas, pero esta vez no presentaremos los datos, ya que,
como hemos dicho, están expuestos en el Anexo III.
Por tanto, conforme a esta asignación, los trabajos en las máquinas quedarían de la
siguiente forma:
Proyecto fin de Carrera 2014
29
Nºs de los trabajos Tiempos
M1 2 17 1 6 14 5 12 25 37 50
M2 7 16 10 13 5 12 9 13 15 26 29 37
M3 15 11 8 3 4 9 2 6 10 18 22 38
Lmax 2 5 9 16
Ahora veremos cuál es el resultado que nos da el código propuesto en el Anexo II, con
el objetivo de comprobar su veracidad. Este será el resultado del mismo:
Lmax Conway:
Maq. 1:
Trab. 7 Dur. 9; Trab. 3 Dur. 8; Trab. 4 Dur. 4; Trab. 9 Dur. 16; Trab. 14 Dur. 13;
Dur. Total: 50
Maq. 2:
Trab. 2 Dur. 5; Trab. 17 Dur. 7; Trab. 1 Dur. 13; Trab. 6 Dur. 12;
Dur. Total: 37
Maq. 3:
Trab. 15 Dur. 2; Trab. 11 Dur. 4; Trab. 8 Dur. 4; Trab. 16 Dur. 4; Trab. 10 Dur. 2; Trab. 13 Dur. 11; Trab. 12 Dur. 8; Trab. 5 Dur. 3;
Dur. Total: 38
Lmax Conway: 16
Vemos que los resultados de ambos son exactamente los mismos, por lo que el primer
paso hacia la comprobación que estamos efectuados ha sido dado con éxito.
Proyecto fin de Carrera 2014
30
Ahora pasaremos al problema de 4 máquinas, en el que la asignación manual que
hemos realizado es la siguiente, incluyendo los valores en cada iteración:
Nºs de los trabajos Tiempos
M1 2 5 8 26
M2 7 6 6 15
M3 4 15
M4 8 3 1 9 2 3 8 15
Lmax 9
Y, como siempre, vemos el resultado que nos proporciona el programa Visual Basic y lo
comparamos con el mismo:
Lmax Conway:
Maq. 1:
Trab. 2 Dur. 8; Trab. 5 Dur. 18;
Dur. Total: 26
Maq. 2:
Trab. 7 Dur. 6; Trab. 6 Dur. 9;
Dur. Total: 15
Maq. 3:
Trab. 4 Dur. 15;
Dur. Total: 15
Maq. 4:
Trab. 8 Dur. 2; Trab. 3 Dur. 1; Trab. 1 Dur. 5; Trab. 9 Dur. 7;
Dur. Total: 15
Proyecto fin de Carrera 2014
31
Lmax Conway: 9
De nuevo el resultado es idéntico, por lo que la comprobación es perfecta y podemos
para al tercer y último ejemplo de este bloque de Pm||Lmax, antes de ejecutar los
1140 ejemplos pertenecientes a este capítulo.
Así, pasamos a ver cuál es el resultado de nuestra resolución manual para el tercer
problema de 5 máquinas:
Nºs de los trabajos Tiempos
M1 15 17 21 14 5 10 24 31
M2 5 11 18 5 16 24
M3 1 20 9 10 13 1 6 15 19 27
M4 2 16 3 8 4 8 16 29
M5 7 4 5 19 12 2 7 16 23 32
Lmax 1 2 3
Y el resultado proporcionado por el código del programa que estamos utilizando sería
el que se muestra a continuación:
Lmax Conway:
Maq. 1:
Trab. 15 Dur. 5; Trab. 17 Dur. 5; Trab. 21 Dur. 14; Trab. 14 Dur. 7;
Dur. Total: 31
Maq. 2:
Trab. 6 Dur. 5; Trab. 11 Dur. 11; Trab. 18 Dur. 8;
Dur. Total: 24
Maq. 3:
Proyecto fin de Carrera 2014
32
Trab. 1 Dur. 1; Trab. 20 Dur. 5; Trab. 9 Dur. 9; Trab. 10 Dur. 4; Trab. 13 Dur. 8;
Dur. Total: 27
Maq. 4:
Trab. 2 Dur. 4; Trab. 16 Dur. 4; Trab. 3 Dur. 8; Trab. 8 Dur. 13;
Dur. Total: 29
Maq. 5:
Trab. 7 Dur. 2; Trab. 4 Dur. 5; Trab. 5 Dur. 9; Trab. 19 Dur. 7; Trab. 12 Dur. 9;
Dur. Total: 32
Lmax Conway: 3
Que como se comprueba, de nuevo es idéntico, por lo que podemos asegurar que los
códigos de ambas heurísticas son correctos, con lo que pasamos resolver la colección
de problemas generados y compararlas en el siguiente apartado.
Proyecto fin de Carrera 2014
33
3.5 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS
Una vez obtenidos los datos de las comprobaciones, vamos a analizarlos para ver cuál
es la tendencia en la comparación de ambas heurísticas.
Vemos que para el caso de tres máquinas Lmax aumenta dos unidades de 14 a 16,
comportándose mejor el algoritmo Greedy. Por otro lado, para el ejemplo de 4
máquinas no existe variación, pues para ambas heurísticas se produce un retraso
máximo de 9. Por último, para el ejemplo con 5 máquinas de nuevo se comporta mejor
el algoritmo Greedy, con Lmax de 2, mientras que Conway presenta 3.
Este interesante razonamiento para los ejemplos nos permite observar, como
habíamos previsto, que el algoritmo Greedy se comporta mejor, pero debemos hacer
un estudio más detallado del mismo, por lo que resolveremos la batería de 1140
problemas que teníamos prevista para este apartado.
Puesto que el número de problemas a resolver es tan extenso, vamos a clasificarlos
por el tipo de variables, por lo que para cada conjunto de variables resolveremos un
total de 10 problemas. Por tanto resolveremos 57 tipos de problemas con variables
distintas que compararemos entre sí.
Por si resulta de interés del lector, hemos añadido en el Anexo IV los valores de Lmax
que hemos obtenido, después de hacer la media, para cada tipo de problema, tanto
para la heurística Greedy como para la Conway, así como la diferencia a nivel
porcentual de ambos, con el objetivo de hacer un estudio de las mismas.
Destacar que hay variables como la carga que aún no han sido definidas. O el lector
quizás pueda desconocer cómo se han obtenido los problemas que se han utilizado.
Como adelanto decir que se han generado de forma aleatoria y que todos los aspectos
sobre esto se explicarán en el capítulo de Generación y lectura que se encuentra en las
últimas partes del trabajo. De cualquier forma esto no nos será relevante en este
momento.
Debido a la gran cantidad de datos de salida que tenemos tras implementar esta
cantidad de problemas en nuestro algoritmo, y que han sido mostrados en forma de
media en el Anexo IV, nos vemos obligados a utilizar unas gráficas con nos permitan
ver de forma más clara cuál ha sido el comportamiento de las heurísticas en función de
las variables.
Debido a que tenemos 3 variables, y solo podemos hacer gráficas bidimensionales,
puesto que el papel no nos permite otra cosa de forma clara, mostraremos 4 gráficas,
una para cada número de máquinas utilizadas, que nos permita ver el comportamiento
de estas con respecto a la variación en el número de trabajos y la carga, es decir, lo
Proyecto fin de Carrera 2014
34
mucho o poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1
sería muy comprimido y C3 poco comprimido.
La primera gráfica sería para problemas con 4 máquinas, expresando porcentajes
positivos si el algoritmo Greedy se comporta mejor que el Conway, y negativos en caso
contrario, como se ve a continuación:
Se ve que para pocas máquinas y pocos trabajos, como ocurre a la izquierda, ambas
heurísticas están muy igualadas, incluso comportándose en algunos casos la heurística
Conway mejor que la Greedy, lo cual es absolutamente puntual.
A medida que avanza el número de trabajos los problemas comprimidos no presentan
variación, puesto que se comportan relativamente igual para ambas heurísticas. Sin
embargo, para problemas normales y poco comprimidos la variabilidad se acentúa,
destacando que de media se comporta mejor el algoritmo Greedy que el Conway,
disminuyendo esa ventaja con el número de trabajos.
Veremos ahora para 8 máquinas:
Proyecto fin de Carrera 2014
35
En este caso, la variabilidad se aprecia mucho más alta para problemas de compresión
intermedia, comportándose mejor el algoritmo Greedy, mientras que para problemas
muy comprimidos o muy poco comprimidos el comportamiento ronda la diferencia
nula, habiendo de nuevo algún caso en el que Conway se comporta mejor. Vemos
también que cuando más se nota la diferencia, como veíamos antes, es para valores
medios del número de trabajos y de la compresión.
Veremos ahora el caso de los problemas de 16 máquinas:
Proyecto fin de Carrera 2014
36
Se repite de nuevo la tendencia comentada anteriormente. Para problemas muy
comprimidos y poco comprimidos la diferencia se mantiene estable, aunque superior
para casos muy comprimidos, ya que la de los poco comprimidos se mantiene a cero.
Como venimos diciendo, para valores intermedios de trabajos y compresión la
diferencia se acentúa, llegando a su pico máximo, visto aquí muy claramente.
Por último, para problemas de gran número de máquinas, 32 en este caso:
Vemos que para este caso, de nuevo, para problemas poco comprimidos se presenta
que la variación es nula. Sin embargo, para aquellos problemas de compresión normal
la variación es altamente ascendente con el número de trabajos, mientras que para
problemas muy comprimidos es definitivamente descendente.
Con todo esto me atrevo a sacar una serie de conclusiones para problemas
Pm||Lmax, en la comparación del algoritmo Greedy con el Conway, que son las
siguientes:
• En líneas generales, la heurística Greedy se suele comportar mejor que la
Conway para este tipo de problemas.
• Para trabajos sin compresión especial, C2 (definiremos como se ha obtenido el
parámetro de la compresión en el apartado de experimentación), se produce
un punto de máxima variación en el entorno de la relación
.
Proyecto fin de Carrera 2014
37
• Para trabajos de baja compresión, C3, ambas heurísticas suelen comportase
igual, salvo para poco número de máquinas en el que el algoritmo Greedy
comporta una ligera mejoría. Esto se puede deber a que al haber tan pocas
máquinas, el problema se comprime algo más y por lo tanto no esta tan poco
comprimido como en el resto de casos.
• Para trabajos de alta compresión pasa justamente lo contrario. Para bajo
número de máquinas, encontramos trabajos súper comprimidos, y por tanto la
diferencia es nula. A medida que el número de máquinas va subiendo los
problemas se van descomprimiendo, como se puede observar, sobre todo para
bajos número de trabajos, lo que hace que el problema este aún menos
comprimido.
Por tanto, como conclusión general, para Pm||Lmax, Greedy funciona mejor que
Conway para valores de las variables cercanos al punto medio de compresión, y
mejor cuanto más se acerque al entorno de la relación . En
él, el valor máximo de la diferencia ronda el 13%. A medida que nos alejamos
de este entorno la diferencia entre ambas disminuye, siendo menos relevante la
heurística utilizada.
Proyecto fin de Carrera 2014
38
CAPÍTULO 4
MODELO Pm| |ΣUi
Proyecto fin de Carrera 2014
39
4. MODELO Pm| |ΣUi
4.1 INTRODUCCIÓN
En este tipo de problemas lo que se busca es minimizar el número de retrasos, en vez
de minimizar el retraso máximo, como se pretendía en el bloque anterior. De nuevo se
trata de problemas Pm, con máquinas idénticas y por tanto mismas velocidades de
procesamiento, es decir, un trabajo tarda lo mismo en procesarse
independientemente de que lo haga en una máquina o en otra.
Buscaremos implementar diferentes heurísticas sobre este problema con el objetivo
de ver cual se comporta mejor en función de unos determinados valores o variables
que serán de nuestro interés. Por ello, a través de una batería de problemas
previamente creados estudiaremos los resultados para observar cual nos proporciona
un mejor comportamiento. Se resolverán con el programa Visual Basic y básicamente,
al igual que hicimos para el caso de Lmax, compararemos el algoritmo Conway con el
algoritmo Greedy que explicaremos a continuación.
Proyecto fin de Carrera 2014
40
4.2 HEURÍSTICA EDD&GREEDY
La heurística que en principio presenta mejores resultados es la de ordenar los
trabajos por la regla EDD (Earliest due date), que consiste en poner los trabajos en un
orden no decreciente de , es decir, de sus fechas de entrega, como hemos hecho
también para todos los problemas del caso de Lmax.
Posteriormente estos trabajos deben asignarse a las máquinas según la lógica del
algoritmo de asignación Greedy, es decir, a la máquina que esté libre en el instante
mayor, siguiendo la lógica de que de esta forma se dejará hueco posteriormente para
trabajos en máquinas menos cargada.
Se debe empezar probando en máquinas más cargadas, pero si el tiempo de
finalización fuese superior a la fecha de entrega de este trabajo se debe de ir
intentando en las sucesivamente menos cargadas hasta que se asigne o se agoten las
máquinas.
En este caso extremo de que se agoten las máquinas se debe buscar el trabajo de
mayor duración de los ya asignados. Si este trabajo fuese el mismo que estamos
intentando asignar en esta iteración simplemente de descartaría. Si existiese un
trabajo con mayor duración de los ya asignados deberíamos descartar este y colocar el
trabajo de esta iteración en la máquina en la que se encontraba el anterior. De esta
forma conseguimos que se descarte un trabajo, cuando igualmente era necesario
descartar uno, pero dejando mayor espacio para otros que pudieran venir en el futuro,
y por tanto, reduciendo la probabilidad de retraso de los mismos. No debemos
olvidarnos de aumentar en una unidad el valor del número de retrasos, Ui. El algoritmo
terminará cuando todos los trabajos hayan sido asignados.
Esta misma lógica, que ha sido expresada con palabras, ha sido programada en
lenguaje C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo V.
Visto esto veremos, como hemos visto en los anteriores capítulos, tres ejemplos de
ello, que nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Puesto que son los mismos para todos los problemas realizados en este trabajo, no
pasaremos a describirlos en profundidad como hicimos anteriormente. Tan solo decir
que son 3 ejemplos, de tres, cuatro y cinco máquinas, y cuyos datos de trabajos están
en el Anexo III, como ya hemos comentado.
De esta forma, para el primero de los tres ejemplos, compuesto por 3 máquinas como
ya hemos dicho, la resolución manual será la que se muestra a continuación:
Proyecto fin de Carrera 2014
41
Nºs de los trabajos Tiempos
M1 2 13 7 5 14 13 27 27
M2 17 8 6 12 7 11 23 31
M3 15 11 3 16 10 4 2 6 14 18 20 24
Ui 2 7 1 9
Se puede observar que para este tipo de problemas hay trabajos que han sido
tachados y descartados, es decir, han pasado a estar en el bloque de Ui. Asimismo
comentar que al lado de Ui no se ha puesto el retraso de los trabajos, como hacíamos
con Lmax, ni siquiera el número de trabajos retrasados. Hemos puesto el número de
los trabajos que han sido retrasados por ser mucho más visual y porque es el dato que
nos muestra el código. De esta forma, para este problema el número de trabajos
retrasados serían 4, mientras que los trabajos retrasados serían el número 2, el
número 7, el 1 y el número 9.
Una vez aclarado, podemos ver cuál es la salida que nos proporciona el programa, de
cara a ver su funcionalidad:
SumUisC:
Trabajos no asignados:
Trab. 2, Trab. 7, Trab. 1, Trab. 9,
SumUisC: 4
Como podemos ver, la salida en este caso no es tan extensa como antes, y los datos
son correctos, según lo analizado anteriormente. Por ello podemos dar como bueno el
código en esta primera prueba y pasar a analizar el segundo problema.
Para este segundo problema, de 4 máquinas, como ya hemos visto en los casos
anteriores, la resolución manual nos proporciona los siguientes datos:
Proyecto fin de Carrera 2014
42
Nºs de los trabajos Tiempos
M1
M2 6 9
M3 2 8 3 5 8 10 11
M4 7 1 9 6 11 18
Ui 4
En este problema, al contrario del anterior, no ha habido ningún trabajo que haya
tenido que ser descartado ya habiendo sido asignado, por lo que no hay ninguno
tachado. Sin embargo sí que uno ha sido descartado, pero ha sido el de mayor
duración de los asignados hasta el momento.
Vamos a ver si estos cálculos coinciden con la salida del código programado para este
tipo de problemas:
SumUisC:
Trabajos no asignados:
Trab. 4,
SumUisC: 1
Efectivamente coincide, siendo el trabajo descartado el mismo que habíamos
considerado nosotros, por lo que el código sigue según lo previsto con su viabilidad.
Una vez pasado el trámite de los dos problemas solo nos queda comprobar el tercero
de ellos, el que está compuesto por 5 máquinas, de modo que la resolución manual
sería la siguiente:
Nºs de los trabajos Tiempos
M1 9 5 10 12 9 18 22 31
M2 11 8 14 11 24 31
M3 6 17 5 10
M4 15 4 16 19 13 5 10 14 21 29
M5 1 2 7 20 3 18 1 5 7 12 20 28
Ui 21
Proyecto fin de Carrera 2014
43
Al igual que pasaba en el caso anterior, no ha habido ningún trabajo que haya tenido
que ser descartado ya habiendo sido asignado, por lo que no hay ninguno tachado. Sin
embargo sí que uno ha sido descartado, el trabajo 21, pero habiendo sido el de mayor
duración de los asignados hasta el momento.
Visto esto veremos cuál es la solución dada por el programa, para terminar de ver si
funciona correctamente:
SumUisC:
Trabajos no asignados:
Trab. 21,
SumUisC: 1
Vemos que efectivamente coincide, por lo que podemos estar seguros de que el
programa está funcionando correctamente, y por tanto, podemos utilizarlo para
resolver la colección de 570 problemas que tenemos prevista para este tipo de
ejercicio.
Una vez comprobado esto podemos pasar a analizar el siguiente tipo de problemas, el
cual vamos a comparar con el ya analizado.
Proyecto fin de Carrera 2014
44
4.3 HEURÍSTICA EDD&CONWAY
Esta va a ser la heurística con la que comparemos la anterior, que aunque tienen varios
puntos de coincidencia, como veremos en los resultados finales, da un resultado
diferente.
Al igual que para la heurística Conway lo que debemos hacer en primer lugar es
ordenar los trabajos por la regla EDD, es decir, en orden no decreciente de , es decir,
de sus fechas de entrega.
Una vez hecho esto, como hemos realizado en cada uno de los ejemplos vistos
anteriormente, asignaremos cada trabajo en dicho orden mediante el algoritmo
Greedy, es decir, a la máquina mas ocupada, como su propio nombre indica en inglés:
avaricioso.
Dado que siempre que se asigne a la máquina mas ocupada se tratará del caso más
extremo no debemos intentar la asignación con el resto de máquinas, puesto que si
para esta no es posible que el tiempo de ejecución supere a la fecha de entrega de
este trabajo, para las otras máquinas tampoco sucederá.
Si como hemos dicho, se excede del valor de de la fecha de entrega, debemos
descartar uno de los trabajos, por lo que, al igual que antes, debemos ver cuál de los
trabajos que ya han sido asignados, o el que estamos asignando, es el de mayor
duración. Este es el trabajo que debemos descartar, y si se trata de uno ya asignado,
sustituir el de esta iteración por el ya asignado.
Esta misma lógica que ha sido expresada con palabras, ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo VI.
Visto esto veremos, como hemos hecho en el resto de apartados, tres ejemplos de
ello, que nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Para no repetir de nuevo lo ya expuesto, decimos que los datos de estos ejercicios que
se van a realizar a continuación están expuestos en el Anexo III, por si se quieren
consultar, tanto en el orden dado al programa como ordenados según la regla EDD.
Una vez aclarados estos aspectos pasaremos a resolver, tal y como hicimos en el
apartado anterior, los problemas a mano con el objetivo de comprobar la validez del
código.
Empezaremos por el de 3 máquinas. Por tanto, conforme a esta asignación, los
trabajos en las máquinas quedarían de la siguiente forma:
Proyecto fin de Carrera 2014
45
Nºs de los trabajos Tiempos
M1 17 1 13 12 5 7 18 26 29
M2 11 3 4 6 4 12 16 28
M3 15 8 16 10 9 14 2 6 10 12 25
Ui 2 7 1 9
Como pasaba con el apartado anterior, hay trabajos que han sido descartados después
de asignados. Curiosamente para este problema en el apartado anterior fueron
descartados los cuatro mismos trabajos: el 2, 7 1 y 9. Sin embargo fueron descartados
después de haberse asignado el 2 y el 7. En este caso ha pasado justo lo contrario, y los
descartados después de asignados han sido los otros dos, el 1 y el 9. Sin embargo, el
número total de descartados no ha variado, siguen siendo cuatro.
Tras esta reflexión veamos la solución que nos aporta el programa Visual Basic:
SumUiC:
Trabajos no asignados:
Trab. 2, Trab. 7, Trab. 1, Trab. 9,
SumUisC: 4
De nuevo coincide plenamente con lo que habíamos calculado, y también con la
solución que se nos daba para el apartado anterior, por lo que de momento parece no
afectar el cambio de heurística. El código vemos que es correcto.
Por tanto pasaremos ahora al ejemplo siguiente, el de 4 máquinas, cuyo resultado
manual es el que vemos:
Nºs de los trabajos Tiempos
M1 3 1 5 1 6 24
M2 8 6 2 11
M3 2 8
M4 7 9 6 13
Ui 4
Proyecto fin de Carrera 2014
46
En esta ocasión vemos que no ha habido trabajos rechazados después de asignados, y
tan solo uno rechazado, que es el 4.
No tenemos mucho más que comentar, salvo ver el resultado de la salida del
programa:
SumUiC:
Trabajos no asignados:
Trab. 4,
SumUisC: 1
Como vemos es correcto y además coincide con la del apartado anterior, por lo que
estamos verificando que esta heurística se ve mucho menos afectada que para el caso
de Lmax, donde si se habían modificado los resultados considerablemente.
Vamos a pasar ahora al último ejemplo para comprobar la corrección de este cuarto
código que estamos utilizando. Para este último ejemplo, como venimos haciendo,
hemos utilizado el caso de las 5 máquinas, con lo que el resultado manual sería el
siguiente:
Nºs de los trabajos Tiempos
M1 7 4 3 13 2 7 15 23
M2 6 9 19 14 5 9 16 23
M3 15 17 8 5 10 23
M4 2 16 10 18 4 8 12 20
M5 1 20 5 12 1 6 15 24
Ui 11 21
Proyecto fin de Carrera 2014
47
Cabe destacar que en este caso, pese a ser más largo el problema, tampoco ha habido
trabajos descartados después de ser asignados, quizás por la poca compresión del
mismo al tener cinco máquinas, lo que ha hecho que solo existan dos trabajos
descartados, el 11 y el 21.
Vamos a ver cuál será para este el resultado de la salida del programa:
SumUisC:
Trabajos no asignados:
Trab. 11, Trab. 21,
SumUisC: 2
Vemos que esta vez sí, el resultado para esta heurística ha sido peor, por lo que ya
tenemos un caso de referencia para ver cual se comporta mejor. En la anterior
heurística solo se descartó un trabajo, el 21, mientras que aquí se ha descartado
también el 11, por lo que suman dos en total. Vemos igualmente que el código
podemos afirmar que es correcto ya que en los tres casos coincide con la
experimentación manual.
Una vez que hemos estudiado todos los problemas pasaremos a realizar la
comparación de las dos heurísticas para ver cual se comporta mejor.
Proyecto fin de Carrera 2014
48
4.4 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS
Una vez obtenidos los datos de las comprobaciones, vamos a analizarlos para ver cuál
es la tendencia en la comparación de ambas heurísticas.
Vemos que para los ejemplos que hemos analizado no existe demasiada diferencia,
como pasaba con el caso de Lmax, por lo que no podemos decir que exista una
tendencia clara. Sin embargo, el único problema que muestra una discrepancia entre
ambas heurísticas es el problema de 5 máquinas, el tercero, ya que para Greedy
descarta un trabajo mientras que para Conway descarta dos. Los otros dos problemas
descartan los mismos trabajos. D
Por tanto, dado que en Lmax también se comportaba Greedy mejor que Conway, y que
la única discrepancia que tenemos para este caso también apoya esta teoría la
presupondremos como cierta, por lo que se tomará como referencia positiva el que
Greedy se comporte mejor que Conway de cara a las gráficas que realizaremos.
A pesar de este razonamiento debemos hacer un estudio más detallado del mismo,
por lo que resolveremos la batería de 1140 problemas que teníamos prevista para este
apartado.
Puesto que el número de problemas a resolver es tan extenso, vamos a clasificarlos
por el tipo de variables, como hicimos también para el caso de Lmax. Para cada
conjunto de variables resolveremos un total de 10 problemas, por lo que nos queda
que resolver 57 tipos de problemas con variables distintas que compararemos entre
ellas.
Por si resulta de interés del lector, hemos añadido en el Anexo VII los valores de ΣUi
que han salido de media para cada tipo de problema, tanto para la heurística Greedy
como para la Conway, así como la diferencia a nivel porcentual de ambos, con el
objetivo de hacer un estudio de las mismas.
Como ya comentamos en la comparación del apartado anterior, la gran cantidad de
datos con la que estamos tratando, tanto de variables, como de máquinas, trabajos y
datos, nos obligan a no prescindir del uso de gráficas, que mostraremos y
describiremos a continuación.
Debido a que tenemos 3 variables, y solo podemos hacer gráficas bidimensionales,
puesto que el papel no nos permite otra cosa de forma clara, mostraremos 4 gráficas,
una para cada número de máquinas utilizadas, que nos haga ver el comportamiento de
estas con respecto a la variación en el número de trabajos y la carga, es decir, lo muy o
poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1 sería
muy comprimido y C3 poco comprimido.
Proyecto fin de Carrera 2014
49
La primera gráfica sería para problemas con 4 máquinas, siendo porcentajes positivos
que el algoritmo Greedy se comporta mejor que el Conway, y negativos en caso
contrario, como se ve a continuación:
Se observa como la gráfica de compresión intermedia, C2, viene siendo la que con
mayor diferencia se comporta, como pasaba en el caso de Lmax, aunque bien es
verdad que para 25 trabajos presenta un porcentaje negativo, es decir, de media se
comporta mejor para Conway que para Greedy, algo que podemos ver como algo
meramente puntual.
Vemos que para problemas muy comprimidos, C1, el comportamiento es similar al ya
descrito. Cuanta mayor compresión (aumento de trabajos), mayor igualdad presentan
ambas heurísticas. Mientras, para el caso de menos compresión, C3, la variabilidad es
muy alta por lo que debemos esperar a ver las siguientes gráficas.
De este modo pasamos a observar la gráfica para este tipo de problemas con el caso
de 8 máquinas, que presentamos a continuación:
Proyecto fin de Carrera 2014
50
Para este caso continúa destacando la compresión media, es decir, C2, que tiene una
diferencia mucho mayor que el resto de compresiones. Destacar que en ambas
gráficas se va consolidando la teoría del punto máximo, que se suele acercar al
entorno considerado para Lmax, aunque en este caso presenta mucha menos
variabilidad para esta cantidad de máquinas que en aquel.
Por otra parte vemos que los problemas de alta compresión, C1, siguen en su línea
descendiente, es decir, disminuyendo la diferencia a medida que se acentúa la
compresión, o lo que es lo mismo, aumenta el número de trabajos. Igualmente, a
medida que disminuye la compresión en los problemas C3 (aumenta el número de
máquinas), la diferencia tiende a cero, siendo ya solo para 200 trabajos no nula.
Tras este análisis vamos a observar la gráfica de los problemas de 16 máquinas para
ver si nos facilita nueva información:
Proyecto fin de Carrera 2014
51
En este tipo de problemas de 16 máquinas se aprecia de nuevo claramente la
superioridad de los problemas de compresión intermedia, haciendo que estos sean los
que más diferencia tienen. Sin embargo en esta gráfica se ve que la variabilidad es
prácticamente nula con respecto a otras gráficas para problemas C2, lo que hace que
sea más difícil la localización del punto máximo.
Por otra parte los problemas tipo C1 siguen en su línea, como ya hemos comentado,
de disminución de la variabilidad cuando aumenta el número de trabajos, de forma
que reafirma nuestra teoría. El caso de los problemas C3, como ya comentábamos,
sigue según lo esperado. El número de máquinas ya se ha hecho demasiado grande por
lo que la diferencia entre heurísticas ya es completamente nula.
Ahora por último vamos a analizar la gráfica de los problemas de 32 máquinas, que se
muestra a continuación:
Proyecto fin de Carrera 2014
52
Esta, como se ve, sigue en la misma línea, por lo que tiene poco que comentar. La
superioridad de los problemas de compresión intermedia sigue vigente, apreciándose
además el punto máximo, por lo que es de mayor utilidad, aunque sigue teniendo
menor variabilidad que en el caso de Lmax.
Para los problemas de mayor compresión, C1, sigue en la misma línea que las
anteriores, descendente con el número de trabajos. Por otro lado, para los problemas
de menor compresión lo comentado no cambia, puesto que la diferencia entre las
heurísticas sigue en valor cero.
Por tanto vamos a pasar a hacer unos comentarios generales sobre este bloque que
nos permitan sacar unas conclusiones para el apartado final que tiene este nombre.
Por todo esto me atrevo a sacar una serie de conclusiones para problemas Pm||ΣUi,
en la comparación del algoritmo Greedy con el Conway, que son las siguientes:
• En líneas generales, la heurística Greedy se suele comportar mejor que la
Conway para este tipo de problemas, especialmente para trabajos sin
compresión especial, C2, donde se produce un punto de máxima variación (
).
• Para trabajos de baja compresión, C3, ambas heurísticas suelen comportase
igual, salvo para poco número de máquinas en el que el algoritmo Greedy
comporta una ligera mejoría.
Tras estos puntos anteriores que coinciden en lo básico con el caso de Lmax, podemos
decir también.
Proyecto fin de Carrera 2014
53
• Para trabajos de alta compresión pasa justamente lo contrario que para los de
baja. Parece que independientemente del número de máquinas presenta una
línea descendiente con respecto al número de trabajos, siendo mayor la
diferencia para pocos trabajos (menor compresión y por lo tanto más cerca de
la compresión media) que para muchos, donde prácticamente es nula.
• Existe mucha menos variabilidad en este caso que con Lmax, aunque los valores
de las diferencias suelen ser de media porcentual más altos que con aquel.
• Existe repetición tanto con Ui como con Lmax en valores de pico para baja
compresión como con 100 trabajos y 4 máquinas y 200 trabajos y 8 máquinas,
pero no parece asignable a nada concreto.
Con esto podemos sacar la siguiente conclusión final:
Por tanto, como conclusión general, para Pm||ΣUi, Greedy funciona mejor que
Conway para valores de las variables cercanos al punto medio de compresión, y
mejor cuanto más se acerque al entorno de la relación . En
él, el valor máximo de la diferencia ronda el 19%, aunque no está claramente
definido por su baja variabilidad. A medida que nos alejamos de este entorno la
diferencia entre ambas disminuye, siendo menos relevante la heurística
utilizada.
Proyecto fin de Carrera 2014
54
CAPÍTULO 5
MODELO Qm| |Lmax
Proyecto fin de Carrera 2014
55
5. MODELO Qm| |Lmax
5.1 INTRODUCCIÓN
En este capítulo entramos en el ámbito de las máquinas uniformes, es decir, aquellas
cuyas velocidades de procesamiento son diferentes para cada máquina, por lo que los
trabajos tienen una duración diferente dependiendo a cuál de ellas se asigne. Al igual
que para Pm, se trata de resolver un modelo en el que se busca minimizar el valor de
Lmax, o lo que es lo mismo, el retraso máximo existente entre todos los trabajos.
Buscaremos implementar diferentes heurísticas sobre este problema con el objetivo
de ver cual se comporta mejor en función de unos determinados valores o variables
que serán de nuestro interés. Estas heurísticas serán muy similares al caso de Pm, por
lo que no necesitarán tan extensa explicación. Por ello, a través de la batería de
problemas previamente creados estudiaremos los resultados para observar cual nos
proporciona un mejor comportamiento. Se resolverán con el programa Visual Basic y
básicamente compararemos el algoritmo Conway con el algoritmo Greedy.
Proyecto fin de Carrera 2014
56
5.2 HEURÍSTICA EDD&GREEDY
La heurística que presenta mejores resultados es la de ordenar los trabajos por la regla
EDD (Earliest due date), que consiste en poner los trabajos en un orden no decreciente
de , es decir, de sus fechas de entrega, como ya hemos realizado en tantas ocasiones
anteriormente.
Posteriormente estos trabajos deben asignarse a las máquinas según la lógica del
algoritmo de asignación Greedy, es decir, a la máquina que esté libre en el instante
mayor, siguiendo la lógica de que de esta forma se dejará hueco posteriormente para
trabajos en máquinas menos cargada.
A diferencia de lo que ocurría con Pm, la máquina que esté libre en el instante mayor
se elegirá conforme al momento de finalización del trabajo, y no al del comienzo. Esto
se hace así debido a que las diferentes máquinas tienen velocidades distintas, y por
tantos los trabajos asignados a estas deben tener tiempos de procesamiento distinto.
Para evitar esta disparidad calculamos en qué momento terminaría el trabajo si fuese
asignado a esa máquina, y de esa forma asignamos este en aquella cuyo momento sea
mayor.
Se debe empezar probando en máquinas de mayor momento de finalización, pero si se
superase la fecha de entrega en un valor mayor que el valor vigente de Lmax se debe ir
intentando en las sucesivamente de mayor finalización hasta que se asigne o se agoten
las máquinas.
En este caso extremo se debe asignar el trabajo a la máquina con momento de
finalización más corto, es decir, por Conway, no olvidándonos de actualizar el valor de
Lmax. El algoritmo terminará cuando todos los trabajos hayan sido asignados.
Esta misma lógica que ha sido expresada con palabras ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo VIII.
Pasaremos ahora a resolver los tres problemas que hemos resuelto para los casos
oportunos en los anteriores dos apartados de este proyecto. Como suele ser habitual
cada uno tiene un número de máquinas diferentes. El segundo y el tercero tendrán
cuatro y cinco máquinas respectivamente.
Pero empezaremos con este primero. Destacar de él que a diferencia de los que
pasaba con Pm, se han utilizado números no enteros, es decir, con decimales, debido a
que la velocidad de las máquinas varía entre 1 y 1.5. Esto hace que al multiplicarlo por
la duración de trabajo salgan números decimales. Empezaremos con el de tres
máquinas, y cuyo resultado manual será el siguiente:
Proyecto fin de Carrera 2014
57
Nºs de los trabajos Tiempo
M1 2 15 11 3 10 4 9 5 14 5 7 11 19 21 25 41 44 57
M2 7 16 1 6 10,8 15,6 31,2 45,6
M3 17 8 13 12 10,5 16,5 33,0 45,0
Lmax 2,0 2,8 3 11,2 12 15,6 23
Vemos que como habíamos dicho, uno de los tiempos de finalización, el de la máquina
2, es no entero. Aparte, muchos de los tiempos intermedios, así como de los Lmax
intermedios también tienen decimales.
Ahora vamos a comprobar si el algoritmo propuesto, como hacíamos en los capítulos
anteriores, es o no correcto. Para ello vemos que la salida del código de comprobación
es la siguiente:
Lmax sinConway:
Maq. 3:
Trab. 17 Dur. 7; Trab. 8 Dur. 4; Trab. 13 Dur. 11; Trab. 12 Dur. 8;
Dur. Total: 45
Maq. 2:
Trab. 7 Dur. 9; Trab. 16 Dur. 4; Trab. 1 Dur. 13; Trab. 6 Dur. 12;
Dur. Total: 45,6
Maq. 1:
Trab. 2 Dur. 5; Trab. 15 Dur. 2; Trab. 11 Dur. 4; Trab. 3 Dur. 8; Trab. 10 Dur. 2; Trab. 4 Dur. 4; Trab. 9 Dur. 16; Trab. 5 Dur. 3; Trab. 14 Dur. 13;
Dur. Total: 57
Lmax sinConway: 23
Proyecto fin de Carrera 2014
58
Vemos que aunque no están las maquinas ordenadas en esta salida, los datos son
correctos, por lo que tenemos esta garantía de exactitud del código.
Vamos a pasar a comprobar el segundo de los problemas que tenemos por costumbre
analizar. En este caso vemos el de cuatro máquinas, cuya resolución manual viene
dada por las asignaciones siguientes:
Nºs de los trabajos Tiempo
M1 4 8 3 5 15 17 18 36
M2 0,0
M3 2 1 9 11,2 18,2 28,0
M4 7 6 9,0 22,5
Lmax 9,0
Vemos que en este caso también aparecen algunos números no enteros como era de
esperar. Sin más pasamos a ver la salida del código del mismo:
Lmax sinConway:
Maq. 3:
Trab. 2 Dur. 8; Trab. 1 Dur. 5; Trab. 9 Dur. 7;
Dur. Total: 28
Maq. 4:
Trab. 7 Dur. 6; Trab. 6 Dur. 9;
Dur. Total: 22,5
Maq. 1:
Trab. 4 Dur. 15; Trab. 8 Dur. 2; Trab. 3 Dur. 1; Trab. 5 Dur. 18;
Dur. Total: 36
Proyecto fin de Carrera 2014
59
Maq. 2:
Dur. Total: 0
Lmax sinConway: 9
De nuevo vemos que aunque las máquinas están desordenadas como en el caso
anterior, el resultado es exactamente el mismo que hemos obtenido por el método
manual, por lo que el código vuelve a ser el correcto.
Vamos una vez analizado esto, con el tercer y último problema, esta vez para el de 5
máquinas, que nos da el resultado manual que se muestra a continuación y que
compararemos luego:
Nºs de los trabajos Tiempo
M1 17 11 3 10 18 5 16 24 28 36
M2 20 16 5 19 12 6,0 10,8 21,6 30,0 40,8
M3 15 7 9 13 6,5 9,1 20,8 31,2
M4 2 4 8 14 5,6 12,6 30,8 40,6
M5 1 6 21 1,5 9 30
Lmax 0,3 1,0 3,8 8,0 9,8
De nuevo vemos que existen números decimales en esta solución Pasamos a ver la
salida del código para este problema, que será la siguiente:
Lmax sinConway:
Maq. 2:
Trab. 20 Dur. 5; Trab. 16 Dur. 4; Trab. 5 Dur. 9; Trab. 19 Dur. 7; Trab. 12 Dur. 9;
Dur. Total: 40,8
Maq. 1:
Proyecto fin de Carrera 2014
60
Trab. 17 Dur. 5; Trab. 11 Dur. 11; Trab. 3 Dur. 8; Trab. 10 Dur. 4; Trab. 18 Dur. 8;
Dur. Total: 36
Maq. 4:
Trab. 2 Dur. 4; Trab. 4 Dur. 5; Trab. 8 Dur. 13; Trab. 14 Dur. 7;
Dur. Total: 40,6
Maq. 5:
Trab. 1 Dur. 1; Trab. 6 Dur. 5; Trab. 21 Dur. 14;
Dur. Total: 30
Maq. 3:
Trab. 15 Dur. 5; Trab. 7 Dur. 2; Trab. 9 Dur. 9; Trab. 13 Dur. 8;
Dur. Total: 31,2
Lmax sinConway: 9,8
Vemos que el resultado del mismo es idéntico al ya obtenido de forma manual, por lo
que podemos decir que el código es correcto, una vez efectuadas las tres
comprobaciones para los problemas que venimos efectuando en este estudio.
No lo hemos comentado con anterioridad pero a la salida del código se dan para cada
trabajo dos datos. Uno es el número del trabajo, que es el que podemos comparar con
el problema manual, y el otro es la duración del mismo, que está relacionada con la
ocupación de la máquina que lo procesa, detallada también en el problema manual. Si
para estos problemas Qm queremos comprobarlo de forma exacta debemos
multiplicarlo por la velocidad de cada máquina. Para cada una de las máquinas se ha
asignado una velocidad diferente.
Pasaremos una vez comentado esto a detallar la siguiente heurística.
Proyecto fin de Carrera 2014
61
5.3 HEURÍSTICA EDD&CONWAY
Como viene siendo habitual compararemos esta heurística con la anterior, que
aunque tienen varios puntos de coincidencia, como veremos en los resultados finales,
da un resultado diferente.
Al igual que para la heurística Conway lo que debemos hacer en primer lugar es
ordenar los trabajos por la regla EDD, es decir, en orden no decreciente de , es decir,
de sus fechas de entrega.
Una vez hecho esto, como hemos realizado en cada uno de los ejemplos vistos
anteriormente, asignaremos cada trabajo en dicho orden mediante el algoritmo
Conway, es decir, a la máquina que este libre en el instante menor, una vez sumado el
tiempo de ejecución del trabajo que pensamos asignar, con la velocidad de ejecución
incluida, como hicimos en el anterior apartado.
Dado que siempre que se asigne a la máquina menos ocupada se tratará del caso más
extremo no debemos intentar la asignación con el resto de máquinas, puesto que si
para esta no es posible que el tiempo de ejecución menos la fecha de entrega superen
al Lmax vigente, para las otras máquinas tampoco sucederá.
Si como hemos dicho, se excede del valor de Lmax, debemos pasar de nuevo a asignar
a la máquina menos cargada, al igual que hacíamos en el anterior algoritmo, sin por
supuesto olvidarnos de actualizar el valor de Lmax, que es el que estamos buscando y
el que queremos minimizar.
Esta misma lógica que ha sido expresada con palabras, ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo IX.
Visto esto veremos, como hicimos en el apartado anterior, tres ejemplos de ello, que
nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Como ya dijimos anteriormente, los ejemplos realizados son los mismos para todos los
tipos de problemas, por lo que para no repetir aspectos comunes, como pudiera ser
los datos de los trabajos así como su orden con respecto al algoritmo EDD, se han
presentado estos en el Anexo III para que sean de fácil disposición al lector.
Una vez aclarados estos aspectos pasaremos a resolver, tal y como hicimos en el
apartado anterior, los problemas a mano con el objetivo de comprobar la validez del
código.
Empezaremos por el de 3 máquinas, pero no presentaremos los datos, ya que, como
hemos dicho, están expuestos en el Anexo III.
Proyecto fin de Carrera 2014
62
Por tanto, conforme a esta asignación, los trabajos en las máquinas quedarían de la
siguiente forma:
Nºs de los trabajos Tiempo
M1 2 17 3 13 9 5 12 20 31 47
M2 15 7 1 6 14 2,4 13,2 28,8 43,2 58,8
M3 11 8 16 10 4 12 5 6,0 12,0 18,0 21,0 27,0 39,0 43,5
Lmax 2,0 5,2 8,8 9,0 18,0 24,8
Observamos que en este primer problema, el resultado de esta heurística nos da un
retraso ligeramente superior al que nos daba la primera heurística, por lo que parece
que la tendencia que estamos viendo en el estudio sigue igual.
Ahora veremos cuál es el resultado que nos da el código propuesto en el Anexo IX, con
el objetivo de comprobar su veracidad. Este será el resultado del mismo:
Lmax Conway:
Maq. 2:
Trab. 15 Dur. 2; Trab. 7 Dur. 9; Trab. 1 Dur. 13; Trab. 6 Dur. 12; Trab. 14 Dur. 13;
Dur. Total: 58,8
Maq. 1:
Trab. 2 Dur. 5; Trab. 17 Dur. 7; Trab. 3 Dur. 8; Trab. 13 Dur. 11; Trab. 9 Dur. 16;
Dur. Total: 47
Maq. 3:
Trab. 11 Dur. 4; Trab. 8 Dur. 4; Trab. 16 Dur. 4; Trab. 10 Dur. 2; Trab. 4 Dur. 4; Trab. 12 Dur. 8; Trab. 5 Dur. 3;
Proyecto fin de Carrera 2014
63
Dur. Total: 43,5
Lmax Conway: 24,8
Vemos que los resultados de ambos son exactamente los mismos, por lo que el primer
paso hacia la comprobación que estamos efectuados ha sido dado con éxito.
Ahora pasaremos al problema de 4 máquinas, en el que la asignación manual que
hemos realizado es la siguiente, incluyendo los valores en cada iteración:
Nºs de los trabajos Tiempo
M1 4 5 15 33
M2 7 6 7,2 18,0
M3 2 9 11,2 21,0
M4 8 3 1 3,0 4,5 12,0
Lmax 9,0
En este caso no existe diferencia con la primera heurística. Ahora, como siempre,
vemos el resultado que nos proporciona el programa Visual Basic y lo comparamos con
el mismo:
Lmax Conway:
Maq. 1:
Trab. 4 Dur. 15; Trab. 5 Dur. 18;
Dur. Total: 33
Maq. 4:
Trab. 8 Dur. 2; Trab. 3 Dur. 1; Trab. 1 Dur. 5;
Dur. Total: 12
Proyecto fin de Carrera 2014
64
Maq. 2:
Trab. 7 Dur. 6; Trab. 6 Dur. 9;
Dur. Total: 18
Maq. 3:
Trab. 2 Dur. 8; Trab. 9 Dur. 7;
Dur. Total: 21
Lmax Conway: 9
De nuevo el resultado es idéntico, por lo que la comprobación es perfecta y podemos
pasar al tercer y último ejemplo de este bloque de Qm||Lmax, antes de ejecutar los
1140 ejemplos pertenecientes a este capítulo.
Así, pasamos a ver cuál es el resultado de nuestra resolución manual para el tercer
problema de 5 máquinas:
Nºs de los trabajos Tiempo
M1 1 15 17 9 10 8 1 6 11 20 24 37
M2 2 16 5 19 12 4,8 9,6 20,4 28,8 39,6
M3 6 11 18 6,5 20,8 31,2
M4 7 4 21 14 2,8 9,8 29,4 39,2
M5 20 3 13 7,5 19,5 31,5
Lmax 11,0
Vemos que para este problema el retraso también ha aumentado con respecto a la
primera heurística. De nuevo se confirma la tendencia que estamos estudiando.
Y el resultado proporcionado por el código del programa que estamos utilizando sería
el que se muestra a continuación:
Lmax Conway:
Proyecto fin de Carrera 2014
65
Maq. 4:
Trab. 7 Dur. 2; Trab. 4 Dur. 5; Trab. 21 Dur. 14; Trab. 14 Dur. 7;
Dur. Total: 39,2
Maq. 3:
Trab. 6 Dur. 5; Trab. 11 Dur. 11; Trab. 18 Dur. 8;
Dur. Total: 31,2
Maq. 5:
Trab. 20 Dur. 5; Trab. 3 Dur. 8; Trab. 13 Dur. 8;
Dur. Total: 31,5
Maq. 1:
Trab. 1 Dur. 1; Trab. 15 Dur. 5; Trab. 17 Dur. 5; Trab. 9 Dur. 9; Trab. 10 Dur. 4; Trab. 8 Dur. 13;
Dur. Total: 37
Maq. 2:
Trab. 2 Dur. 4; Trab. 16 Dur. 4; Trab. 5 Dur. 9; Trab. 19 Dur. 7; Trab. 12 Dur. 9;
Dur. Total: 39,6
Lmax Conway: 11
Que como se comprueba, de nuevo es idéntico, por lo que podemos asegurar que los
códigos de ambas heurísticas son correctos. Pasamos resolver la colección de
problemas generados y a compararlas en el siguiente apartado.
Proyecto fin de Carrera 2014
66
5.4 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS
Una vez obtenidos los datos de las comprobaciones, vamos a analizarlos para ver cuál
es la tendencia en la comparación de ambas heurísticas.
Vemos que para el caso de tres máquinas aumenta Lmax en 1,8 unidades de 23 a 24,8,
comportándose mejor el algoritmo Greedy. Por otro lado, para el ejemplo de 4
máquinas no existe variación, pues para ambas heurísticas se produce un retraso
máximo de 9. Por último, para el ejemplo con 5 máquinas de nuevo se comporta mejor
el algoritmo Greedy, con Lmax de 9,8, mientras que Conway presenta 11.
Este interesante razonamiento para los ejemplos nos permite observar, como
habíamos previsto, que el algoritmo Greedy se comporta mejor, pero debemos hacer
un estudio más detallado del mismo, por lo que resolveremos la batería de 1140
problemas que teníamos prevista para este apartado.
Puesto que el número de problemas a resolver es tan extenso, vamos a clasificarlos
por el tipo de variables, por lo que para cada conjunto de variables resolveremos un
total de 10 problemas. Nos queda que resolveremos 57 tipos de problemas con
variables distintas, comparándolas entre ellas.
Por si resulta de interés del lector, hemos añadido en el Anexo X los valores de Lmax
que han salido de media para cada tipo de problema, tanto para la heurística Greedy
como para la Conway, así como la diferencia a nivel porcentual de ambos, con el
objetivo de hacer un estudio de las mismas.
Debido a la gran cantidad de datos de salida que tenemos tras implementar esta
cantidad de problemas en nuestro algoritmo, y que han sido mostrados en forma de
media en el Anexo X, nos vemos obligados a utilizar unas gráficas con nos permitan ver
de forma más clara cuál ha sido el comportamiento de las heurísticas en función de las
variables.
Debido a que tenemos 3 variables, y solo podemos hacer gráficas bidimensionales,
puesto que el papel no nos permite otra cosa de forma clara, mostraremos 4 gráficas,
una para cada número de máquinas utilizadas, que nos permita ver el comportamiento
de estas con respecto a la variación en el número de trabajos y la carga, es decir, lo
muy o poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1
sería muy comprimido y C3 poco comprimido.
La primera gráfica sería para problemas con 4 máquinas, significando porcentajes
positivos que el algoritmo Greedy se comporte mejor que el Conway, y negativos en
caso contrario, como se ve a continuación:
Proyecto fin de Carrera 2014
67
Vemos que para problemas del tipo C1 y C2, es decir, los más comprimidos, la
diferencia prácticamente es nula entre las dos heurísticas. Cuando estamos con un
número de trabajos inferior todavía existe alguna variabilidad, que se hace nula
cuando aumenta este número de trabajos.
En contraposición con esto vemos que los problemas que originariamente tenían muy
baja compresión, C3, ahora se comportan con unos niveles de diferencia entre
heurísticas mucho mayores, propios de los que tenían para Pm algunos como los de
compresión intermedia, C2.
Siguiendo el razonamiento obtenido en los casos de Pm, y teniendo en cuenta que Qm
no ha hecho más que comprimir los problemas estudiados, puesto que las máquinas
en media tienen una velocidad de procesamiento inferior, obtenemos una lógica para
estos resultados.
Dado que la generación de problemas está creada en torno a un valor de compresión
medio como para máquinas con velocidad 1, al disminuir la velocidad de las máquinas
se ha incrementado la compresión de todos los problemas, teniendo ahora una
compresión que podríamos llamar media aquellos que antes la tenían como baja. Esto
se ha notado especialmente para el caso estudiado de 4 máquinas, donde aumenta
aún más la compresión, pero vamos a ver cómo se comporta para el resto.
Veremos ahora para 8 máquinas:
Proyecto fin de Carrera 2014
68
En este caso se ha producido una disminución de la compresión, por haber aumentado
el número de máquinas. Por lo tanto vemos como los problemas C2 están subiendo
algo su porcentaje mientras que aquellos con baja compresión, C3, la disminuyen con
respecto al caso de 4 máquinas.
Es significativo el hecho de que para bajo número de trabajos todos los problemas
suben su diferencia. Esto es debido a que al haber pocos trabajos la compresión
disminuye, y por lo tanto se contrapone al aumento de la misma causada por la
disminución de la velocidad. Esto nos demuestra que nuestra línea de que mayor
diferencia entre heurísticas existe cuanto mayor es el acercamiento al punto de
compresión media es correcta.
Veremos ahora el caso de los problemas de 16 máquinas:
Proyecto fin de Carrera 2014
69
Se repite de nuevo la tendencia comentada anteriormente. En este caso vemos como
la tendencia de los problemas C3 es ir bajando a medida que aumenta el número de
máquinas y por lo tanto disminuye la compresión. Por el contrario, como ya venimos
diciendo, la diferencia de los trabajos C2 tiende a subir, mientras que vemos como los
C1 ya presentan una apreciable mejoría debido al contrarresto de su alta compresión
inicial.
Por último, para problemas de gran número de máquinas, 32 en este caso:
Observamos como los problemas de compresión media, ahora ya que se ha producido
el contrarresto a la disminución de la velocidad de las máquinas, se imponen a los
otros dos tipos de problemas. Este es el escenario ya más parecido al típico que se nos
presentaba para Pm debido a las razones que acabamos de comentar.
Destacar también como para bajos valores del número de trabajos la compresión de
hace mucho más baja y a consecuencia de esto permite dispararse a la diferencia entre
heurísticas para los problemas de alta compresión, C1, algo que no había ocurrido
anteriormente. Igualmente vemos que a los problemas de media compresión también
le sucede algo parecido, presentando una línea descendiente con respecto al número
de trabajos y máximo total de casi el 20% de diferencia para el número de trabajos
mínimo de 100.
Proyecto fin de Carrera 2014
70
Con todo esto me atrevo a sacar una serie de conclusiones para problemas
Qm||Lmax, en la comparación del algoritmo Greedy con el Conway, que son las
siguientes:
• En líneas generales, la heurística Greedy se suele comportar mejor que la
Conway para este tipo de problemas.
• La diferencia entre ambas heurísticas se hace mayor cuanto más se acerca al
entorno de compresión medio definido para problemas Pm.
• En este sentido para pocas máquinas los que mayor diferencia presentan son
los problemas C3, pero a medida que van disminuyendo los trabajos y
aumentado las máquinas los problemas C2 van aumentando su diferencia
ampliamente mientras que los de alta compresión, C1, la van aumentando
levemente.
• Por tanto, la mayor diferencia se da para el punto extremo en este sentido, y no
para el punto medio como pasaba con Pm. Este punto extremo es el de mayor
número de máquinas (32) y menor de trabajos (100), que presenta una
diferencia porcentual del 18,7%.
Por tanto, como conclusión general, para Qm||Lmax, Greedy funciona mejor
que Conway, y debido a la compresión artificial creada por la disminución de
velocidades de las máquinas, la diferencia es mayor cuanto más se acerque al
punto compresión intermedia. Este se produce para los valores límites de mayor
número de máquinas (32 mqs.) y menor de trabajos estudiados (100 tbs.). Para
este punto la diferencia es del 18,7 %. Cuanto más se aleje de él en el entorno
estudiado, más disminuirá esta diferencia.
Proyecto fin de Carrera 2014
71
CAPÍTULO 6
MODELO Qm| |ΣUi
Proyecto fin de Carrera 2014
72
6. MODELO Qm| |ΣUi
6.1 INTRODUCCIÓN
En este tipo de problemas lo que se busca es minimizar el número de retrasos, en vez
de minimizar el retraso máximo, como se pretendía en el bloque anterior. De nuevo se
trata de problemas Qm, uniformes, es decir, aquellos cuyas velocidades de
procesamiento son diferentes para cada máquina, por lo que los trabajos tienen una
duración diferente dependiendo a cuál de ellas se asigne.
Buscaremos implementar diferentes heurísticas sobre este problema con el objetivo
de ver cual se comporta mejor en función de unos determinados valores o variables
que serán de nuestro interés. Por ello, a través de una batería de problemas
previamente creados estudiaremos los resultados para observar cual nos proporciona
un mejor comportamiento. Se resolverán con el programa Visual Basic y básicamente,
al igual que hicimos para el caso de Lmax, compararemos el algoritmo Conway con el
algoritmo Greedy que explicaremos a continuación.
Proyecto fin de Carrera 2014
73
6.2 HEURÍSTICA EDD&GREEDY
La heurística que en principio presenta mejores resultados es la de ordenar los
trabajos por la regla EDD (Earliest due date), que consiste en poner los trabajos en un
orden no decreciente de , es decir, de sus fechas de entrega, como hemos hecho
también para todos los problemas del caso de Lmax.
Posteriormente estos trabajos deben asignarse a las máquinas según la lógica del
algoritmo de asignación Greedy, es decir, a la máquina que esté libre en el instante
mayor contando con el tiempo de procesamiento del trabajo que estamos asignando,
multiplicado por la velocidad de esa máquina, siguiendo la lógica de que de esta forma
se dejará hueco posteriormente para trabajos en máquinas menos cargada.
Se debe empezar probando en máquinas más cargadas, pero si el tiempo de
finalización fuese superior a la fecha de entrega de este trabajo se debe ir intentando
en las sucesivamente más cargadas hasta que se asigne o se agoten las máquinas.
En este caso extremo de que se agoten las máquinas se debe buscar el trabajo de
mayor duración de los ya asignados. Si este trabajo fuese el mismo que estamos
intentando asignar en esta iteración simplemente de descartaría. Si existiese un
trabajo con mayor duración ya asignado deberíamos descartar este y colocar el trabajo
de esta iteración en la máquina en la que se encontraba el anterior. De esta forma
conseguimos que se descarte un trabajo, cuando igualmente era necesario descartar
uno, pero dejando mayor espacio para otros que pudieran venir en el futuro, y por
tanto, reduciendo la probabilidad de retraso de los mismos. No debemos olvidarnos de
aumentar en una unidad el valor del número de retrasos, Ui. El algoritmo terminará
cuando todos los trabajos hayan sido asignados.
Esta misma lógica, que ha sido expresada con palabras, ha sido programada en
lenguaje C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo
XI.
Visto esto veremos, como hemos hecho en los anteriores capítulos, tres ejemplos de
ello, que nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Puesto que son los mismos para todos los problemas realizados en este trabajo, no
pasaremos a describirlos en profundidad como hicimos anteriormente. Tan solo decir
que son 3 ejemplos, de tres, cuatro y cinco máquinas, y cuyos datos de trabajos están
en el Anexo III como ya hemos comentado.
De esta forma, para el primero de los tres ejemplos, compuesto por 3 máquinas como
ya hemos dicho, la resolución manual será la que se muestra a continuación:
Proyecto fin de Carrera 2014
74
Nºs de los trabajos Tiempo
M1 3 13 12 5 8 19 27 30
M2 17 16 6 8,4 13,2 27,6
M3 15 11 8 10 4 3 9 15 18 24
Ui 2 7 1 9 14
Se puede observar que para este tipo de problemas no hay trabajos que hayan sido
tachados y descartados después de haber sido asignados, tal y como pasaba con Pm
para este mismo problema. Asimismo comentar que al lado de Ui no se ha puesto el
retraso de los trabajos, como hacíamos con Lmax, ni siquiera el número de trabajos
retrasados. Hemos puesto el número de los trabajos que han sido retrasados, por ser
mucho más visual y porque es el dato que nos muestra el código. De esta forma, para
este problema el número de trabajos retrasados serían cinco, mientras que los
trabajos retrasados serían el número 2, el número 7, el 1, el número 9 y el 14, uno más
que para Lmax.
También debemos observar que para este problema, al tratarse de Qm y haber
velocidades distintas en las máquinas, y ser estos números no enteros, algunos de los
valores de finalización de las máquinas también han salido no enteros, como le pasa
por ejemplo a la máquina 2.
Una vez aclarado, podemos ver cuál es la salida que nos proporciona el programa, de
cara a ver su funcionalidad:
SumUisC:
Trabajos no asignados:
Trab. 2, Trab. 7, Trab. 1, Trab. 9, Trab. 14,
Maq. 3: Dur. Total: 24
Maq. 2: Dur. Total: 27,6
Proyecto fin de Carrera 2014
75
Maq. 1: Dur. Total: 30
SumUisC: 5
Como podemos ver, hemos añadido una salida más extensa que para el caso de Pm,
para comprobar mejor la viabilidad del código. De esta forma hemos añadido la
duración final del procesamiento de las máquinas, viendo que todos los datos son
correctos y coinciden con los calculados manualmente. Por ello podemos dar como
bueno el código en esta primera prueba y pasar a analizar el segundo problema.
Para este segundo problema, de 4 máquinas, como ya hemos visto en los casos
anteriores, la resolución manual nos proporciona los siguientes datos:
Nºs de los trabajos Tiempo
M1 2 8 3 5 8 10 11 29
M2 7 7,2
M3 6 12,6
M4 1 9 7,5 18
Ui 4
En este problema, no ha habido ningún trabajo que haya tenido que ser descartado ya
habiendo sido asignado, por eso no hay ninguno tachado. Sin embargo sí que uno ha
sido descartado, pero habiendo sido el de mayor duración de los asignados hasta el
momento.
Vamos a ver si estos cálculos coinciden con la salida del código programado para este
tipo de problemas:
SumUisC:
Trabajos no asignados:
Trab. 4,
Proyecto fin de Carrera 2014
76
Maq. 4: Dur. Total: 18
Maq. 3: Dur. Total: 12,6
Maq. 1: Dur. Total: 29
Maq. 2: Dur. Total: 7,2
SumUisC: 1
Efectivamente coincide, siendo el trabajo descartado el mismo que habíamos
considerado nosotros, por lo que el código sigue según lo previsto con su viabilidad.
Aunque el orden de las máquinas no es el mismo que en la resolución manual, el valor
de finalización sí que es el mismo y por tanto podemos considerar que los datos son
válidos.
Una vez pasado el trámite de los dos problemas solo nos queda comprobar el tercero
de ellos, el que está compuesto por 5 máquinas, de modo que la resolución manual
sería la siguiente:
Nºs de los trabajos Tiempo
M1 17 5 19 13 5 14 21 29
M2 20 16 18 6 10,8 20,4
M3 15 7 8 6,5 9,1 26
M4 2 4 10 12 5,6 12,6 18,2 30,8
M5 1 6 3 14 1,5 9 21 31,5
Ui 11 9 21
Proyecto fin de Carrera 2014
77
Al igual que pasaba en el caso anterior, no ha habido ningún trabajo que haya tenido
que ser descartado ya habiendo sido asignado, por lo que no hay ninguno tachado. Sin
embargo sí que tres han sido descartados, los trabajos 11, 9 y 21, pero habiendo sido
los de mayor duración de los asignados hasta el momento.
Visto esto veremos cuál es la solución dada por el programa, para terminar de ver si
funciona correctamente:
SumUisC:
Trabajos no asignados:
Trab. 11, Trab. 9, Trab. 21,
Maq. 4: Dur. Total: 30,8
Maq. 1: Dur. Total: 29
Maq. 3: Dur. Total: 26
Maq. 5: Dur. Total: 31,5
Maq. 2: Dur. Total: 20,4
SumUisC: 3
Vemos que efectivamente coincide aunque las máquinas no estén ordenadas, por lo
que podemos estar seguros de que el programa está funcionando correctamente, y
por tanto, podemos utilizarlo para resolver la colección de 570 problemas que
tenemos prevista para este tipo de ejercicio.
Una vez comprobado esto podemos pasar a analizar el siguiente tipo de problemas, el
cual vamos a comparar con el ya analizado.
Proyecto fin de Carrera 2014
78
6.3 HEURÍSTICA EDD&CONWAY
Esta va a ser la heurística con la que comparemos la anterior, que aunque tienen varios
puntos de coincidencia, como veremos en los resultados finales, da un resultado
diferente.
Al igual que para la heurística Conway lo que debemos de hacer en primer lugar es
ordenar los trabajos por la regla EDD, es decir, en orden no decreciente de , es decir,
de sus fechas de entrega.
Una vez hecho esto, como hemos realizado en cada uno de los ejemplos vistos
anteriormente, asignaremos cada trabajo en dicho orden mediante el algoritmo
Conway, es decir, a la máquina que este libre en el instante menor, una vez sumado el
tiempo de ejecución del trabajo que pensamos asignar, con la velocidad de ejecución
incluida, como hicimos en el anterior apartado.
Dado que siempre que se asigne a la máquina menos ocupada se tratará del caso más
extremo no debemos intentar la asignación con el resto de máquinas, puesto que si
para esta no es posible que el tiempo de ejecución no supere a la fecha de entrega
vigente, para las otras máquinas tampoco sucederá.
Si como hemos dicho, se excede del valor de de la fecha de entrega, debemos
descartar uno de los trabajos, por lo que, al igual que antes, debemos ver cuál de los
trabajos que ya han sido asignados, o el que estamos asignando, es el de mayor
duración. Este es el trabajo que debemos descartar, y si se trata de uno ya asignado,
sustituir el de esta iteración por el ya asignado.
No debemos olvidarnos de multiplicar la duración del trabajo por la velocidad de la
máquina, tanto si es de nueva asignación como si es sustituido por otro trabajo que
vayamos a descartar.
Esta misma lógica que ha sido expresada con palabras, ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo XII.
Visto esto veremos, como hemos hecho en el resto de apartados, tres ejemplos de
ello, que nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Para no repetir de nuevo lo ya expuesto, decimos que los datos de estos ejercicios que
se van a realizar a continuación están expuestos en el Anexo III, por si se quieren
consultar, tanto en el orden dado al programa como ordenados según la regla EDD.
Una vez aclarados estos aspectos pasaremos a resolver, tal y como hicimos en el
apartado anterior, los problemas a mano con el objetivo de comprobar la validez del
código.
Proyecto fin de Carrera 2014
79
Empezaremos por el de 3 máquinas. Por tanto, conforme a esta asignación, los
trabajos en las máquinas quedarían de la siguiente forma:
Nºs de los trabajos Tiempo
M1 15 17 10 13 5 2 9 11 22 25
M2 11 3 6 4,8 14,4 28,8
M3 8 16 4 12 6 12 18 30
Ui 2 7 1 9 14
Vemos que para este problema ha habido 5 trabajos descartados, igual que asaba para
la heurística Greedy, por lo que de momento no se aprecia mejoría para esta
heurística. Los trabajos descartados han sido el 2, el 7, el 1, el 9 y el 14.
Tras esta reflexión veamos la solución que nos aporta el programa Visual Basic:
SumUiC:
Trabajos no asignados:
Trab. 2, Trab. 7, Trab. 1, Trab. 9, Trab. 14,
Maq. 1: Dur. Total: 25
Maq. 2: Dur. Total: 28,8
Maq. 3: Dur. Total: 30
SumUisC: 5
Proyecto fin de Carrera 2014
80
De nuevo coincide plenamente con lo que habíamos calculado, y también con la
solución que se nos daba para el apartado anterior, por lo que de momento parece no
afectar el cambio de heurística. El código vemos que es correcto.
Por tanto pasaremos ahora al ejemplo siguiente, el de 4 máquinas, cuyo resultado
manual es el que vemos:
Nºs de los trabajos Tiempo
M1 7 5 6 24
M2 2 9,6
M3 8 9 2,8 12,6
M4 3 1 1,5 9
Ui 4 6
En esta ocasión vemos que no ha habido trabajos rechazados después de asignados, y
tan solo dos rechazados, que son el 4 y el 6.
No tenemos mucho más que comentar, salvo ver el resultado de la salida del
programa:
SumUiC:
Trabajos no asignados:
Trab. 4, Trab. 6,
Maq. 1: Dur. Total: 24
Maq. 2: Dur. Total: 9,6
Proyecto fin de Carrera 2014
81
Maq. 4: Dur. Total: 9
Maq. 3: Dur. Total: 12,6
SumUisC: 2
Como vemos es correcto y vemos que no coincide con la del apartado anterior puesto
que se ha descartado un trabajo más, el 6. Por tanto, como venimos viendo en todo el
estudio, aquí tenemos el primer indicio de que de nuevo Greedy se comporta mejor
que Conway.
Vamos a pasar ahora al último ejemplo para comprobar la corrección de este cuarto
código que estamos utilizando. Para este último ejemplo, como venimos haciendo,
hemos utilizado el caso de las 5 máquinas, con lo que el resultado manual sería el
siguiente:
Nºs de los trabajos Tiempo
M1 1 15 17 8 1,0 6,0 11,0 24,0
M2 2 16 19 14 4,8 9,6 18,0 26,4
M3 6 3 12 6,5 16,9 28,6
M4 7 4 18 2,8 9,8 21,0
M5 20 10 13 7,5 13,5 25,5
Ui 11 9 5 21
Cabe destacar que en este caso ha habido un trabajo descartado más que en el caso de
la heurística Greedy, que es el trabajo 5. Esto nos demuestra de nuevo como esta
segunda heurística se comporta peor, como ya venimos observando.
Vamos a ver cuál será para este el resultado de la salida del programa:
Proyecto fin de Carrera 2014
82
SumUiC:
Trabajos no asignados:
Trab. 11, Trab. 9, Trab. 5, Trab. 21,
Maq. 2: Dur. Total: 26,4
Maq. 4: Dur. Total: 21
Maq. 1: Dur. Total: 24
Maq. 5: Dur. Total: 25,5
Maq. 3: Dur. Total: 28,6
SumUisC: 4
Vemos que esta vez sí, el resultado para esta heurística ha sido peor, por lo que ya
tenemos un caso de referencia para ver cual se comporta mejor. Vemos igualmente
que el código podemos afirmar que es correcto ya que en los tres casos coincide con la
experimentación manual.
Una vez que hemos estudiado todos los problemas pasaremos a realizar la
comparación de las dos heurísticas para ver cual se comporta mejor.
Proyecto fin de Carrera 2014
83
4.4 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS
Una vez obtenidos los datos de las comprobaciones, vamos a analizarlos para ver cuál
es la tendencia en la comparación de ambas heurísticas.
Vemos que vuelve a existir la tendencia que venimos comentando durante todo el
trabajo de que la heurística Greedy se comporta mejor que la heurística Conway. Estos
observa en el segundo y tercer problema estudiados, en donde se ha incrementado el
número de trabajos en una unidad.
Aunque en el primero no ha habido diferencias en el descarte de trabajos, tanto en el
segundo como en el tercero se ha descartado una unidad más. En el segundo
problema pasando de 2 a 3 y en el tercero de 3 a 4, por lo que seguimos en el camino
comentado.
Por tanto, dado que en Lmax también se comportaba Greedy mejor que Conway, y que
la única discrepancia que tenemos para este caso también apoya esta teoría la
presupondremos como cierta, por lo que se tomará como referencia positiva el que
Greedy se comporte mejor que Conway de cara a las gráficas que realizaremos.
A pesar de este razonamiento debemos hacer un estudio más detallado del mismo,
por lo que resolveremos la batería de 1140 problemas que teníamos prevista para este
apartado.
Puesto que el número de problemas a resolver es tan extenso, vamos a clasificarlos
por el tipo de variables, como hicimos también para el caso de Lmax, por lo que para
cada conjunto de variables resolveremos un total de 10 problemas, por lo que nos
queda que resolveremos 57 tipos de problemas con variables distintas, la
compararemos entre ellas.
Por si resulta de interés del lector, hemos añadido en el Anexo XIII los valores de ΣUi
que han salido de medio para cada tipo de problema, tanto para la heurística Greedy
como para la Conway, así como la diferencia a nivel porcentual de ambos, con el
objetivo de hacer un estudio de las mismas.
Como ya comentamos en la comparación del apartado anterior, la gran cantidad de
datos con la que estamos tratando, tanto de variables, como de máquinas, trabajos y
datos, nos obligan a no prescindir del uso de gráficas, que mostraremos y
describiremos a continuación.
Debido a que tenemos 3 variables, y solo podemos hacer gráficas bidimensionales,
puesto que el papel no nos permite otra cosa de forma clara, mostraremos 4 gráficas,
una para cada número de máquinas utilizadas, que nos haga ver el comportamiento de
estas con respecto a la variación en el número de trabajos y la carga, es decir, lo muy o
Proyecto fin de Carrera 2014
84
poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1 sería
muy comprimido y C3 poco comprimido.
La primera gráfica sería para problemas con 4 máquinas, siendo porcentajes positivos
que el algoritmo Greedy se comporta mejor que el Conway, y negativos en caso
contrario, como se ve a continuación:
De nuevo vemos que ocurre lo mismo que ocurría para el caso de Lmax para este tipo
de problemas Qm. Como dijimos, al haber disminuido en media la velocidad de
procesamiento de las máquinas, hemos hecho que los problemas estén ahora más
comprimidos. Esto hace que los problemas de tipo C3 se acerquen más al punto medio
mientras que los de tipo C1 y C2 se alejan.
Como podemos observar, este razonamiento lleva a que los problemas con menor
compresión sean los que mejor se comporten, ya que contrarrestan el efecto de la
disminución de la velocidad. Esto es lo que pasa con aquellos del tipo C3. Por otro lado,
vemos que los de tipo C1 y C2, tal y como pasaba en el caso de Lmax, presentan
mayores diferencias entre heurísticas cuanto menor número de trabajos existen,
debido a que este es otro parámetro que hace equilibrar la compresión de los mismos.
De este modo pasamos a observar la gráfica para este tipo de problemas con el caso
de 8 máquinas, que presentamos a continuación:
Proyecto fin de Carrera 2014
85
En el mismo camino de lo comentado anteriormente vemos como aquellos trabajos
con menor compresión siguen siendo los que mayor diferencia entre heurísticas
presentan. Esto es debido al contrarresto que se produce por el aumento de
compresión dado por la disminución de velocidad de las máquinas. De nuevo son los
trabajos C3, aumentando a una cifra record el valor de la diferencia, que llega a pasar
del 25 %.
Para el resto de tipos de problemas, aquellos con compresión intermedia, C2, y de
compresión alta, C1, vemos como las diferencias se van aumentando progresivamente
con respecto a la anterior gráfica, y además se produce de una forma mucho más
estable, por lo que se reduce su variabilidad. Esto es debido a que se ha aumentado el
número de máquinas, lo que es un apoyo a la normalización de la compresión de
forma que contrarresta aquella producida por la disminución de la velocidad que ya
hemos comentado. Veremos cómo las siguientes gráficas siguen en la misma línea.
Tras este análisis vamos a observar la gráfica de los problemas de 16 máquinas para
ver si nos facilita nueva información:
Proyecto fin de Carrera 2014
86
Vamos viendo como aquí si ya el efecto del aumento de máquinas va teniendo mayor
importancia, ya que los trabajos de compresión intermedia se van acercando a los,
todavía superiores en diferencia, de compresión baja.
Igualmente, tal y como comentábamos antes, la diferencia con respecto al número de
trabajos también se hace apreciable y clara, disminuyendo esta diferencia cuando
aumenta el número de trabajos, como ya viene pasando. De igual forma la variabilidad
en esta línea se hace casi nula y la progresión de esta muy evidente.
Ahora por último vamos a analizar la gráfica de los problemas de 32 máquinas, que se
muestra a continuación:
Proyecto fin de Carrera 2014
87
Por último, esta gráfica nos demuestra lo que ya veníamos apuntando en las
anteriores. Estamos observando como por fin la curva (que es prácticamente una
recta, debido a su nula variabilidad) de los problemas de compresión media, C2,
superan para bajo número de trabajos a aquellos con compresión baja, que eran los
que estaban dominando en diferencia en las anteriores gráficas, confirmando nuestra
tendencia.
Además, vemos la tendencia clarísima de disminuir la variabilidad cuando aumentan el
número de trabajos, especialmente aquí en los trabajos de media y alta compresión,
que de nuevo nos dan la razón.
Por tanto vamos a pasar a hacer unos comentarios generales sobre este bloque que
nos permitan sacar unas conclusiones para el apartado final que tiene este nombre.
Por todo esto me atrevo a sacar una serie de conclusiones para problemas Qm||ΣUi,
en la comparación del algoritmo Greedy con el Conway, que son las siguientes:
• En líneas generales, la heurística Greedy se suele comportar mejor que la
Conway para este tipo de problemas, especialmente para trabajos de baja
compresión.
• La diferencia entre ambas heurísticas se hace mayor cuanto más se acerca al
entorno de compresión medio definido para problemas Pm.
• En este sentido para pocas máquinas los que mayor diferencia presentan son
los problemas C3, pero a medida que van disminuyendo los trabajos y
aumentado las máquinas los problemas C2 van aumentando su diferencia
ampliamente mientras que los de alta compresión, C1, la van aumentando
levemente.
Proyecto fin de Carrera 2014
88
Tras estos puntos anteriores que coinciden en lo básico con el caso de Lmax, podemos
decir también.
• Para todos los tipos de trabajos vemos una dependencia clara entre la
diferencia entre heurísticas y el número de trabajos, aumentando la primera a
medida que disminuye el número de la segunda.
• Se producen valores de las diferencias generalmente más altos que para el caso
de Lmax, siendo comunes valores de en torno al 25% para el mínimo número
de trabajos, pero para casi todos los números de máquinas, exceptuando el
menor de 4 máquinas.
Con esto podemos sacar la siguiente conclusión final:
Por tanto, como conclusión general, para Qm||ΣUi, Greedy funciona mejor que
Conway, y debido a la compresión artificial creada por la disminución de
velocidades de las máquinas, la diferencia es mayor cuanto más se acerque al
punto compresión intermedia. Destaca la dependencia de esta diferencia con
respecto al número de trabajos, siendo muy significativa su disminución cuando
este aumenta. De hecho, se produce la mayor diferencia de todos los casos (en
torno al 25%) para el menor número de trabajos y para casi todos los números
de máquinas, exceptuando el menor (4 mqs.).
Proyecto fin de Carrera 2014
89
CAPÍTULO 7
MODELO Pm||ΣT i
Proyecto fin de Carrera 2014
90
7. MODELO Pm||ΣT i
7.1 INTRODUCCIÓN
De nuevo en este capítulo volvemos al tipo de máquinas inicial, las máquinas idénticas,
es decir, aquellas que tienen la misma velocidad de procesamiento. Se trata ahora de
encontrar el valor del sumatorio de Ti. Este sumatorio es la suma de los retrasos
totales que se producen en los problemas analizados, y el objetivo, como ha venido
siendo siempre, es minimizarlo.
Buscaremos implementar diferentes heurísticas sobre este problema con el objetivo
de ver cual se comporta mejor en función de unos determinados valores o variables
que serán de nuestro interés. Estas heurísticas serán muy similares al caso de las de los
apartados anteriores, por lo que no necesitarán tan extensa explicación. Por ello, a
través de la batería de problemas previamente creados estudiaremos los resultados
para observar cual nos proporciona un mejor comportamiento. Se resolverán con el
programa Visual Basic y básicamente compararemos el algoritmo Conway con el
algoritmo Greedy.
Proyecto fin de Carrera 2014
91
7.2 HEURÍSTICA GREEDY
Para este tipo de problemas, por primera vez, no será el ordenar los trabajos mediante
el algoritmo EDD lo que de la mejor solución, por lo que utilizaremos otro tipo de
algoritmo que explicaremos a continuación.
A diferencia del resto de los apartados de este estudio, no se deberá primero ordenar
los trabajos para ver el orden de asignación de los mismos, si no que tantas veces
como trabajos existan debemos decidir que trabajo y a que máquina vamos a asignar.
Para cada iteración descrita (tanta como número de trabajos) debemos ordenar las
máquinas mediante el algoritmo Greedy que hemos venido utilizando, es decir, en
orden decreciente de su tiempo de finalización, siendo primera la que tenga un tiempo
de finalización mayor.
Para esta máquina debemos analizar todos los trabajos con el objetivo de ver cual
asignar. Debemos obtener el número mayor de entre su tiempo de entrega y el
instante en el que finalizaría si se procesase en la máquina elegida, es decir, el tiempo
acumulado de la máquina más el tiempo de procesamiento de este trabajo.
Esto nos dará un valor (el mayor de entre esos dos valores) para cada trabajo,
debiendo asignar aquél para el que este valor sea menor. Es decir, asignamos a cada
trabajo un valor que es el mayor de entre los dos explicados, y el trabajo que tenga
menor valor de entre estos será el asignado.
En el caso de que esa asignación produjese retraso, es decir, el tiempo de
procesamiento supere al tiempo de entrega del trabajo, debemos repetir el proceso
con la siguiente máquina, y así respectivamente hasta que encontrásemos una que no
produjese ningún retraso.
En el caso de que todas las máquinas produjesen retraso deberíamos asignar el trabajo
hallado mediante esta heurística a la última máquina, es decir, a aquella con un tiempo
de finalización menor, y lógicamente no olvidarnos de actualizar el valor del sumatorio
de Ti, es decir, de sumar el retraso producido en esta ocasión. Cuando todos los
trabajos estén asignados se podrá dar por concluida la heurística.
Esta misma lógica que ha sido expresada con palabras ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo XIV.
Pasaremos ahora a resolver los tres problemas que hemos resuelto para los casos
oportunos en los anteriores dos apartados de este proyecto. Como suele ser habitual
cada uno tiene un número de máquinas diferentes. El segundo y el tercero tendrán
cuatro y cinco máquinas respectivamente.
Proyecto fin de Carrera 2014
92
Pero empezaremos con este primero. Destacar de él que de nuevo estamos con
máquinas con velocidades enteras por lo que nos encontraremos que los valores de
esta resolución manual también vuelven a ser enteros. Empezaremos con el de tres
máquinas, y cuyo resultado manual será el siguiente:
Nºs de los trabajos Tiempo
M1 2 11 8 16 10 4 5 6 5 9 13 17 19 23 26 38
M2 15 17 1 12 9 2 9 22 30 46
M3 7 3 13 14 9 17 28 41
Ti 2 3 4 6 12 20 27 44
Vemos que los valores estudiados ahora suelen ser más altos que en los casos
anteriores ya que, lógicamente, Lmax era superior normalmente a Ui, y Ti es la suma
de todos los L, es decir, de todos los retrasos, ya que Lmax tan solo era el mayor de
ellos. Esto hace que los valores de salida sean bastante superiores a los anteriores y
por lo tanto hemos modificado los valores que hacen de cota infinita en el código
hasta llevarlos a los siete dígitos.
Ahora vamos a comprobar si el algoritmo propuesto, como hacíamos en los capítulos
anteriores, es o no correcto. Para ello vemos que la salida del código de comprobación
es la siguiente:
Ti Greedy:
Maq. 3:
Trab. 7 Dur. 9; Trab. 3 Dur. 8; Trab. 13 Dur. 11; Trab. 14 Dur. 13;
Dur. Total: 41
Maq. 1:
Trab. 2 Dur. 5; Trab. 11 Dur. 4; Trab. 8 Dur. 4; Trab. 16 Dur. 4; Trab. 10 Dur. 2; Trab. 4 Dur. 4; Trab. 5 Dur. 3; Trab. 6 Dur. 12;
Dur. Total: 38
Proyecto fin de Carrera 2014
93
Maq. 2:
Trab. 15 Dur. 2; Trab. 17 Dur. 7; Trab. 1 Dur. 13; Trab. 12 Dur. 8; Trab. 9 Dur. 16;
Dur. Total: 46
Ti Greedy: 44
Vemos que aunque no están las maquinas ordenadas en esta salida, los datos son
correctos, por lo que tenemos esta garantía de exactitud del código, tal y como
teníamos previsto.
Vamos a pasar a comprobar el segundo de los problemas que tenemos por costumbre
analizar. En este caso vemos el de cuatro máquinas, cuya resolución manual viene
dada por las asignaciones siguientes:
Nºs de los trabajos Tiempo
M1 2 1 9 8 13 20
M2 4 15
M3 6 9
M4 7 8 3 5 6 8 9 27
Ti 9
Vemos que este caso tiene la peculiaridad de coincidir con el estudio de Lmax por lo
que comentamos anteriormente. Aunque Lmax es el máximo de los retrasos, aquí al
solo existir un retraso el máximo coincide con la suma de ellos. Sin más pasamos a ver
la salida del código del mismo:
Ti Greedy:
Maq. 1:
Trab. 2 Dur. 8; Trab. 1 Dur. 5; Trab. 9 Dur. 7;
Dur. Total: 20
Proyecto fin de Carrera 2014
94
Maq. 2:
Trab. 4 Dur. 15;
Dur. Total: 15
Maq. 4:
Trab. 7 Dur. 6; Trab. 8 Dur. 2; Trab. 3 Dur. 1; Trab. 5 Dur. 18;
Dur. Total: 27
Maq. 3:
Trab. 6 Dur. 9;
Dur. Total: 9
Ti Greedy: 9
De nuevo vemos que aunque las máquinas están desordenadas como en el caso
anterior, el resultado es exactamente el mismo que hemos obtenido por el método
manual, por lo que el código vuelve a ser el correcto.
Vamos una vez analizado esto con el tercer y último problema, esta vez para el de 5
máquinas, que nos da el resultado manual que se muestra a continuación y que
compararemos luego:
Nºs de los trabajos Tiempo
M1 6 7 20 3 18 5 7 12 20 28
M2 11 19 12 11 18 27
M3 9 5 13 9 18 26
M4 15 17 21 14 5 10 24 31
M5 1 2 4 16 10 8 1 5 10 14 18 31
Ti 2 7
Proyecto fin de Carrera 2014
95
Cabe destacar que no hay valores decimales ni en este ni en los problemas anteriores
como dijimos al principio de este apartado. Pasamos a ver la salida del código para
este problema, que será la siguiente:
Ti Greedy:
Maq. 5:
Trab. 1 Dur. 1; Trab. 2 Dur. 4; Trab. 4 Dur. 5; Trab. 16 Dur. 4; Trab. 10 Dur. 4; Trab. 8 Dur. 13;
Dur. Total: 31
Maq. 4:
Trab. 15 Dur. 5; Trab. 17 Dur. 5; Trab. 21 Dur. 14; Trab. 14 Dur. 7;
Dur. Total: 31
Maq. 1:
Trab. 6 Dur. 5; Trab. 7 Dur. 2; Trab. 20 Dur. 5; Trab. 3 Dur. 8; Trab. 18 Dur. 8;
Dur. Total: 28
Maq. 3:
Trab. 9 Dur. 9; Trab. 5 Dur. 9; Trab. 13 Dur. 8;
Dur. Total: 26
Maq. 2:
Trab. 11 Dur. 11; Trab. 19 Dur. 7; Trab. 12 Dur. 9;
Dur. Total: 27
Proyecto fin de Carrera 2014
96
Ti Greedy: 7
Vemos que el resultado del mismo es idéntico al ya obtenido de forma manual, por lo
que podemos decir que el código es correcto, una vez efectuadas las tres
comprobaciones para los problemas que venimos efectuando en este estudio.
Pasaremos una vez comentado esto a detallar la siguiente heurística.
Proyecto fin de Carrera 2014
97
7.3 HEURÍSTICA CONWAY
Como viene siendo habitual compararemos esta heurística con la anterior, que
aunque tienen varios puntos de coincidencia, como veremos en los resultados finales,
da un resultado diferente.
Como ya dijimos anteriormente no se deberá primero ordenar los trabajos para ver el
orden de asignación de los mismos, si no que tantas veces como trabajos existan
debemos decidir que trabajo y a que máquina vamos a asignar.
Para cada iteración descrita (tanta como número de trabajos) debemos ordenar las
máquinas mediante el algoritmo Conway que hemos venido utilizando, es decir, en
orden creciente de su tiempo de finalización, siendo primera la que tenga un tiempo
de finalización menor.
Para esta máquina (la de tiempo de finalización menor) debemos analizar todos los
trabajos con el objetivo de ver cual asignar. Debemos obtener el número mayor de
entre su tiempo de entrega y el instante en el que finalizaría si se procesase en la
máquina elegida, es decir, el tiempo acumulado de la máquina más el tiempo de
procesamiento de este trabajo.
Esto nos dará un valor (el mayor de entre esos dos valores) para cada trabajo,
debiendo asignar aquél cuyo valor sea menor. Es decir, asignamos a cada trabajo un
valor que es el mayor de entre los dos explicados, y el trabajo que tenga menor valor
de entre estos será el asignado.
En caso de que se produjese retraso no se debe buscar asignar el trabajo en otra
máquinas, como hacíamos en el apartado anterior, ya que la máquina que estamos
asignando es la de menor tiempo de funcionamiento y por lo tanto la máquina límite.
Eso sí, si se produjese este citado retraso, al igual que hemos hecho anteriormente,
habría que actualizar el sumatorio de Ti.
Esta misma lógica que ha sido expresada con palabras, ha sido programada en lenguaje
C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo XV.
Visto esto veremos, como hicimos en el apartado anterior, tres ejemplos de ello, que
nos servirán, tras ser realizados manualmente, de comprobación del código
programado y mencionado anteriormente.
Como ya dijimos anteriormente, los ejemplos realizados son los mismos para todos los
tipos de problemas, por lo que para no repetir aspectos comunes, como pudiera ser
los datos de los trabajos así como su orden con respecto al algoritmo EDD, se han
presentado estos en el Anexo III para que sean de fácil disposición al lector.
Proyecto fin de Carrera 2014
98
Una vez aclarados estos aspectos pasaremos a resolver, tal y como hicimos en el
apartado anterior, los problemas a mano con el objetivo de comprobar la validez del
código.
Empezaremos por el de 3 máquinas, pero no presentaremos los datos, ya que, como
hemos dicho, están expuestos en el Anexo III.
Por tanto, conforme a esta asignación, los trabajos en las máquinas quedarían de la
siguiente forma:
Nºs de los trabajos Tiempo
M1 2 17 10 13 5 12 5 12 14 25 28 36
M2 7 3 1 14 9 17 30 43
M3 15 11 8 16 4 6 9 2 6 10 14 18 30 46
Ti 2 3 4 5 8 18 23 32 49
Observamos que en este primer problema, el resultado de esta heurística nos da un
retraso ligeramente superior al que nos daba la primera heurística, por lo que parece
que la tendencia que estamos viendo en el estudio sigue igual.
Ahora veremos cuál es el resultado que nos da el código propuesto en el Anexo XV,
con el objetivo de comprobar su veracidad. Este será el resultado del mismo:
Ti Conway:
Maq. 2:
Trab. 7 Dur. 9; Trab. 3 Dur. 8; Trab. 1 Dur. 13; Trab. 14 Dur. 13;
Dur. Total: 43
Maq. 1:
Trab. 2 Dur. 5; Trab. 17 Dur. 7; Trab. 10 Dur. 2; Trab. 13 Dur. 11; Trab. 5 Dur. 3; Trab. 12 Dur. 8;
Dur. Total: 36
Proyecto fin de Carrera 2014
99
Maq. 3:
Trab. 15 Dur. 2; Trab. 11 Dur. 4; Trab. 8 Dur. 4; Trab. 16 Dur. 4; Trab. 4 Dur. 4; Trab. 6 Dur. 12; Trab. 9 Dur. 16;
Dur. Total: 46
Ti Conway: 49
Vemos que los resultados de ambos son exactamente los mismos, por lo que el primer
paso hacia la comprobación que estamos efectuados ha sido dado con éxito.
Ahora pasaremos al problema de 4 máquinas, en el que la asignación manual que
hemos realizado es la siguiente, incluyendo los valores en cada iteración:
Nºs de los trabajos Tiempo
M1 7 9 6 13
M2 8 6 2 11
M3 3 1 4 1 6 21
M4 2 5 8 26
Ti 15
En este caso existe una diferencia notable con la primera heurística. Ahora, como
siempre, vemos el resultado que nos proporciona el programa Visual Basic y lo
comparamos con el mismo:
Ti Conway:
Maq. 3:
Trab. 3 Dur. 1; Trab. 1 Dur. 5; Trab. 4 Dur. 15;
Dur. Total: 21
Proyecto fin de Carrera 2014
100
Maq. 1:
Trab. 7 Dur. 6; Trab. 9 Dur. 7;
Dur. Total: 13
Maq. 2:
Trab. 8 Dur. 2; Trab. 6 Dur. 9;
Dur. Total: 11
Maq. 4:
Trab. 2 Dur. 8; Trab. 5 Dur. 18;
Dur. Total: 26
Ti Conway: 15
De nuevo el resultado es idéntico, por lo que la comprobación es perfecta y podemos
pasar al tercer y último ejemplo de este bloque antes de ejecutar los 1140 ejemplos
pertenecientes a este capítulo.
Así, pasamos a ver cuál es el resultado de nuestra resolución manual para el tercer
problema de 5 máquinas:
Nºs de los trabajos Tiempo
M1 1 20 9 8 1 6 15 28
M2 15 17 10 19 12 5 10 14 21 30
M3 7 4 5 13 2 7 16 24
M4 6 11 21 5 16 30
M5 2 16 3 18 14 4 8 16 24 31
Ti 1 3 11
Proyecto fin de Carrera 2014
101
Vemos que para este problema el retraso también ha aumentado con respecto a la
primera heurística. De nuevo se confirma la tendencia que estamos estudiando.
Y el resultado proporcionado por el código del programa que estamos utilizando sería
el que se muestra a continuación:
Ti Conway:
Maq. 2:
Trab. 15 Dur. 5; Trab. 17 Dur. 5; Trab. 10 Dur. 4; Trab. 19 Dur. 7; Trab. 12 Dur. 9;
Dur. Total: 30
Maq. 4:
Trab. 6 Dur. 5; Trab. 11 Dur. 11; Trab. 21 Dur. 14;
Dur. Total: 30
Maq. 1:
Trab. 1 Dur. 1; Trab. 20 Dur. 5; Trab. 9 Dur. 9; Trab. 8 Dur. 13;
Dur. Total: 28
Maq. 3:
Trab. 7 Dur. 2; Trab. 4 Dur. 5; Trab. 5 Dur. 9; Trab. 13 Dur. 8;
Dur. Total: 24
Maq. 5:
Trab. 2 Dur. 4; Trab. 16 Dur. 4; Trab. 3 Dur. 8; Trab. 18 Dur. 8; Trab. 14 Dur. 7;
Proyecto fin de Carrera 2014
102
Dur. Total: 31
Ti Conway: 11
Que como se comprueba, aunque estén las máquinas desordenadas, de nuevo es
idéntico, por lo que podemos asegurar que los códigos de ambas heurísticas son
correctos, con lo que pasamos resolver la colección de problemas generados y
compararlas en el siguiente apartado.
Proyecto fin de Carrera 2014
103
7.4 COMPARACIÓN ENTRE AMBAS HEURÍSTICAS
Una vez obtenidos los datos de las comprobaciones, vamos a analizarlos para ver cuál
es la tendencia en la comparación de ambas heurísticas.
Vemos que para el caso de tres máquinas aumenta el sumatorio de Ti en 5 unidades de
44 a 49, comportándose mejor el algoritmo Greedy. Por otro lado, para el ejemplo de 4
máquinas la variación es de 6 unidades, de 9 a 15. Por último, para el ejemplo con 5
máquinas de nuevo se comporta mejor el algoritmo Greedy, con el sumatorio de 7,
mientras que Conway presenta 11, por lo que existe una diferencia de 4.
Este interesante razonamiento para los ejemplos nos permite observar, como
habíamos previsto, que el algoritmo Greedy se comporta mejor, pero debemos hacer
un estudio más detallado del mismo, por lo que resolveremos la batería de 1140
problemas que teníamos prevista para este apartado.
Puesto que el número de problemas a resolver es tan extenso, vamos a clasificarlos
por el tipo de variables, por lo que para cada conjunto de variables resolveremos un
total de 10 problemas. Nos queda por resolver 57 tipos de problemas con variables
distintas, que compararemos entre ellas.
Por si resulta de interés del lector, hemos añadido en el Anexo XVI los valores del
sumatorio de Ti que han salido de media para cada tipo de problema, tanto para la
heurística Greedy como para la Conway, así como la diferencia a nivel porcentual de
ambos, con el objetivo de hacer un estudio de las mismas.
Debido a la gran cantidad de datos de salida que tenemos tras implementar esta
cantidad de problemas en nuestro algoritmo, y que han sido mostrados en forma de
media en el Anexo XVI, nos vemos obligados a utilizar unas gráficas con nos permitan
ver de forma más clara cuál ha sido el comportamiento de las heurísticas en función de
las variables.
Debido a que tenemos 3 variables, y solo podemos hacer gráficas bidimensionales,
puesto que el papel no nos permite otra cosa de forma clara, mostraremos 4 gráficas,
una para cada número de máquinas utilizadas, que nos permita ver el comportamiento
de estas con respecto a la variación en el número de trabajos y la carga, es decir, lo
muy o poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1
sería muy comprimido y C3 poco comprimido.
La primera gráfica sería para problemas con 4 máquinas, siendo porcentajes positivos
que el algoritmo Greedy se comporta mejor que el Conway, y negativos en caso
contrario, como se ve a continuación:
Proyecto fin de Carrera 2014
104
Vemos que para este caso de pocas máquinas se presenta una alta compresión en los
problemas, por lo que la mayor diferencia viene dada para los problemas de baja
compresión, que presenta una alta variabilidad, lo que no permite sacar consecuencias
claras.
Para problemas de compresión media se produce una diferencia moderada que
veremos irá aumentando a medida que lo haga el número de máquinas. En esta
primera gráfica destaca además por su estabilidad.
Por último los problemas de alta compresión, como era de esperar, sufren una
compresión excesiva que lleva a que la diferencia entre heurísticas tienda a cero.
Veremos ahora para 8 máquinas:
Proyecto fin de Carrera 2014
105
Para este tipo de problemas vemos como se imponen en diferencia aquellos que
tienen una compresión intermedia, llegando a valores mucho mas altos de los que se
tenían para la gráfica anterior.
Sin embargo, para problemas con compresión baja observamos que han bajado de
media los valores en los que se situaban para el caso de 4 máquinas pero conservan su
alta variabilidad, siendo impredecible al igual que ocurría en el caso anterior.
Por último seguir comentando que para problemas de alta compresión la diferencia
sigue siendo cercana a cero pero va aumentando en valor con respecto al caso de 4
máquinas, debido al descenso de la compresión. También se evidencia el efecto de
esta en su dependencia con respecto al número de trabajos, cuya pendiente va
aumentando.
Veremos ahora el caso de los problemas de 16 máquinas:
Vemos ahora como destaca la estabilidad de todos los tipos de problemas. Aunque los
de baja compresión, que eran los que presentaban mayor variabilidad, aún presentan
alguna, se ha reducido considerablemente con respecto a los valores anteriores.
Mucha más tiene los de compresión intermedia y los de alta, que son prácticamente
una línea recta. Vemos que este tipo de problemas C2 son los que siguen dominando
en diferencia entre heurísticas y el valor de estas diferencias sigue en aumento.
Por último, para problemas de gran número de máquinas, 32 en este caso:
Proyecto fin de Carrera 2014
106
Observamos aquí que la diferencia entre los distintos tipos de problemas es
aplastante. Mientras que los problemas de alta y baja compresión tienen unas
diferencias que varían entre el 0% y el 5%, aquellos de compresión intermedia están
muy por encima de estos y presentan valores de más del 40% de diferencia, lo cual
supone un verdadero record en este estudio.
Con todo esto me atrevo a sacar una serie de conclusiones para problemas Pm||ΣTi,
en la comparación del algoritmo Greedy con el Conway, que son las siguientes:
• En líneas generales, la heurística Greedy se suele comportar mejor que la
Conway para este tipo de problemas.
• La diferencia entre ambas heurísticas se hace mayor cuanto más se acerca al
entorno de compresión medio definido para problemas Pm.
Proyecto fin de Carrera 2014
107
• En este sentido para pocas máquinas los que mayor diferencia presentan son
los problemas C3, pero a medida que van disminuyendo los trabajos y
aumentado las máquinas los problemas C2 van aumentando su diferencia
ampliamente mientras que los de alta compresión, C1, la van aumentando muy
levemente.
• La mayor diferencia se da para el mayor número de máquinas y un número de
trabajos intermedio, y supone un verdadero record al superar el 40%.
Por tanto, como conclusión general, para Pm||ΣTi, Greedy funciona mejor que
Conway, y salvo para bajo número de máquinas la diferencia es mayor para problemas
de compresión intermedia. Los problemas de alta compresión no presentan una gran
diferencia entre heurísticas. El punto de mayor valor de la diferencia se da para el
mayor número de máquinas y compresión y número de trabajos intermedios, y
presenta un valor record en el estudio que supera el 40%.
Proyecto fin de Carrera 2014
108
CAPÍTULO 8
GENERACIÓN Y LECTURA
Proyecto fin de Carrera 2014
109
8. GENERACIÓN Y LECTURA
8.1 INTRODUCCIÓN
En este capítulo se van a presentar diferentes aspectos de la ejecución del estudio,
entre ellos las diferentes variables utilizadas para los problemas de este proyecto en
particular. Posteriormente veremos cómo hemos generado la colección de problemas
que hemos utilizado, para posteriormente analizar el algoritmo y las características
técnicas que nos han permitido leer los datos y llevar a cabo el proyecto.
Proyecto fin de Carrera 2014
110
8.2 DESCRIPCIÓN DE LAS VARIABLES
Aunque a estas alturas del proyecto ya son de sobra conocidas las variables utilizadas
en el mismo para los diferentes problemas, vamos a pasar a describirlas con el objetivo
de que podamos comprender posteriormente de forma satisfactoria como se han
generado los problemas estudiados.
Básicamente son tres las variables que se han utilizado para definir los problemas:
• Número de trabajos: se trata de la cantidad de trabajos que han sido asignados
a las máquinas correspondientes. Cuantos más trabajos existan más
comprimido estará el problema, y más retraso existirá en el mismo. Se han
utilizado seis números de trabajos: 25, 50, 100, 200, 400 y 800 trabajos.
• Número de máquinas: esta variable se refiere lógicamente a la cantidad de
máquinas disponibles en el problema a la que se les pueden asignar trabajos.
En este estudio las hemos tratado de dos tipos:
o Idénticas: todas tienen la misma velocidad de funcionamiento.
o Uniformes: cada una tiene una velocidad diferente de funcionamiento.
Nosotros la hemos puesto en el intervalo 1- 1.5
A medida que el número de máquinas disminuye, el problema se encuentra
más comprimido, de forma que el retraso producido en el mismo será
mayor. Se han utilizado cuatro números de máquinas: 4, 8, 16 y 32
máquinas.
• Compresión: La compresión es quizás la variable más interesante puesto que
está relacionada con las otras dos y por lo tanto es la que marca la tendencia
del trabajo a tener una mayor o menor diferencia entre ambas heurísticas,
como hemos venido viendo empíricamente en los apartados anteriores.
Sabemos que a mayor compresión los retrasos provocados serán mayores y a
menor compresión dichos retrasos disminuirán.
Debido a que ha sido un valor difícil de cuantificar, se ha tomado como valor
intermedio los problemas en los que, para unos trabajos con una duración
marcado por una normal N(100,1), el tiempo de finalización de los mismos
viniese marcado por otra normal de la forma: . Se
explicará mejor en el siguiente apartado.
Proyecto fin de Carrera 2014
111
8.3 GENERACIÓN DE LOS PROBLEMAS
Vamos a ver en este apartado cual ha sido el proceso y el criterio de generación de los
distintos problemas utilizados en este estudio.
En primer lugar decir que los problemas iniciales estudiados como ejemplos manuales
en cada apartado han sido creados de forma totalmente manual y aleatoria, buscando
la complejidad en los mismos así como que fueran diferentes y con una cierta trampa
de cara a que se diesen casos confusos para el código que pudiera hacernos estar
seguro de que funcionaba a la corrección.
Por ello se eligieron problemas de 3, 4 y 5 máquinas, con distintos números de
trabajos, con el objetivo de que su resolución manual fuera factible pero que pudieran
ser lo suficientemente largos como para poner al código en apuros. Una vez
comprobada en cada apartado la validez del código pasábamos a resolver el conjunto
1140 problemas que se buscaban comparar para cada apartado.
Estos 1140 problemas, debido a su amplio número, no han podido ser diseñados
manualmente, por lo que se ha creado un algoritmo a través del programa Visual Basic
que ha permitido su creación automática, así como una serie de archivos de textos con
unas características determinadas que pudieran leerse posteriormente por otro
código.
Así, el formato en el que se han creado los archivos de texto ha sido el formado por
tantas líneas como trabajos existiesen, encabezado por dos líneas en la parte superior.
La primera de ellas ha sido el número de trabajos existentes, las segunda el número de
máquinas, seguidas por tantas líneas como trabajos había. Cada una de estas líneas de
trabajos contenía dos datos separados por una coma. El primero se refería a la
duración del trabajo mientras que el segundo era el relativo a la fecha de finalización
del mismo.
Por otra parte no para cada número de máquinas existían todos los números de
trabajos, puesto que algunos eran casos extremos que se han desechado por su falta
de idoneidad. De esta forma, para el caso de 8 máquinas se han desechado los
problemas de 25 trabajos, y para los de 16 y 32 máquinas se han obviado, aparte de
estos de 25 trabajos, también los de 50 trabajos. Esto es debido a que para estos casos
la compresión es demasiado baja y por tanto los retrasos serían mínimos, produciendo
una gran volatilidad en las diferencias entre los mismos, que distorsionaría el estudio.
Como se ha dicho antes, para cada trabajo se ha calculado un valor del tiempo de
ejecución aleatorio entre 1 y 100, constante para todas las variables. Por otro lado, el
valor del tiempo de finalización de los trabajos ha venido dado por otra función
Proyecto fin de Carrera 2014
112
aleatoria pero esta vez en el rango entre 10 y , por lo que sí que
dependía del resto de variables.
Controlando este valor del tiempo de finalización de los trabajos se han podido
comprimir en mayor o menor medida los problemas. De esta forma se han establecido
tres tipos. Los mas comprimidos, C1, cuyo valor máximo de finalización se ha dividido a
la mitad ( ), los de compresión intermedia, C2, que son el caso
estándar comentado anteriormente, y los menos comprimidos, C3, cuyo valor de
finalización límite se ha multiplicado por dos ( ).
Por si resulta de interés del lector, algunas partes del código de generación se
muestran en el Anexo XVII con la intención de que quede más claro lo aquí expuesto.
Sin más, pasamos al último bloque de este apartado.
Proyecto fin de Carrera 2014
113
8.4 LECTURA DE LOS PROBLEMAS
En este apartado describiremos brevemente como se ha realizado la lectura de los
1140 problemas anteriormente generados, de cara a poder implementar el código que
habíamos diseñado.
Lo primero que se debe es crear un conjunto de bucles para cada número de trabajos y
cada número de máquinas con el objetivo de que se resuelva el problema una vez que
los índices estén colocados en la posición correcta para ellos. No debemos olvidar de
que ya que existen 10 problemas para cada conjunto de variables debemos crear otro
bucle adicional para ir recorriendo los índices relativos a estos problemas.
Para cada uno de estos problemas debemos leer los datos y extraerlos correctamente
antes de pasarlo por el código que hemos creado por lo que crearemos la referencia su
dirección a través de los índices que hemos creado en la parte de generación para
definir a cada uno de los archivos de texto. En nuestro caso la llamada sería la
siguiente:
…acion\File" & "_" & CStr(indclasetrabajo) & "_" & CStr(numtrabajos) & "_" &
CStr(nummaquinas) & "_" & CStr(indice) & ".txt"
Una vez que tenemos el archivo de texto ubicado en nuestro código debemos extraer
los datos mediante instrucciones de posicionamiento para deshacernos de los espacios
que separan estos datos. Algunas de las instrucciones que hemos utilizado han sido
InStr, Len, Right Left…
Cuando tengamos los datos ubicados tan solo debemos ir guardándolos en variables
que posteriormente utilizaremos en nuestro código, de forma que ya hemos
conseguido extraer los datos del archivo de texto y habrá que pasar al siguiente
archivo hasta que acabemos.
Proyecto fin de Carrera 2014
114
CAPÍTULO 9
CONCLUSIONES
Proyecto fin de Carrera 2014
115
9. CONCLUSIONES
Tras la realización y finalización de este proyecto soy capaz de sacar un conjunto de
conclusiones personales del mismo, que en cierto modo me han formado en los
aspectos que se han tratado, y que son las siguientes:
• He sido capaz de afianzar los conocimientos de Scheduling aprendidos en la
asignatura de Secuenciación, teniendo un perfecto dominio de los problemas
estudiados en este trabajo y mejorando la comprensión de los del resto de la
asignatura.
• He mejorado mi capacidad de resolución de problemas por la gran cantidad de
ellos resueltos a mano durante este proyecto, lo que me ayuda a mejorar mi
capacidad analítica.
• He mejorado mis conocimientos y mi práctica en el campo de la programación
informática, en especial con el programa Visual Basic. Me ha servido
igualmente para comprender los procesos lógicos utilizados y mejorar mi
habilidad para crearlos.
• He reforzado mi expresión escrita y de síntesis durante la redacción del trabajo.
Por otra parte, aunque a lo largo de los diferentes capítulos hemos sido capaces de ir
sacando conclusiones al respecto de los datos obtenidos, se ha considerado
interesante hacer un repaso final y estructurar en unas conclusiones generales el
estudio:
• Como conclusión general podemos decir que en todos los casos estudiados el
algoritmo Greedy (asignar a la máquina más cargada) se comporta mejor que
el algoritmo Conway (asignar a la menos cargada). Esto responde a la lógica de
dejar espacio en las máquinas menos cargadas para trabajos que puedan
asignarse posteriormente.
• La diferencia entre ambas heurísticas tiene gran dependencia con la
compresión de los problemas (una de las tres variables usadas). Las mayores
diferencias se dan para compresiones intermedias (ver capítulo anterior para
definir estas compresiones). Tanto el exceso de compresión como la
disminución de compresión de los problemas hacen que la diferencia decrezca
en porcentaje.
Proyecto fin de Carrera 2014
116
• Para problemas con máquinas idénticas (Pm) hay indicios para pensar que la
mayor diferencia se da para compresión intermedia, y en el entorno de la
relación . Esta diferencia máxima ronda el 13% para
Lmax, el 19% para Ui y el 40% para Ti.
• Para problemas con máquinas uniformes (Qm), debido a la pérdida de
velocidad de las máquinas se produce un aumento de la compresión, lo que
hace que los problemas de menor compresión se acerquen al valor medio de
compresión definido para problemas con máquinas idénticas (Pm). Esto sucede
especialmente para bajos números de máquinas. Todo lo anterior hace que los
problemas de menor compresión aumenten su diferencia entre heurísticas.
• En general, para problemas de baja compresión el aumento del número de
trabajos y la disminución del nº máquinas, aumenta la compresión y con ella la
diferencia entre heurísticas.
• En general, para problemas de alta compresión el aumento del número de
máquinas y la disminución del nº trabajos, disminuye la compresión y con ella
aumenta la diferencia entre heurísticas.
Proyecto fin de Carrera 2014
117
CAPÍTULO 10
BIBLIOGRAFÍA
Proyecto fin de Carrera 2014
118
10. BIBLIOGRAFÍA
Mostramos a continuación la bibliografía utilizada para este proyecto:
• Enciclopedia de Visual Basic
Autor: Francisco Javier Ceballos
Editorial: Ra-ma
• Visual Basic
Autor: José Eduardo Maluf de Cervalho
Editorial: McGraw-Hill
• Optimización heurística y redes neuronales
Autores: A.Díaz, F.Glover, H.M.Chaziri, J.L.González, M.Segura, P.Moscato,
F.T.Seng
Editorial: Paraninfo
• Sheduling. Theory, Algorithms and Systems.
Autor: M.Pinedo
Editorial: Prentice-Hall, 1995
• Wikipedia.com
http://en.wikipedia.org/wiki/Scheduling_(computing)
Proyecto fin de Carrera 2014
119
CAPÍTULO 11
ANEXOS
Proyecto fin de Carrera 2014
120
ANEXO I
Código de la programación del problema Pm||Lmax para la heurística EDD&Greedy.
Proyecto fin de Carrera 2014
121
ANEXO II
Código de la programación del problema Pm||Lmax para la heurística EDD&Conway.
Proyecto fin de Carrera 2014
122
ANEXO III
Orden de los trabajos de los problemas de comprobación, tanto introducidos en el
código (izquierda), como por EDD (derecha).
� Problema de tres máquinas:
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
13 20 1 5 3 2
5 3 2 2 5 15
8 16 3 9 8 7
4 24 4 4 9 11
3 31 5 7 11 17
12 30 6 4 15 8
9 8 7 8 16 3
4 15 8 4 18 16
16 29 9 13 20 1
2 21 10 2 21 10
4 9 11 11 22 13
8 31 12 4 24 4
11 22 13 16 29 9
13 34 14 12 30 6
2 5 15 8 31 12
4 18 16 3 31 5
7 11 17 13 34 14
� Problema de 4 máquinas:
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
5 13 1 15 6 4
8 10 2 6 8 7
1 12 3 8 10 2
15 6 4 2 11 8
18 32 5 1 12 3
9 14 6 5 13 1
6 8 7 9 14 6
2 11 8 7 21 9
7 21 9 18 32 5
Proyecto fin de Carrera 2014
123
� Problema de cinco máquinas
Trabajos orden inicial Trabajos orden EDD
Duración Fecha de entrega Nº trabajo Duración Fecha de entrega Nº trabajo
1 2 1 1 2 1
4 6 2 4 6 2
8 21 3 5 7 15
5 13 4 5 9 6
9 18 5 2 11 7
5 9 6 5 12 20
2 11 7 5 13 4
13 26 8 4 14 16
9 17 9 11 15 11
4 22 10 5 15 17
11 15 11 9 17 9
9 31 12 9 18 5
8 29 13 8 21 3
7 32 14 4 22 10
5 7 15 14 22 21
4 14 16 7 23 19
5 15 17 13 26 8
8 28 18 8 28 18
7 23 19 8 29 13
5 12 20 9 31 12
14 22 21 7 32 14
Proyecto fin de Carrera 2014
124
ANEXO IV
Resultado de los valores medios de Lmax para cada tipo de problema Pm||Lmax según
sus variables, tanto para algoritmo Greedy como para algoritmo Conway, así como sus
diferencias porcentuales.
Carga Nmaq Ntrab LmG media LmC media Diferencia Dif. Porc.
1 4 25 204,4 202,3 -2,1 -1,03%
1 4 50 354,8 357,6 2,8 0,79%
1 4 100 667,4 668,2 0,8 0,12%
1 4 200 1362,7 1369,3 6,6 0,48%
1 4 400 2653,7 2653,9 0,2 0,01%
1 4 800 5098,3 5108,8 10,5 0,21%
1 8 50 204,2 207,8 3,6 1,76%
1 8 100 401,7 397,7 -4 -1,00%
1 8 200 688,1 688 -0,1 -0,01%
1 8 400 1331,7 1342,7 11 0,83%
1 8 800 2648,2 2665 16,8 0,63%
1 16 100 213,8 220,7 6,9 3,23%
1 16 200 385,5 391,8 6,3 1,63%
1 16 400 686,3 691,2 4,9 0,71%
1 16 800 1332,4 1337,4 5 0,38%
1 32 100 131,4 143,1 11,7 8,90%
1 32 200 210,2 225,8 15,6 7,42%
1 32 400 377,8 387,3 9,5 2,51%
1 32 800 689,2 706,8 17,6 2,55%
2 4 25 75,6 75,5 -0,1 -0,13%
2 4 50 103,9 111,9 8 7,70%
2 4 100 171 179 8 4,68%
2 4 200 228,3 231,7 3,4 1,49%
2 4 400 275,1 276,7 1,6 0,58%
2 4 800 456,5 463,5 7 1,53%
2 8 50 72,6 78,3 5,7 7,85%
2 8 100 108,1 108,7 0,6 0,56%
2 8 200 106,6 120,3 13,7 12,85%
2 8 400 140,6 146,4 5,8 4,13%
2 8 800 237,6 246 8,4 3,54%
2 16 100 76,1 78,1 2 2,63%
2 16 200 92,9 101 8,1 8,72%
2 16 400 111 120,6 9,6 8,65%
2 16 800 138,5 146,3 7,8 5,63%
Proyecto fin de Carrera 2014
125
2 32 100 75,3 76 0,7 0,93%
2 32 200 77,2 81,6 4,4 5,70%
2 32 400 81,2 88,2 7 8,62%
2 32 800 107,6 119,3 11,7 10,87%
3 4 25 36,8 36,8 0 0,00%
3 4 50 33,1 32,1 -1 -3,02%
3 4 100 27,8 28,9 1,1 3,96%
3 4 200 39,9 39,9 0 0,00%
3 4 400 43,8 45,5 1,7 3,88%
3 4 800 49,7 49,8 0,1 0,20%
3 8 50 45,4 45,4 0 0,00%
3 8 100 46,9 46,9 0 0,00%
3 8 200 49 49,6 0,6 1,22%
3 8 400 42,5 42,5 0 0,00%
3 8 800 45,9 45,9 0 0,00%
3 16 100 51,8 51,8 0 0,00%
3 16 200 60,5 60,5 0 0,00%
3 16 400 66 66 0 0,00%
3 16 800 63,6 63,6 0 0,00%
3 32 100 65,5 65,5 0 0,00%
3 32 200 72,3 72,3 0 0,00%
3 32 400 64,4 64,4 0 0,00%
3 32 800 70,1 70,1 0 0,00%
Proyecto fin de Carrera 2014
126
ANEXO V
Código de la programación del problema Pm| |ΣUi para la heurística EDD&Greedy.
Proyecto fin de Carrera 2014
127
ANEXO VI
Código de la programación del problema Pm| |ΣUi para la heurística EDD&Conway.
Proyecto fin de Carrera 2014
128
ANEXO VII
Resultado de los valores medios de ΣUi para cada tipo de problema Pm||ΣUi según
sus variables, tanto para algoritmo Greedy como para algoritmo Conway, así como sus
diferencias porcentuales.
Carga Nmaq Ntrab ΣUi G media ΣUi C media Diferencia Dif. Porc.
1 4 25 11 11,8 0,8 7,27%
1 4 50 18,5 19,1 0,6 3,24%
1 4 100 33,2 34,1 0,9 2,71%
1 4 200 65,5 65,7 0,2 0,31%
1 4 400 126,1 126,2 0,1 0,08%
1 4 800 240,8 241,4 0,6 0,25%
1 8 50 21,1 22,3 1,2 5,69%
1 8 100 39 40,6 1,6 4,10%
1 8 200 65,7 67,3 1,6 2,44%
1 8 400 126,9 128,1 1,2 0,95%
1 8 800 249,1 250,4 1,3 0,52%
1 16 100 41,7 44,7 3 7,19%
1 16 200 75,2 78,7 3,5 4,65%
1 16 400 130,3 134,4 4,1 3,15%
1 16 800 251,2 254,3 3,1 1,23%
1 32 100 56,9 58,4 1,5 2,64%
1 32 200 83 90,3 7,3 8,80%
1 32 400 143,3 150,8 7,5 5,23%
1 32 800 261,2 267,8 6,6 2,53%
2 4 25 4,4 4,3 -0,1 -2,27%
2 4 50 5,4 6 0,6 11,11%
2 4 100 8,5 9 0,5 5,88%
2 4 200 10,4 10,8 0,4 3,85%
2 4 400 12,5 12,9 0,4 3,20%
2 4 800 19,8 20,3 0,5 2,53%
2 8 50 6,9 7,5 0,6 8,70%
2 8 100 10,7 11,7 1 9,35%
2 8 200 10,8 11,9 1,1 10,19%
2 8 400 12,7 13,7 1 7,87%
2 8 800 21,3 22,2 0,9 4,23%
2 16 100 13,2 15 1,8 13,64%
2 16 200 18 20,3 2,3 12,78%
2 16 400 21,7 24,1 2,4 11,06%
2 16 800 24,9 27,8 2,9 11,65%
Proyecto fin de Carrera 2014
129
2 32 100 28,8 31,2 2,4 8,33%
2 32 200 28,6 33 4,4 15,38%
2 32 400 29 34,4 5,4 18,62%
2 32 800 39,1 45,9 6,8 17,39%
3 4 25 1,7 1,7 0 0,00%
3 4 50 1,6 1,6 0 0,00%
3 4 100 1,1 1,2 0,1 9,09%
3 4 200 2,1 2,1 0 0,00%
3 4 400 2,1 2,1 0 0,00%
3 4 800 2,2 2,3 0,1 4,55%
3 8 50 2,6 2,6 0 0,00%
3 8 100 3,1 3,1 0 0,00%
3 8 200 3,7 3,8 0,1 2,70%
3 8 400 2,5 2,5 0 0,00%
3 8 800 2,9 2,9 0 0,00%
3 16 100 6,5 6,5 0 0,00%
3 16 200 6 6 0 0,00%
3 16 400 7 7 0 0,00%
3 16 800 6,1 6,1 0 0,00%
3 32 100 12,7 12,7 0 0,00%
3 32 200 13,2 13,2 0 0,00%
3 32 400 13,4 13,4 0 0,00%
3 32 800 13,7 13,7 0 0,00%
Proyecto fin de Carrera 2014
130
ANEXO VIII
Código de la programación del problema Qm||Lmax para la heurística EDD&Greedy.
Proyecto fin de Carrera 2014
131
Proyecto fin de Carrera 2014
132
ANEXO IX
Código de la programación del problema Qm||Lmax para la heurística EDD&Conway.
Proyecto fin de Carrera 2014
133
Proyecto fin de Carrera 2014
134
ANEXO X
Resultado de los valores medios de Lmax para cada tipo de problema Qm||Lmax
según sus variables, tanto para algoritmo Greedy como para algoritmo Conway, así
como sus diferencias porcentuales.
Carga Nmaq Ntrab LmG media LmC media Diferencia Porc
1 4 25 278,06 276,76 -1,3 -0,47%
1 4 50 498,51 492,14 -6,37 -1,28%
1 4 100 931,5 936,22 4,72 0,51%
1 4 200 1901,33 1902,9 1,57 0,08%
1 4 400 3706,85 3712,81 5,96 0,16%
1 4 800 7174,41 7182,33 7,92 0,11%
1 8 50 277,44 280,59 3,15 1,14%
1 8 100 541,96 548,15 6,19 1,14%
1 8 200 960,73 966,17 5,44 0,57%
1 8 400 1890,99 1898,2 7,21 0,38%
1 8 800 3757,03 3772,03 15 0,40%
1 16 100 301,89 308,17 6,28 2,08%
1 16 200 541,97 555,09 13,12 2,42%
1 16 400 984,48 1000,43 15,95 1,62%
1 16 800 1930,12 1946,5 16,38 0,85%
1 32 100 171,23 194,32 23,09 13,48%
1 32 200 306,2 310,82 4,62 1,51%
1 32 400 541,68 558,65 16,97 3,13%
1 32 800 1006,77 1027,44 20,67 2,05%
2 4 25 136 133,14 -2,86 -2,10%
2 4 50 217,2 222,98 5,78 2,66%
2 4 100 414,66 411,87 -2,79 -0,67%
2 4 200 710,39 711,27 0,88 0,12%
2 4 400 1213,57 1218,74 5,17 0,43%
2 4 800 2438,96 2432,27 -6,69 -0,27%
2 8 50 126,69 135,14 8,45 6,67%
2 8 100 222,04 223,94 1,9 0,86%
2 8 200 332,76 343,6 10,84 3,26%
2 8 400 634,73 639,37 4,64 0,73%
2 8 800 1295,4 1298,87 3,47 0,27%
2 16 100 145,44 153,2 7,76 5,34%
2 16 200 225,42 242,37 16,95 7,52%
2 16 400 374,82 392,2 17,38 4,64%
2 16 800 695,27 707,54 12,27 1,76%
2 32 100 99,19 117,74 18,55 18,70%
2 32 200 140,4 161,69 21,29 15,16%
Proyecto fin de Carrera 2014
135
2 32 400 222,98 240,42 17,44 7,82%
2 32 800 405,47 425,3 19,83 4,89%
3 4 25 43,96 45,11 1,15 2,62%
3 4 50 39,82 42,72 2,9 7,28%
3 4 100 37,3 42,7 5,4 14,48%
3 4 200 48,15 50,59 2,44 5,07%
3 4 400 68,38 71,8 3,42 5,00%
3 4 800 65,22 64,28 -0,94 -1,44%
3 8 50 45,4 50,25 4,85 10,68%
3 8 100 53,27 55,18 1,91 3,59%
3 8 200 56,96 60,1 3,14 5,51%
3 8 400 45,5 45 -0,5 -1,10%
3 8 800 50,7 51,86 1,16 2,29%
3 16 100 54,9 61,18 6,28 11,44%
3 16 200 61,96 62,6 0,64 1,03%
3 16 400 66,38 69,87 3,49 5,26%
3 16 800 63,6 65,26 1,66 2,61%
3 32 100 66,16 69,7 3,54 5,35%
3 32 200 72,3 77 4,7 6,50%
3 32 400 66,06 69,48 3,42 5,18%
3 32 800 70,1 74,9 4,8 6,85%
Proyecto fin de Carrera 2014
136
ANEXO XI
Código de la programación del problema Qm| |ΣUi para la heurística EDD&Greedy.
Proyecto fin de Carrera 2014
137
Proyecto fin de Carrera 2014
138
ANEXO XII
Código de la programación del problema Qm| |ΣUi para la heurística EDD&Conway.
Proyecto fin de Carrera 2014
139
Proyecto fin de Carrera 2014
140
ANEXO XIII
Resultado de los valores medios de ΣUi para cada tipo de problema Qm||ΣUi según
sus variables, tanto para algoritmo Greedy como para algoritmo Conway, así como sus
diferencias porcentuales.
Carga Nmaq Ntrab SUiG media SUiC media Diferencia Porc
1 4 25 12,6 13,2 0,6 4,76%
1 4 50 21,6 22,3 0,7 3,24%
1 4 100 39,6 40,3 0,7 1,77%
1 4 200 77,9 78,5 0,6 0,77%
1 4 400 150,8 151,5 0,7 0,46%
1 4 800 291,2 292 0,8 0,27%
1 8 50 23,9 25,5 1,6 6,69%
1 8 100 45,4 46,8 1,4 3,08%
1 8 200 78,5 80,1 1,6 2,04%
1 8 400 152,7 154,5 1,8 1,18%
1 8 800 300,7 302,1 1,4 0,47%
1 16 100 48 51,1 3,1 6,46%
1 16 200 89 92,8 3,8 4,27%
1 16 400 157,5 162,2 4,7 2,98%
1 16 800 307,8 311,2 3,4 1,10%
1 32 100 58,6 64,5 5,9 10,07%
1 32 200 95,1 103,6 8,5 8,94%
1 32 400 171,5 178 6,5 3,79%
1 32 800 317,6 325,3 7,7 2,42%
2 4 25 5,6 6,3 0,7 12,50%
2 4 50 8,6 9,2 0,6 6,98%
2 4 100 16,3 16,5 0,2 1,23%
2 4 200 25,9 26,2 0,3 1,16%
2 4 400 43,6 44 0,4 0,92%
2 4 800 85,8 86,2 0,4 0,47%
2 8 50 10 11,4 1,4 14,00%
2 8 100 17,6 19,6 2 11,36%
2 8 200 24,5 26 1,5 6,12%
2 8 400 45,1 46,6 1,5 3,33%
2 8 800 91,1 92,3 1,2 1,32%
2 16 100 20,6 24,2 3,6 17,48%
2 16 200 34,2 37,9 3,7 10,82%
2 16 400 54,1 58,1 4 7,39%
2 16 800 96,9 100,4 3,5 3,61%
2 32 100 31,8 39,6 7,8 24,53%
2 32 200 42,3 50,2 7,9 18,68%
Proyecto fin de Carrera 2014
141
2 32 400 63,7 71,3 7,6 11,93%
2 32 800 115,1 122,2 7,1 6,17%
3 4 25 1,8 2,1 0,3 16,67%
3 4 50 1,9 2,1 0,2 10,53%
3 4 100 1,5 1,7 0,2 13,33%
3 4 200 2,2 2,4 0,2 9,09%
3 4 400 2,5 2,9 0,4 16,00%
3 4 800 2,5 2,6 0,1 4,00%
3 8 50 2,8 3,5 0,7 25,00%
3 8 100 3,1 3,9 0,8 25,81%
3 8 200 3,9 4,4 0,5 12,82%
3 8 400 2,6 3 0,4 15,38%
3 8 800 2,9 3,6 0,7 24,14%
3 16 100 6,8 8,4 1,6 23,53%
3 16 200 6,1 7 0,9 14,75%
3 16 400 7,2 7,9 0,7 9,72%
3 16 800 6,1 6,7 0,6 9,84%
3 32 100 12,7 14,2 1,5 11,81%
3 32 200 13,2 15,1 1,9 14,39%
3 32 400 13,4 15,2 1,8 13,43%
3 32 800 13,7 15 1,3 9,49%
Proyecto fin de Carrera 2014
142
ANEXO XIV
Código de la programación del problema Pm| |ΣTi para la heurística Greedy.
Proyecto fin de Carrera 2014
143
ANEXO XV
Código de la programación del problema Pm| |ΣTi para la heurística Conway.
Proyecto fin de Carrera 2014
144
ANEXO XVI
Resultado de los valores medios de ΣTi para cada tipo de problema Pm||ΣTi según
sus variables, tanto para algoritmo Greedy como para algoritmo Conway, así como sus
diferencias porcentuales.
Carga Nmaq Ntrab LmG media LmC media Diferencia Porc
1 4 25 1812,3 1833,3 21 1,16%
1 4 50 5862,6 5902 39,4 0,67%
1 4 100 20277,4 20389,8 112,4 0,55%
1 4 200 80181 80368,3 187,3 0,23%
1 4 400 317051,8 317308 256,2 0,08%
1 4 800 1172155,3 1172782,7 627,4 0,05%
1 8 50 3396,1 3474,5 78,4 2,31%
1 8 100 13323,3 13489,8 166,5 1,25%
1 8 200 41049,4 41440,6 391,2 0,95%
1 8 400 159596,5 160345,2 748,7 0,47%
1 8 800 618317,5 619825,8 1508,3 0,24%
1 16 100 7152,2 7376,9 224,7 3,14%
1 16 200 24752,9 25270,5 517,6 2,09%
1 16 400 82751,9 83956,4 1204,5 1,46%
1 16 800 307701,4 310243 2541,6 0,83%
1 32 100 4685,9 4841,7 155,8 3,32%
1 32 200 13892,9 14409,3 516,4 3,72%
1 32 400 47239,3 48596,7 1357,4 2,87%
1 32 800 165461 168604,7 3143,7 1,90%
2 4 25 562,1 586,3 24,2 4,31%
2 4 50 1257,5 1356,3 98,8 7,86%
2 4 100 4221,4 4400,5 179,1 4,24%
2 4 200 11262,4 11585,8 323,4 2,87%
2 4 400 21990 22607,4 617,4 2,81%
2 4 800 86071,6 87354,3 1282,7 1,49%
2 8 50 887,9 1072,9 185 20,84%
2 8 100 2778,9 3111,9 333 11,98%
2 8 200 4593,8 5380,1 786,3 17,12%
2 8 400 8507,6 9785,7 1278,1 15,02%
2 8 800 35834,3 38759,9 2925,6 8,16%
2 16 100 1818,4 2329,3 510,9 28,10%
2 16 200 5437,3 6548,7 1111,4 20,44%
2 16 400 12052,7 14495,6 2442,9 20,27%
2 16 800 23217,4 27671,7 4454,3 19,19%
2 32 100 2158,5 2575,2 416,7 19,31%
2 32 200 3974,7 5145,5 1170,8 29,46%
Proyecto fin de Carrera 2014
145
2 32 400 7251,3 10264,6 3013,3 41,56%
2 32 800 23164 29522,8 6358,8 27,45%
3 4 25 68 73,5 5,5 8,09%
3 4 50 65,2 67,3 2,1 3,22%
3 4 100 55 63,8 8,8 16,00%
3 4 200 82 84,9 2,9 3,54%
3 4 400 178,2 198 19,8 11,11%
3 4 800 117,2 119,2 2 1,71%
3 8 50 83,1 98,3 15,2 18,29%
3 8 100 80,3 80,3 0 0,00%
3 8 200 149,7 154,3 4,6 3,07%
3 8 400 71,8 72,5 0,7 0,97%
3 8 800 76,1 86,5 10,4 13,67%
3 16 100 190,8 216,1 25,3 13,26%
3 16 200 186,7 194,9 8,2 4,39%
3 16 400 241,3 260,8 19,5 8,08%
3 16 800 187,6 191,7 4,1 2,19%
3 32 100 420,4 432,7 12,3 2,93%
3 32 200 454,7 478 23,3 5,12%
3 32 400 366 390,9 24,9 6,80%
3 32 800 423,3 436,1 12,8 3,02%
Proyecto fin de Carrera 2014
146
Anexo XVII
Extractos del código de la parte de Generación de los problemas en el programa Visual
Basic.