estudio de heurísticas para problemas de scheduling con...

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


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


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


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


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


vi


1

CAPÍTULO 1

INTRODUCCIÓN Y OBJETIVOS DEL PROYECTO


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):


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


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.


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.


6

CAPÍTULO 2

PROBLEMAS CON MÁQUINAS EN PARALELO


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.


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


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:


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.


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:


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


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

<=


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á


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.


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.


17

CAPÍTULO 3

MODELO Pm| |Lmax


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.


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


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.


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:


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


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:


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:


24



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:


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:


25


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:


26



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:


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:


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:


Dur. Total: 34

Maq. 3:

Trab. 11 Dur. 11; Trab. 18 Dur. 8; Trab. 13 Dur. 8;

Dur. Total: 27

Maq. 4:


Dur. Total: 25

Maq. 5:


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.


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


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:


29


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:


Dur. Total: 50

Maq. 2:


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.


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:


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:


Dur. Total: 15

Maq. 3:

Trab. 4 Dur. 15;

Dur. Total: 15

Maq. 4:


Dur. Total: 15


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:


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:


Dur. Total: 31

Maq. 2:


Dur. Total: 24

Maq. 3:


32


Dur. Total: 27

Maq. 4:


Dur. Total: 29

Maq. 5:


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.


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


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:


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:


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

.


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.


38

CAPÍTULO 4

MODELO Pm| |ΣUi


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.





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.


40




orden no decreciente de , es decir, de sus fechas de entrega, como hemos hecho

también para todos los problemas del caso de Lmax.





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



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:


41


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:


42


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:


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:


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


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:


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.


44




diferente.

Al igual que para la heurística Conway lo que debemos hacer en primer lugar es





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


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.


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



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.



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:


45


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:



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:


M1 3 1 5 1 6 24

M2 8 6 2 11

M3 2 8

M4 7 9 6 13

Ui 4


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:


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:


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


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:


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.


48




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.


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.



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.


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


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:


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:


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:


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:


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.


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.


54

CAPÍTULO 5

MODELO Qm| |Lmax


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.



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.


56


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.





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.


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:


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:


Dur. Total: 45

Maq. 2:


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


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:


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:


Dur. Total: 28

Maq. 4:


Dur. Total: 22,5

Maq. 1:


Dur. Total: 36


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:


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:


Dur. Total: 40,8

Maq. 1:


60


Dur. Total: 36

Maq. 4:


Dur. Total: 40,6

Maq. 5:


Dur. Total: 30

Maq. 3:


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.


61


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





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.



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.


C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo IX.










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.


62


siguiente forma:


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:


Dur. Total: 58,8

Maq. 1:


Dur. Total: 47

Maq. 3:



63

Dur. Total: 43,5

Lmax Conway: 24,8






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:


Dur. Total: 33

Maq. 4:


Dur. Total: 12


64

Maq. 2:


Dur. Total: 18

Maq. 3:


Dur. Total: 21

Lmax Conway: 9


pasar al tercer y último ejemplo de este bloque de Qm||Lmax, antes de ejecutar los

1140 ejemplos pertenecientes a este capítulo.




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.



Lmax Conway:


65

Maq. 4:


Dur. Total: 39,2

Maq. 3:


Dur. Total: 31,2

Maq. 5:


Dur. Total: 31,5

Maq. 1:


Dur. Total: 37

Maq. 2:


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.


66




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.







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





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.





muy o poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1


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:


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.



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.



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.


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.


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:



• 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.


71

CAPÍTULO 6

MODELO Qm| |ΣUi


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.





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.


73




orden no decreciente de , es decir, de sus fechas de entrega, como hemos hecho

también para todos los problemas del caso de Lmax.



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



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:


74


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:


Trab. 2, Trab. 7, Trab. 1, Trab. 9, Trab. 14,

Maq. 3: Dur. Total: 24

Maq. 2: Dur. Total: 27,6


75


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:


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:


Trab. 4,


76





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:


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


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:


Trab. 11, Trab. 9, Trab. 21,






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.


78




diferente.

Al igual que para la heurística Conway lo que debemos de hacer en primer lugar es





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.



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.


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



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.



código.


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:


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:


Trab. 2, Trab. 7, Trab. 1, Trab. 9, Trab. 14,




SumUisC: 5


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:


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:


Trab. 4, Trab. 6,




81



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:


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:


82

SumUiC:








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.


83




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.


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 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.



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


84

poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1 sería

muy comprimido y C3 poco comprimido.




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:


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:


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:


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,



Conway para este tipo de problemas, especialmente para trabajos de baja

compresión.






ampliamente mientras que los de alta compresión, C1, la van aumentando

levemente.


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.).


89

CAPÍTULO 7

MODELO Pm||ΣT i


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.



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.


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.


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.


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:


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:


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


93

Maq. 2:


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:


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:


Dur. Total: 20


94

Maq. 2:

Trab. 4 Dur. 15;

Dur. Total: 15

Maq. 4:


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:


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


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:


Dur. Total: 31

Maq. 4:


Dur. Total: 31

Maq. 1:


Dur. Total: 28

Maq. 3:


Dur. Total: 26

Maq. 2:


Dur. Total: 27


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.


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.


C+ en el programa Visual Basic, cuyo código se puede consultar en el Anexo XV.









98



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.


siguiente forma:


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:


Dur. Total: 43

Maq. 1:


Dur. Total: 36


99

Maq. 3:


Dur. Total: 46

Ti Conway: 49






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:


Dur. Total: 21


100

Maq. 1:


Dur. Total: 13

Maq. 2:


Dur. Total: 11

Maq. 4:


Dur. Total: 26

Ti Conway: 15


pasar al tercer y último ejemplo de este bloque antes de ejecutar los 1140 ejemplos

pertenecientes a este capítulo.




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


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.



Ti Conway:

Maq. 2:


Dur. Total: 30

Maq. 4:


Dur. Total: 30

Maq. 1:


Dur. Total: 28

Maq. 3:


Dur. Total: 24

Maq. 5:



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.


103




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.







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.



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.





muy o poco comprimidos que se encuentran los trabajos en estos problemas. Así, C1






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.



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.


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.



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,







107




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%.


108

CAPÍTULO 8

GENERACIÓN Y LECTURA


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.


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.


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


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.


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.


114

CAPÍTULO 9

CONCLUSIONES


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.


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.


117

CAPÍTULO 10

BIBLIOGRAFÍA


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)


119

CAPÍTULO 11

ANEXOS


120

ANEXO I

Código de la programación del problema Pm||Lmax para la heurística EDD&Greedy.


121

ANEXO II

Código de la programación del problema Pm||Lmax para la heurística EDD&Conway.


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:



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:



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


123

� Problema de cinco máquinas



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


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%


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%


126

ANEXO V

Código de la programación del problema Pm| |ΣUi para la heurística EDD&Greedy.


127

ANEXO VI

Código de la programación del problema Pm| |ΣUi para la heurística EDD&Conway.


128

ANEXO VII

Resultado de los valores medios de ΣUi para cada tipo de problema Pm||ΣUi según



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%


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%


130

ANEXO VIII

Código de la programación del problema Qm||Lmax para la heurística EDD&Greedy.


131


132

ANEXO IX

Código de la programación del problema Qm||Lmax para la heurística EDD&Conway.


133


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%


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%


136

ANEXO XI

Código de la programación del problema Qm| |ΣUi para la heurística EDD&Greedy.


137


138

ANEXO XII

Código de la programación del problema Qm| |ΣUi para la heurística EDD&Conway.


139


140

ANEXO XIII

Resultado de los valores medios de ΣUi para cada tipo de problema Qm||ΣUi según



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%


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%


142

ANEXO XIV

Código de la programación del problema Pm| |ΣTi para la heurística Greedy.


143

ANEXO XV

Código de la programación del problema Pm| |ΣTi para la heurística Conway.


144

ANEXO XVI

Resultado de los valores medios de ΣTi para cada tipo de problema Pm||ΣTi según



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%


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%


146

Anexo XVII

Extractos del código de la parte de Generación de los problemas en el programa Visual

Basic.

estudio de heurísticas para problemas de scheduling con...

Documents