anÁlisis y comparaciÓn de reglas de despacho para la...
TRANSCRIPT
0
Trabajo Fin de Carrera
Grado en Ingeniería de Organización Industrial
Dep. Organización Industrial y Gestión de
Empresas I
Escuela Técnica Superior de Ingeniería
Universidad de Sevilla
ANÁLISIS Y COMPARACIÓN DE
REGLAS DE DESPACHO PARA LA
PROGRAMACIÓN DE MÁQUINAS
PARALELAS NO RELACIONADAS
BAJO DIFERENTES OBJETIVOS
1
2
Trabajo Fin de Grado Ingeniería
de Organización Industrial.
TITULO
Análisis y comparación de reglas de despacho para la programación de máquinas
paralelas no relacionadas bajo diferentes objetivos.
Autor:
Carlos Romero Águila
Tutor:
Dr.Víctor Fernández-Viagas Escudero
Dep. de Organización Industrial y Gestión de Empresas I
Escuela Técnica Superior de Ingeniería
Universidad de Sevilla
Sevilla, 2017
3
4
Trabajo Fin de Grado: Título
Autor: Carlos Romero Águila
Tutor: Víctor Fernández-Viagas Escudero
El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los
siguientes miembros:
Presidente:
Vocales:
Secretario:
Acuerdan otorgarle la calificación de:
Sevilla, 2017
El Secretario del Tribunal
5
6
AGRADECIMIENTOS
Quisiera darle el agradecimiento más sincero a D. Víctor Fernández-Viagas Escudero, tutor
académico de este proyecto, por su gran amabilidad, y su excepcional atención y
orientación durante todo este Proyecto Fin de Grado.
También, me gustaría extender estas líneas de agradecimiento a mi familia, por su
constante e incondicional apoyo durante estos años de esfuerzo.
Gracias.
7
8
INDICE
1. SUMARIO DEL INFORME ........................................................................................................... 15
2. PRESENTACIÓN .......................................................................................................................... 16
3. DESCRIPCIÓN DEL PROBLEMA ................................................................................................... 19
NOTACIONES ..................................................................................................................... 19 3.1
DATOS DEL PROBLEMA ..................................................................................................... 20 3.2
OBJETIVOS DE OPTIMIZACION .......................................................................................... 21 3.3
3.3.1 REFERENTES A INSTANTES DE FINALIZACION .................................................................. 21
3.3.2 REFERENTES A FECHAS DE ENTREGA ............................................................................... 21
4. REGLAS DE DESPACHO .............................................................................................................. 23
5. METODOLOGÍA .......................................................................................................................... 30
INTRODUCCIÓN ................................................................................................................. 30 5.1
4.2 CODE::BLOCKS ......................................................................................................................... 30
GENERACIÓN DE LOS ESCENARIOS DE PARTIDA ............................................................... 31 5.2
5.2.1 ELEMENTOS Y CARACTERISTICAS .................................................................................... 31
5.2.2 FORMACIÓN DEL ESCENARIO ........................................................................................... 32
5.2.3 ELEMENTOS ADICIONALES DE CADA INSTANCIA ............................................................. 33
CREACIÓN DE LAS FUNCIONES. ......................................................................................... 35 5.3
5.3.1 CREACIÓN DE LAS FUNCION PRINCIPAL ........................................................................... 36
5.3.2 CREACIÓN DE LAS FUNCIONES OBJETIVO ........................................................................ 36
5.3.3 EJEMPLO DE FUNCIÓN OBJETIVO EN C ............................................................................ 37
5.3.4 CREACIÓN DE LAS FUNCIONES DE LAS REGLAS DE DESPACHO. ...................................... 38
5.3.5 CREACIÓN DE FUNCIONES AUXILIARES ............................................................................ 39
5.3.6 COMBINACIÓN DE LAS FUNCIONES PARA LA CREACIÓN DE ESCENARIOS ...................... 39
6. HEURÍSTICA NEH ....................................................................................................................... 42
GENERACIÓN DE LA HEURÍSTICA ...................................................................................... 42 6.1
EJEMPLO HEURÍSTICA NEH ................................................................................................ 43 6.2
CÓDIGO EN C DE LA HEURÍSTICA NEH ............................................................................... 45 6.3
7. RESULTADOS ............................................................................................................................. 48
FACTOR ARPD .................................................................................................................... 48 7.1
9
RESULTADOS PARA EL MAKESPAN .................................................................................... 49 7.2
RESULTADOS PARA LA TARDANZA TOTAL ......................................................................... 53 7.3
RESULTADOS PARA RETRASO TOTAL ................................................................................ 57 7.4
RESULTADOS PARA SUMATORIO DE LOS TIEMPOS DE FINALIZACION TOTAL .................. 61 7.5
RESULTADOS DE RETRASO MÁXIMO ................................................................................ 66 7.6
RESULTADOS PARA EL SUMATORIO DE TRABAJOS TARDÍOS ............................................ 70 7.7
8. CONCLUSIONES ......................................................................................................................... 75
9. BIBLIOGRAFÍA ............................................................................................................................ 79
10
11
INDICE DE TABLAS
TABLA 1: NOTACIONES DE PROGRAMACIÓN DE LA PRODUCCIÓN ..................................................................................... 20
TABLA 2: ARPD MAKESPAN - REGLAS DE DESPACHO DERIVADA DE LA SUMA DE TIEMPOS DE PROCESOS. ................................ 50
TABLA 3: ARPD MAKESPAN - REGLAS DE DESPACHO DERIVADA DEL TIEMPO MINIMO DE PROCESO PARA CADA TRABAJO. .......... 51
TABLA 4: ARPD MAKESPAN - REGLAS DE DESPACHO DERIVADA DE LAS FECHAS DE ENTREGA. ............................................... 51
TABLA 5: ARPD TARDANZA TOTAL - REGLAS DE DESPACHO DERIVADA DE LA SUMA DE TIEMPOS DE PROCESOS......................... 54
TABLA 6: ARPD TARDANZA TOTAL - REGLAS DE DESPACHO DERIVADA DEL TIEMPO MINIMO DE PROCESO PARA CADA TRABAJO. .. 55
TABLA 7: ARPD TARDANZA TOTAL - REGLAS DE DESPACHO DERIVADA DE LAS FECHAS DE ENTREGA. ...................................... 55
TABLA 8: ARPD RETRASO TOTAL - REGLAS DE DESPACHO DERIVADA DE LA SUMA DE TIEMPOS DE PROCESOS. .......................... 57
TABLA 9: ARPD RETRASO TOTAL - REGLAS DE DESPACHO DERIVADA DEL TIEMPO MÍNIMO DE PROCESO PARA CADA TRABAJO. .... 58
TABLA 10 : ARPD RETRASO TOTAL - REGLAS DE DESPACHO DERIVADAS DE LAS FECHAS DE ENTREGA. .................................... 59
TABLA 11: ARPD TIEMPO FINALIZACIÓN TOTAL - REGLAS DE DESPACHO DERIVADAS DE LA SUMA DE TIEMPOS DE PROCESOS. ..... 62
TABLA 12: ARPD TIEMPO FINALIZACIÓN TOTAL - REGLAS DE DESPACHO DERIVADAS DEL TIEMPO MINIMO DE PROCESO PARA CADA
TRABAJO. .................................................................................................................................................... 63
TABLA 13: ARPD TIEMPO FINALIZACIÓN TOTAL - REGLAS DE DESPACHO DERIVADAS DE LAS FECHAS DE ENTREGA. ................... 64
TABLA 14: ARPD RETRASO MÁXIMO - REGLAS DE DESPACHO DERIVADA DE LA SUMA DE TIEMPOS DE PROCESOS. .................... 66
TABLA 15: ARPD RETRASO MÁXIMO - REGLAS DE DESPACHO DERIVADA DEL TIEMPO MINIMO DE PROCESO PARA CADA TRABAJO.67
TABLA 16: ARPD RETRASO MÁXIMO - REGLAS DE DESPACHO DERIVADAS DE LAS FECHAS DE ENTREGA. .................................. 68
TABLA 17: ARPD SUMATORIO TRABAJOS TARDÍOS - REGLAS DE DESPACHO DERIVADAS DE LA SUMA DE TIEMPOS DE PROCESOS. . 70
12
TABLA 18: ARPD SUMATORIO TRABAJOS TARDÍOS - REGLAS DE DESPACHO DERIVADAS DEL TIEMPO MINIMO DE PROCESO PARA
CADA TRABAJO. ............................................................................................................................................ 71
TABLA 19:ARPD SUMATORIO TRABAJOS TARDÍOS - REGLAS DE DESPACHO DERIVADAS DE LAS FECHAS DE ENTREGA. ................. 72
TABLA 20: ARPD MEDIO DE CADA REGLA DE DESPACHO PARA CADA OBJETIVO. ................................................................. 77
TABLA 21: RANKING DE POSICION GLOBAL DE CADA REGLA DE DESPACHO. ....................................................................... 78
13
INDICE DE GRA FICAS
GRÁFICAS 1: COMPOSICIÓN DE LAS 24 REGLAS DE DESPACHO ........................................................................................ 38
GRÁFICAS 2: ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO MAKESPAN ............................................................... 52
GRÁFICAS 3:ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO TARDANZA TOTAL. ....................................................... 56
GRÁFICAS 4: ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO RETRASO TOTAL ......................................................... 60
GRÁFICAS 5: ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO SUMATORIO DE LOS TIEMPOS DE FINALIZACIÓN ................. 65
GRÁFICAS 6: ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO RETRASO MÁXIMO. ..................................................... 69
GRÁFICAS 7:ARPD PARA LAS 24 REGLAS DE DESPACHO - OBJETIVO SUMATORIO DE TRABAJOS TARDIOS................................. 73
INDICE DE ILUSTRACIONES
ILUSTRACIÓN 1: ESQUEMAS DE ELEMENTOS DE PROGRAMACIÓN DE LA PRODUCCIÓN .......................................................... 17
ILUSTRACIÓN 2: EVALUACIÓN DE REGLAS DE DESPACHO. ............................................................................................... 23
ILUSTRACIÓN 3: DISTRIBUCIÓN DE VALORES EN LAS REGLAS DE DESPACHO.. ...................................................................... 29
ILUSTRACIÓN 4: BUCLES DE FORMACIÓN DE LAS INSTANCIAS EN CODE::BLOCKS. ................................................................ 33
ILUSTRACIÓN 5: BUCLE DE FORMACIÓN DE FECHAS DE LAS FECHAS DE ENTREGA EN CODE::BLOCKS. ....................................... 35
ILUSTRACIÓN 6: FUNCIÓN DE TARDANZA TOTAL CREADA EN CODE::BLOCKS. ..................................................................... 37
ILUSTRACIÓN 7: ALGORITMO DE LA HEURÍSTICA NEH REALIZADO EN CODE::BLOCKS. ......................................................... 47
14
15
1. SUMARIO DEL INFORME
El presente Trabajo de Fin de Grado constituye un estudio enfocado a la programación de
la producción, más concretamente a un análisis completo y detallado de una serie de
reglas de despacho (las cuales nos permiten definir una priorización en el orden de
procesamiento de trabajos en una planta de producción cualquiera).
Por una parte, se crearán diferentes unos escenarios de partida, es decir, diferentes tipos
de plantas de producción con características variables, con el objetivo de hacer extensible
el estudio a diversos volúmenes de producción. Por otra parte, se crearán una serie de
objetivos de optimización en esas plantas, aplicándose cada una de estas reglas de
despacho en las distintas opciones de escenarios y de objetivos de optimización. Se
pretende analizar el comportamiento que tiene cada una de ellas y así poder concluir cual
se ajusta mejor a cada característica de plantas de producción y de objetivos de
optimización que pretenda esa planta en cuestión.
Lo resultados obtenidos para las reglas de despacho serán comparados con la heurística
NEH, la cual está comprobada como una de las heurísticas que mejor se comporta dentro
de la programación de la producción, y que por tanto estableceremos como nuestra
solución de referencia para cada uno de los objetivos de estudio.
Esta proximidad en cuanto a los resultados obtenidos de cada regla de despacho
(relacionada a un objetivo de optimización y a un escenario de partida) y la heurística NEH
se calculará mediante el indicador ARPD, el cual establece en porcentaje, el grado en que
el resultado de la regla de despacho se acerca o se aleja de la NEH, permitiendo también
comparar entre sí las distintas reglas de despacho objeto de estudio.
Gran parte del trabajo es realizado mediante programación en C, realizando numerosos
ensayos para cada una de las opciones de estudio lo que nos permite en conjunto realizar
un análisis claro que establezca una serie de conclusiones finales fundamentadas.
16
2. PRESENTACIO N
Hasta mediados del siglo XVIII eran los propios artesanos los que controlaban el proceso
productivo dentro de las empresas. Más tarde y debido a la revolución industrial, de la
producción artesanal se pasó a una producción con una economía industrial y
manufacturera, reemplazándose todos los recursos manuales por máquinas y empezando
a surgir la necesidad de la planificación y organización de la producción. Así, con un
volumen de la producción más elevado que en décadas anteriores debido a la reducción
de los tiempos de producción y los costes, se da comienzo a la producción en masa, cuyas
bases teóricas fueron asentadas por Frederic W. Taylor y Henry Ford.
Este modelo de producción tuvo mucho éxito en la época, logrando influir en el sistema
económico y haciendo que grandes empresas copiaran su forma de producir bienes
idénticos a gran escala.
No obstante, debido a una serie de acontecimientos tanto económicos como sociales,
alrededor de 1960, se produjo un cambio en el tipo de demanda existente hasta el
momento, hundiendo a multitud de grandes empresas que habían implantado este
modelo de producción en masa, y pasando a un modelo de demanda basado en productos
con ciertas variaciones. Es el caso de Toyota, con su fundador Sakichi Toyoda, que
implantó un sistema que permitía esta diversificación y abría el camino a un nuevo tipo de
mercado. Para poder llevar a cabo este tipo de producción Toyota tuvo que reducir al
máximo los costes por el uso excesivo de recursos, exceso de producción y de existencias,
basándose en una optimización continua y constante conocida como filosofía Kaizen.
Este cambio de filosofía, hizo modificar a la mayoría de empresas sus formas de
enfrentarse a la demanda, iniciándose un sistema de producción a menor escala y que
permitía ofrecer productos más diversos, naciendo con ello el lean Management.
Así, la tendencia actual en el mercado y por tanto en la producción industrial se basa en la
flexibilización del sistema productivo siendo la competitividad de las empresas desde
mediados del siglo XX hasta la actualidad un aspecto determinante para poder desarrollar
una actividad empresarial en un mundo cada vez más globalizado y cambiante, donde las
oportunidades y posibilidades de sacar adelante un determinado producto con garantías
en el mercado conlleva entre otros factores un uso eficiente de los recursos.
17
Entre estos recursos son de vital importancia las máquinas, donde las materias primas son
procesadas con idea de añadir un determinado valor al producto
Son muchos los aspectos que pueden influir a la hora de definir la organización de una
determinada empresa. Sin duda, un factor principal será la programación de la
producción, posterior al proceso de planeación de la misma.
La programación de la producción permite que los recursos existentes en una planta
puedan ser asignados de la forma más eficiente posible a las distintas tareas que se
requieren a lo largo del tiempo, teniendo en cuenta las principales características y el
escenario en el que se lleva a cabo.
Ésta a su vez, se apoya en un conjunto de métodos, herramientas y modelos que permiten
la toma de decisiones dentro de la empresa, estando estos tres elementos relacionados
entre sí y fuertemente influenciados por el contexto en el que se encuentra la
organización y por tanto en sus decisiones.
Es fundamental llegar a unas soluciones que permitan a la empresa dar un paso adelante
en cuanto a la productividad.
Ilustración 1: Esquemas de elementos que en conjunto dan lugar a la programación y control de la producción. J.M, Framiñan ,“Program. y control de la producción” Universidad de Sevilla.
18
Sin duda uno de esas soluciones por las que pasa una mejora dentro de la producción de
una compañía cualquiera, es establecer prioridades a la hora de realizar sus trabajos.
Cuando una planta de producción conoce sus objetivos reales, puede enfocar dichos
objetivos a optimización mediante diversos modelos o reglas que tiene a su alcance y que
debe saber enfocar para la mejora de esos objetivos.
En este trabajo nos centraremos en escenarios de máquinas paralelas, teniendo estas
tiempos de procesos para cada trabajo diferentes entre ellas y por tanto no teniendo
ningún tipo de relación entre sí. La elección de la máquina en la que se procesa un
determinado trabajo se determinará en función de aquella que tengo un menor tiempo de
proceso acumulado de entre todas las máquinas de la planta.
Además los trabajos que se procesarán tendrán unas fechas de entrega en la que el
trabajo debería estar finalizado para poder ser entregado al cliente, siendo varios los
objetivos de optimización de las distintas plantas de producción, los cuales explicaremos
detalladamente en el próximo capítulo. También plantearemos los escenarios teniendo en
cuenta que los trabajos para ser procesados sólo tienen que pasar por una de las múltiples
máquinas que existan dentro de la planta de producción, considerándose como finalizados
los procesos una vez terminen por una de las máquinas.
19
3. DESCRIPCIO N DEL PROBLEMA
En este capítulo trataremos de definir cuál es la descripción del problema de
programación de la producción de forma general pasando posteriormente a los aspectos
que queremos desarrollar de forma más concreta dentro de este campo, así como los
conceptos teóricos en los que se asienta, definiendo cada una de las diferentes
configuraciones productivas posibles.
El problema de la programación de trabajos en máquinas puede definirse como “la
asignación en el tiempo de los recursos disponibles de forma que satisfaga un conjunto de
criterios y/o restricciones. Se trata de secuenciar un conjunto de trabajos que han de ser
procesados en un conjunto de máquinas. Cada trabajo lleva asociado una secuencia de
operaciones y cada operación se realiza en una máquina concreta durante un periodo de
tiempo conocido.” (PINEDO, 2012).
NOTACIONES 3.1
En la programación de la producción debido a la multitud de términos de los que se hacen
uso para referirnos a los distintos conceptos que la envuelven, se emplean una notación
que permiten simplificar toda la información, permitiendo una mayor comprensión y
organización de lo que se pretende reflejar.
Esta notación referida a la programación de la producción, propuesta por R.L. Graham,
está divida en tres grupos principales, los cuales componen los modelos de programación
de la producción. Estos tres grandes grupos son:
α: Referida a las características de la máquina, y que en nuestro caso, como ya se
ha explicado anteriormente corresponde a máquinas paralelas, sin ningún tipo de
relación entre ellas.
β: Referida a las características de los trabajos, y que en nuestro caso tendrán
prioridad en el orden de procesamiento en función de las reglas de despacho que
apliquemos de las 24 que se van a emplear. Además cada trabajo tendrá una fecha
de entrega o fecha en la que el trabajo debe estar finalizado.
20
ϒ: Referida a las funciones objetivo que se pretende optimizar, y que en nuestro
caso se estudiarán seis objetivos distintos como veremos a continuación.
En cualquier problema de programación de la producción el número de máquinas
empleadas en el proceso como el número de trabajos se consideran finitos. Por tanto se
suele utilizar “n” para indicar el número de trabajos y “m” como el número de máquinas.
Cuando queremos referirnos a un trabajo en concreto se emplea el subíndice j, siendo i el
respectivo subíndice para referirnos a la máquina en la posición i-ésima, es decir:
Sea J= { } el conjunto de trabajos a realizar.
Sea M= { } el conjunto de máquinas donde se van a procesar los
distintos trabajos.
Como ya hemos explicado anteriormente, el trabajo se centrará en escenarios de
máquinas paralelas donde cada trabajo podrá ser procesado en cualquiera de las
máquinas disponibles.
NOTACIÓN
Número de trabajos en el sistema N
Número de máquinas en el sistema M
Trabajo concreto j
Máquina concreta i
Maquinas idénticas en paralelo Pm
Tiempo de proceso por máquina y trabajo
Tiempo de puesta a punto de máquina
Fecha de finalización de trabajo
Peso de importancia de trabajo
Tabla 1: Notaciones de Programación de la producción
DATOS DEL PROBLEMA 3.2
Tiempo de proceso ( ): Representa el tiempo de proceso del trabajo j en la maquina i. A
veces el subíndice i se puede omitir en caso de que el tiempo de proceso sea indiferente
de la maquina en la que se procese dicho trabajo.
21
(Fechas de entrega o Due date): Representa la fecha de finalización del trabajo, es
decir, la fecha acordada con el cliente de finalización del trabajo y entrega del mismo. Esta
fecha se puede vencer, pero normalmente suele conllevar algún tipo de penalización en el
acuerdo con el cliente.
OBJETIVOS DE OPTIMIZACION 3.3
Durante este estudio, dadas las reglas de despacho descritas en próximo capítulo y para
los distintos escenarios, buscaremos obtener los resultados en función de distintos
objetivos, es decir, las distintas metas que se pueden plantear en el escenario, para
concluir posteriormente cual regla de despacho resulta preferible u óptima, para cada uno
de los objetivos que vamos a describir.
3.3.1 REFERENTES A INSTANTES DE FINALIZACION
Makespan ( ): Finalización del último trabajo, y por tanto de todos. Es sin
duda uno de los objetivos principales respecto a la planificación de la
producción y su posterior programación.
{ }, siendo el tiempo de finalización de cada trabajo j.
Suma de tiempos de finalización ( ): Suma de los tiempos de finalización
de cada uno de los distintos trabajos.
3.3.2 REFERENTES A FECHAS DE ENTREGA
Retraso ( : Es la diferencia entre la fecha de entrega y la fecha de finalización del
trabajo. Un retraso positivo significaría que la fecha de finalización no ha superado
la fecha límite de entrega del mismo al cliente, al contrario, un retraso con signo
negativo supondría que el trabajo se ha finalizado con fecha posterior al de
entrega con la consiguiente posible sanción.
22
Para este retraso estableceremos dos objetivos de optimización:
Retraso total: Sumatorio del retraso de cada uno de los trabajos que
tengan que ser procesados:
Retraso máximo: Valor máximo del retraso de entre los retrasos de cada
uno de los trabajos que tengan que ser procesados.
Tardanza ( : Es el máximo en el intervalo entre 0 y el retraso positivo, es decir, la
tardanza será siempre mayor que 0. Se suele utilizar en casos en lo que podemos
tener penalizaciones por vencimiento de la fecha de entrega.
(
Trabajo tardío : Vale la unidad si la tardanza es mayor que 0, y 0 en caso de lo
contrario.
23
4. REGLAS DE DESPACHO
En este capítulo vamos a definir las distintas reglas de despacho de las cuales haremos uso
para el estudio. Éstas nos permiten definir las prioridades a la hora de ser procesadas
entre los distintos trabajos que nos encontremos en cualquier tipo de fábrica. Así, las
reglas de despacho se basan en datos simples del producto como pueden ser los tiempos
de procesamiento o las fechas de vencimiento o en combinaciones entre ellas, para
establecer a través de algunos de estos datos un orden en el procesamiento de los
distintos trabajos que tenga una fábrica.
Ilustración 2: Evaluación de reglas de despacho. Juan R. “Aplicación de las reglas de despacho”.
24
Para el presente estudio seguiremos el proceso de generación de reglas de despacho
propuesto por Framiñan et al. (2003). De esta forma vamos a partir de tres datos
principales, formando tres grandes grupos de reglas de despacho, a cada uno de los cuales
le aplicaremos 8 secuencias de combinación diferentes dando lugar a un total de 24 reglas
de despacho diferentes. Como veremos posteriormente estas reglas de despacho serán
sometidas todas y cada una de ellas a los objetivos de optimización, estableciéndose las
diferencias oportunas entre ellas, en función de su comportamiento,
Procedemos a explicar a continuación la creación de las 24 reglas de despacho:
Los tres grupos iniciales de los cuales vamos a partir son:
: Vector con la suma para cada uno de los trabajos del tiempo de
proceso en todas las maquinas en las que puede ser procesado.
Vector con la fecha de entrega correspondiente a cada uno de los trabajos.
: Vector con el tiempo mínimo de proceso para cada trabajo de entre
todas las maquinas en las que pueden ser procesados.
A partir de cada uno de estos 3 vectores (suma de tiempos de proceso para cada uno de
los trabajos, fechas de entrega, y tiempo mínimo de proceso para cada trabajo de entre
todas las máquinas) se obtendrán 8 distintas secuencias, resultado de distintas
alternativas, cada una de las cual utilizaremos como reglas de despacho y que se explican
a continuación.
Para simplificar la comprensión de cada alternativa se mostrará un ejemplo visual en cada
una de ellas, observando los movimientos que se realizan para su ordenación final:
Función Creciente: Disposición de los datos de la secuencia en orden creciente, es
decir, de menor a mayor.
Suponiendo los datos reflejados en el siguiente vector como la suma de tiempos
de proceso para cada trabajo de entre todas las máquinas en las que puede ser
procesado, la secuencia creciente de esos tiempos de proceso seria:
25
Función Decreciente: Disposición de los datos de la secuencia en orden
decreciente, es decir, de mayor a menor.
Suponiendo los datos reflejados en el siguiente vector como tiempos de proceso
para cada trabajo de entre todas las máquinas en las que puede ser procesado, la
secuencia decreciente de esos tiempos de proceso seria:
Función Valley: Esta regla de despacho se obtiene a partir de la función creciente
mediante una combinación donde el primer elemento se almacena en la primera
posición del nuevo vector; el segundo en la última posición del nuevo vector, el
tercer elemento en la segunda posición del nuevo vector, el cuarto elemento en la
penúltima posición, y así sucesivamente. Así, ordenamos los trabajos como un
“valle”, donde los valores más bajos se van a ir almacenando en la parte central
del nuevo vector y los valores más altos en los extremos.
Para obtener esta secuencia, previamente se ha tenido que realizar la función
creciente, a partir de la cual, se puede proceder a realizar la función Valley.
Suponiendo los datos reflejados en el siguiente vector como la suma de tiempos
de proceso ( ), la secuencia Valley obtenida a partir de la secuencia creciente
de esos tiempos de proceso seria:
26
Función Hill: Esta regla de despacho se obtiene a partir de la decreciente con la
misma función con la que se obtiene el vector Valley, únicamente que partimos
del vector inverso al creciente. Así, para obtener esta secuencia, previamente se
ha tenido que realizar la función decreciente, a partir de la cual, se puede
proceder a realizar la función Hill.
Por tanto, y al contrario que en el anterior vector, ordenamos los trabajos como
una “colina” donde los valores más altos se situarán en el centro mientras que en
los extremos tendremos los valores más bajos.
Suponiendo los datos reflejados en el siguiente vector como tiempos de proceso,
la secuencia Hill obtenida a partir de la secuencia decreciente de esos tiempos de
proceso seria:
Función HI/LOHI: Esta regla de despacho se obtiene también a partir de la
creciente mediante una función donde el primer elemento del vector de la
función creciente ocupa la primera posición del nuevo vector, el último elemento
ocupa la segunda posición del nuevo vector, el segundo dato del vector ocupa la
tercera posición del nuevo vector, y así sucesivamente. Es decir, vamos alternando
un primer valor inicial bajo seguido de un segundo valor alto y así de forma
continuada.
Suponiendo los datos reflejados en el siguiente vector como tiempos de proceso,
la secuencia HI/LOHI obtenida a partir de la secuencia creciente de esos tiempos
de proceso seria:
27
Función HI/HILO: Esta regla de despacho se obtiene a partir de la decreciente
mediante la misma función con la que se obtiene el vector de la función HI/LOHI
solo que en este caso partimos de un vector distinto, en este caso el decreciente.
Es decir, alternamos un primer valor alto seguido de uno bajo y así de forma
continuada.
Suponiendo los datos reflejados en el siguiente vector como tiempos de proceso,
la secuencia HI/HILO obtenida a partir de la secuencia decreciente de esos
tiempos de proceso seria:
Función LO/HILO (inversa de la HI/LOHI): Esta regla de despacho se obtiene a
partir de la HI/LOHI, haciendo la inversa de la misma, es decir, para llegar a esta
función previamente habrá que realizar la HI/LOHI.
Así, el primer número de ese vector ahora pasará a ser el último, el segundo
pasará a ser el penúltimo y así sucesivamente.
28
Función LO/LOHI (inversa de la HI/HILO): Esta regla de despacho se obtiene a
partir de la HI/HILO, haciendo la inversa de la misma, es decir, para llegar a esta
función previamente habrá que realizar la HI/HILO.
Así, el primer número de ese vector ahora pasará a ser el último, el segundo
pasará a ser el penúltimo y así sucesivamente.
En la Ilustración 3 podemos ver donde se “sitúan” los valores para cada una de las
secuencias anteriormente descritas.
Por una parte vemos como secuencias como la Creciente o la Decreciente tienen sus
valores elevados en la parte inicial y final respectivamente.
Por otro lado las secuencias Hill y Valley tienen sus valores más elevados y menores en la
parte central, respectivamente dando ese aspecto de colina y de valle anteriormente
descrito.
Por último podemos también observar como las últimas 4 secuencias descritas, la HI/LOHI,
la HI/HILO, y las respectivas inversas de ambas tienen sus valores de forma mucho más
distribuida a lo largo de la secuencia, apreciándose únicamente valores algo más elevados
o menores en la parte inicial y final de las secuencias, siendo no obstante distribuido de
forma mucho más uniforme que el resto.
29
Ilustración 3: Distribución de valores en las reglas de despacho. J.M.Framiñán (2003) “Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem”.
30
5. METODOLOGI A
INTRODUCCIÓN 5.1
En el presente documento se hace un estudio del comportamiento de las reglas de
despacho en la programación de los trabajos para la producción. Para ello se utilizará el
Code::Blocks el cual nos permitirá crear todas las funciones necesarias para desarrollar
nuestros escenarios de partida, al igual que aquellos objetivos a los cuales se quieren
llegar y las 24 reglas de despacho anteriormente descritas y que se someterán a todos los
objetivos de optimización planteados.
Una vez creados los distintos modelos de programación de la producción, así como los
distintos escenarios contemplados en el trabajo, los cuales veremos más detalladamente a
continuación, se ha procedido a estudiar los resultados trasladando los mismos a
Microsoft Excel, siendo este un software, que permite crear tablas, y calcular y analizar los
datos obtenidos.
Así, a través de las hojas de cálculo, debido a las utilidades descritas, que facilitan las
operaciones matemáticas de números, edición de fórmulas y la creación intuitiva y rápida
de tablas, nos facilitará reflejar los datos mediante gráficas visuales, explicando todo el
análisis y conclusión final del trabajo en el capítulo posterior de “Resultados” y de
“Conclusiones”.
4.2 CODE::BLOCKS
Como ya hemos indicado anteriormente, mediante el programa Code::Blocks hemos
planteado, desarrollado y ejecutado, unos escenarios objetos de estudio.
Este programa informático está formado por un conjunto de herramientas para el
desarrollo de programas en lenguaje C y C++. Dado que Code::Blocks es únicamente la
interfaz del entorno de desarrollo, existe la posibilidad de complementarlo con una gran
variedad de compiladores, usando en el presente estudio el compilador GCC, en su versión
MinGW.
31
A fin de facilitar la compresión del presente documento, únicamente se mostrará en el
mismo una parte muy reducida del código C elaborado para el estudio. El código completo
en C se adjunta en formato digital.
GENERACIÓN DE LOS ESCENARIOS DE PARTIDA 5.2
5.2.1 ELEMENTOS Y CARACTERISTICAS
Todos los escenarios donde se ejecutarán las distintas reglas de despacho y calcularán sus
objetivos, están formados por una serie de elementos que constituirán las distintas
fábricas con características concretas. Posteriormente, los resultados serán analizados,
obteniendo unas conclusiones en función de las características generales de las fábricas.
Así por tanto se crean en primer lugar una serie de instancias, las cuales estarán, formadas
por:
Número de trabajos:
Serán en número total de tareas que tenga que realizar la fábrica. Cada uno de estos
trabajos tendrá que ser asignado a una máquina para ser procesado tardando en cada
máquina un tiempo distinto en finalizarse. Es decir, un mismo trabajo T1 puede tardar
10s en ser procesado en una maquina M1 sin embargo puede tardar 20s en ser
procesado en una maquina distinta M2. Esto es debido a que, con objeto de hacer un
estudio que abarque el mayor número de posibilidades, las máquinas que conforman
una fábrica, no tienen que tener idénticas características y por tanto sus tiempos de
proceso, como ya hemos comentado pueden variar para un mismo trabajo.
También con objeto de abarcar el mayor intervalo posible de escenarios, como
variable de número de trabajos en las distintas fábricas se han dispuesto 4 opciones
posibles, siendo estas 50, 100, 200, 500 número de trabajos.
Número de máquinas:
Serán el número total de dispositivos que se encuentren en la fábrica para procesar
los distintos trabajos. Como ya hemos comentado, estas máquinas no serán iguales
unas a otras y por tanto sus características respecto a los tiempos de proceso variarán
entre unas u otras reflejando de manera más real los datos obtenidos.
32
En este caso, se han dispuesto de 3 opciones posibles de número de máquinas en las
fábricas que se van a estudiar, siendo estas de 5,10,20.
Factor R y factor T:
Estos dos factores son necesarios para limitar en ambos extremos las fechas de
entrega de cada trabajo. Así, estas fechas de entrega para cada trabajo serán acordes
a las características de este, principalmente del tiempo de proceso del trabajo,
haciendo también que el estudio sea más realista.
Para R los posibles valores que formarán un escenario serán 0.2, 0.6 y 1 y para T serán
de 0.2, 0.4 y 0.6.
5.2.2 FORMACIÓN DEL ESCENARIO
Estos elementos anteriormente descritos se combinarán entre ellos para asegurar la
creación de escenarios que incluyan todas las posibles opciones. Para asegurar esta
combinación entre los distintos elementos que conforman un escenario se realizará
dentro del code::Blocks un árbol de bucles incluyendo un bucle por cada elemento. Es
decir la programación para la creación de las instancias se iniciará con un bucle para el
número de trabajos, dentro de este bucle se incluirá otro bucle para el número de
máquinas y así sucesivamente hasta llegar a los cuatro bucles, uno dentro de otro,
asegurando que se cumplen todas las combinaciones posibles de estos elementos y por
tanto haciendo un estudio con gran variedad de escenarios lo que nos permitirá por una
parte ver cómo responden las distintas reglas de despacho a escenarios muy dispares y
además, concluir que regla es más favorable según las características que tenga la fábrica.
Además de estos 4 bucles se incluirán un quinto el cual tendrá únicamente la función de
repetir 5 veces para una misma instancia con sus características concretas todo el proceso
de desarrollo de las funciones objetivo combinándolas con las reglas de despacho como
veremos a continuación.
Esta repetición para un mismo escenario de todas las funciones objetivo y las respectivas
reglas de despacho es debido a que dentro de esos bucles se crearán características de
forma aleatoria como pueden ser el tiempo de proceso de los distintos trabajos en una
máquina y por tanto para hacer muestras y un estudio fiable deben realizarse varias
repeticiones para posteriormente hacer una media ponderada entre todos los resultados
permitiendo un análisis mucho más fiable.
33
A continuación, se refleja el inicio de la función principal “main” en la cual se pueden ver
el árbol de bucles inicial para la creación de las instancias, que nos permiten cada una de
estas con unas características concretas:
Ilustración 4: Bucles de formación de las instancias en Code::Blocks. Elaboración propia.
5.2.3 ELEMENTOS ADICIONALES DE CADA INSTANCIA
Cada instancia está formada por un número de máquinas, un número de trabajos a
realizar y unos factores de T y R concretos junto a una serie de características
imprescindibles que conforman en conjunto cada escenario determinado al cual se le
aplicarán las distintas funciones objetivo, combinadas con las reglas de despacho.
Estas características adicionales que conforman cada una de las instancias son:
34
Tiempo de proceso:
Como ya se ha explicado anteriormente está referido al tiempo que requiere cada
máquina para cada trabajo. Así cada máquina tiene un tiempo de proceso distinto
para cada uno de los trabajos y entre dos máquinas los tiempos de proceso varían.
Además, para cada fabrica estos tiempos también variarán, es decir, para la
primera fábrica, el tiempo de proceso del trabajo 1 en la máquina 1 será distinto
al tiempo de proceso del trabajo 1 en la maquina 1 para la segunda fábrica creada.
Estos tiempos de proceso se generarán de manera aleatoria dentro del árbol de
bucles que forman cada una de las instancias como podemos ver en la anterior
imagen en un intervalo uniforme de 1 a 100, mediante el uso de la función rand, la
cual nos transfiere ese carácter aleatorio.
Fechas de entrega:
Estos tiempos, los cuales son independientes para cada trabajo, corresponden a la
fecha límite en la que “deberían” estar acabados por cualquier decisión, bien sea,
por fecha de entrega a cliente, o fecha intermedia de finalización en un proceso
de fabricación cualquiera en el que se requiera terminar como muy tarde en esa
fecha para empezar otro proceso.
En muchas ocasiones, la fecha de finalización de los trabajos es posterior a la
fecha de entrega provocando principalmente tardanzas, uno de los objetivos que
se estudian en el presente trabajo, y que suponen uno de los principales puntos a
minimizar por las empresas, ya que implican mayores costes en la mayoría de los
casos.
En este caso las fechas de entrega se hicieron mediante un pequeño algoritmo
que contiene entre otros los factores T y R, lo cual nos permite crear unas fechas
de entrega coherentes con el escenario creado y las funciones objetivo a usar en
cada momento.
El algoritmo es el siguiente:
35
lustración 5: Bucle de formación de fechas de las fechas de entrega en Code::Blocks. Elaboración propia.
Dónde:
o VecT[t] y VecR[r], corresponden a los vectores T y R respectivamente
antes explicados.
o Parte, es una posible cota inferior del posible valor del objetivo que
vayamos a calcular (makespan, tardanza,…).En este caso puesto que
ese objetivo variará puesto que se analizarán varios de ellos, se ha
optado por tomar como cota inferior la suma de los tiempos de
proceso mínimos (es decir, el menor tiempo de proceso de un trabajo
en todas las máquinas) y dividiendo la suma esos tiempos entre el
número de máquinas que tenga ese escenario concreto.
o NúmeroAleatorio, es un número decimal aleatorio entre 0 y 1.
o Nearest, es el número entero inferior del creado en la variable
dueDate.
Aún con este algoritmo en algunos casos donde las fechas de entrega sean ligeramente
inferiores a 0. En estos casos se ha creado esta fecha de entrega como 0.
CREACIÓN DE LAS FUNCIONES. 5.3
Para poder llegar a los distintos objetivos que se plantean en el presente trabajo, la
programación se debe de hacer de forma parcial.
36
Estas distintas divisiones que componen en conjunto toda la parte de programación del
presente trabajo se denominan funciones, las cuales se pueden crear por separado para
posteriormente hacer un uso combinado de todas ellas que nos lleve como punto final a
nuestro objetivo.
Así por tanto tendremos una función principal en la cual se crearán las distintas fabricas
(asignándole sus distintos elementos mediante los bucles que hemos explicado
anteriormente) y en la cual, también, iremos nombrando al resto de funciones creadas de
forma anexa a esta, con la idea de poder ir combinándolas como veremos más adelante.
5.3.1 CREACIÓN DE LAS FUNCION PRINCIPAL
En esta función principal se han definido numerosos parámetros, tales como números de
trabajos, números de máquinas, tiempos de proceso en cada máquina para cada trabajo,
fechas de entrega, de los cuales vamos a explicar detalladamente y uno por uno a
continuación cómo se han obtenido cada uno de esos datos para así poder crear los
distintos escenarios a partir de los cuales se ha hecho el presente estudio.
5.3.2 CREACIÓN DE LAS FUNCIONES OBJETIVO
Cada una de las funciones objetivo se han ejecutado para cada escenario. Estas funciones
creadas en Code::Blocks reciben toda la información de ese escenario concreto para
posteriormente calcular el objetivo para el cual ha sido creada. Es decir, por ejemplo, se
ha creado una función de cálculo de la tardanza, en un escenario concreto. Este escenario
se compone de un número de trabajos que necesitan ser procesados, un número de
máquinas para procesar dichos trabajos, unas fechas de entrega y unas reglas de
despacho que determinan el método o secuencia para procesar estos trabajos. Toda esta
información se le aporta a cada uno de los objetivos a través de las funciones creadas y
mediante un algoritmo calculamos el objetivo deseado.
Así pues, se ha creado una función en C dentro del programa, para cada uno de los
objetivos que se han querido reflejar en el presente trabajo.
37
5.3.3 EJEMPLO DE FUNCIÓN OBJETIVO EN C
A continuación reflejamos una de las funciones objetivo realizadas en la programación
para su posterior estudio mediante las reglas de despacho y la heurística NEH, en concreto
la función objetivo de la tardanza total:
Ilustración 6: Función de tardanza total creada en Code::Blocks. Elaboración propia.
En este caso como en la mayoría del resto se puede observar como la función objetivo a
su vez se nutre de otra serie de funciones auxiliares que permiten hacer la construcción de
la misma algo más sencilla permitiendo que algunos de los pasos realizados puedan servir
para varias de ellas.
38
5.3.4 CREACIÓN DE LAS FUNCIONES DE LAS REGLAS DE DESPACHO.
Como ya se ha descrito en el capítulo 4 del trabajo, se han tenido en cuenta 24 reglas de
despacho distintas para nuestro estudio con el objetivo de ver el comportamiento
respecto a cada escenario.
Estas 24 reglas de despacho se articulan respecto a tres vectores iniciales distintos como
ya se ha explicado anteriormente:
1. El sumatorio para cada trabajo de los tiempos de proceso de todas las maquinas en
las que puede ser procesado.
2. Las fechas de entrega de cada trabajo.
3. El tiempo mínimo para cada trabajo de entre todas las maquinas en las que puede
ser procesado.
Así, a la hora de desarrollar las reglas de despacho en el programa se han hecho 8
funciones que sirven indistintamente para cada una de las 3 secuencias y que permite
recibir cualquier secuencia como información para posteriormente obtener mediante el
algoritmo la regla de despacho deseada, así como el número de trabajos a procesar y el
número de máquinas presentes en cada escenario concreto.
Gráficas 1: Composición de las 24 reglas de despacho. Elaboración propia.
0
1
2
3
4
5
6
7
8
9
Sec. ∑_j Pij Sec. Dj Sec. Min_i Pij
Inversa HI/HILO
HI/HILO
Inversa HI/LOH1
HI/LOH1
Hill
Valley
Decreciente
Creciente
39
Como vemos en la tabla se han creado 8 algoritmos para la creación de las reglas de
despacho, que aplicadas a las tres secuencias distintas dan el total de las 24 reglas de
despacho inicialmente citadas.
5.3.5 CREACIÓN DE FUNCIONES AUXILIARES
Además de todas las funciones anteriormente descritas se han realizado otras que, si bien
no son tan importantes, o incluso se podría haber prescindido de algunas de ellas, han
servido para facilitar y agilizar todo el trabajo tanto de creación del resto como de otras
partes del trabajo.
Algunas de estas funciones son:
Función de orden creciente: Ésta funciones nos ha permitido, mediante entrada de
información como número de trabajos, y una secuencia de entrada en forma de vector,
ordenar el mismo de forma creciente
Función de orden decreciente: Al igual que la anterior, pero en este caso la secuencia de
entrada que se recibe, se ordena de forma decreciente.
Función de números aleatorios: Función usada para generar números aleatorios dentro de
un intervalo concreto, para algoritmos como en la creación de fechas de entrega.
5.3.6 COMBINACIÓN DE LAS FUNCIONES PARA LA CREACIÓN DE ESCENARIOS
Todo el trabajo de programación realizado ha permitido obtener los resultados esperados
a través de una combinación de todas estas funciones anteriormente descritas. El
procedimiento realizado dentro de la función principal, para todos los objetivos, con cada
una de las reglas de despacho y en todas las instancias ha sido el siguiente:
1. En primer lugar, la creación del árbol de bucles ya descrito anteriormente que
nos va creando las distintas fabricas (con sus elementos concretos). Para cada
fábrica concreta se crean los tiempos de proceso de las máquinas y las fechas de
40
entrega de los trabajos acordes al objetivo y a los tiempos de proceso que se le
asignen a cada trabajo.
Así, obtenemos todos los posibles escenarios combinando las distintas
características que los componen asegurando un estudio amplio y variado que
nos permite sacar un mayor número de conclusiones.
2. Para cada una de las fábricas dentro del árbol de bucles se ejecuta una regla de
despacho. Así, al nombrar la función, esta se ejecuta, ordenándose los trabajos
de la fábrica en función de la misma. Esta regla de despacho tendrá como punto
de partida uno de los tres vectores que forman los tres grandes grupos de los
cuales derivan las reglas de despacho, la suma de tiempos de proceso para cada
trabajo de entre todas las máquinas en las que puede ser procesado, el tiempo
mínimo de proceso para cada trabajo de entre todas las máquinas en las que
puede ser procesados o las fechas de entrega de cada trabajo.
3. Una vez los trabajos están ordenados atendiendo a la regla de despacho en
concreto que se desea analizar, el siguiente paso sería calcular uno de los
objetivos. Así al igual que con la regla de despacho, se llama a la función del
objetivo de optimización que se quiere calcular, a la cual le pasaremos como
secuencia de trabajos la anteriormente calculada en el punto 2 a través de la
regla de despacho. Por lo tanto este objetivo de optimización se irá calculando,
procesando los trabajos en el orden establecido por la regla de despacho.
4. Por otra parte para el posterior análisis que se hace de todo los datos que se
obtienen del Code::Blocks, se nombra también la función de la Heurística NEH
que posteriormente explicamos de forma especial, pues se trata de un algoritmo
que nos va a permitir obtener a partir de una secuencia inicial dada, y mediante
distintas iteraciones, un resultado que aunque no tiene por qué ser óptimo si es
una buena solución ante el objetivo con el que queremos trabajar. Así, teniendo
por una parte el resultado obtenido mediante una regla de despacho cualquiera
y un objetivo de optimización concreto, y por otra parte el resultado para este
objetivo de optimización a través de la heurística NEH, lo siguiente será ver
cuánto se aproxima la regla de despacho a esta heurística, y por tanto poder
41
establecer el buen o mal resultado que nos proporciona para cada uno de los
objetivos descritos anteriormente.
42
6. HEURI STICA NEH
GENERACIÓN DE LA HEURÍSTICA 6.1
Una de las principales conclusiones que se pretenden extraer de este trabajo es cuánto de
buenas son cada una de las reglas de despacho para los distintos objetivos planteados.
Este análisis sería imposible de plantear, sin saber cómo de buenos pueden llegar a ser las
secuencias en cada objetivo, es decir sin saber cuál es el óptimo para cada objetivo o en su
defecto una aproximación a este, con el cual poder comparar el resultado obtenido para la
función objetivo con cada una de las reglas de despacho.
En este caso, utilizaremos la heurística NEH, planteada por M. Nawaz, Jr. E. E. Enscore, y l.
Ham, en el artículo “A Heuristic Algorithm for the m-Machine, n-Job Flow- shop Sequencing Problem”, para obtener soluciones aproximadas y dado que el estudio planteado emplea” variables con rangos elevados, como puede ser el caso de escenarios donde el número de trabajos es de 500 (a fin de representar entornos de trabajo reales), realizándose a su vez numerosas repeticiones del mismo, obtener el óptimo resulta imposible en tiempos razonables. Esta heurística NEH tiene dentro de la programación de la producción y en concreto
dentro del “scheduling” una muy buena aceptación que sin llegar a la solución óptima del
problema que se está planteando, se obtiene una secuencia de prioridad de trabajos, y
por tanto una solución aproximada, que se acerca a este valor del óptimo y que nos
permite tomar dichas soluciones como soluciones sobresalientes con las que comparar los
distintos resultados obtenidos mediante las secuencias creadas por las reglas de despacho
objeto de estudio en el presente trabajo.
Así, esta heurística se construye en diversos pasos:
Se realiza el sumatorio para cada trabajo de todos sus tiempos de proceso en cada
máquina, obteniendo por tanto para cada trabajo un tiempo.
∑
43
Estos tiempos se ordenan de forma decreciente. Es decir, aquel trabajo cuyo sumatorio de
tiempos sea mayor será el primero y así sucesivamente obteniendo la secuencia de
trabajos de forma descendente.
Una vez ordenados, se empieza con el proceso de prueba de la heurística a través de dicha
secuencia. Se empieza con una secuencia parcial inicial consistente únicamente en el
primer trabajo de dicha secuencia (k=1). A partir de ahí, para k=2,…,n se considera la
secuencia parcial anterior como determinada (Nº de trabajos= k-1) y se empieza a calcular
la función objetivo de las k subsecuencias (de k trabajos) insertando el trabajo k-ésimo en
todas las posiciones posibles de la subsecuencia k-1, eligiendo la de mejor valor para el
objetivo de entre todas ellas. La secuencia final en la iteración n es la solución de la
heurística NEH.
EJEMPLO HEURÍSTICA NEH 6.2
Para entender el procedimiento de la creación de esta heurística se procede a
continuación a la realización de un ejercicio ejemplo paso a paso.
Consideremos los siguientes elementos de una fábrica:
Sea J= 3, el número de trabajos a realizar.
Sea M=2, el número de máquinas en la fábrica.
Sean , , , , , , el tiempo de proceso del
trabajo j en la maquina i.
Se realizan los pasos descritos anteriormente:
1. Siendo ; .
2. Por tanto, el orden decreciente de los sería > > -> {1,3,2}.
3. Por último, se realiza la heurística teniendo en cuenta un objetivo. En este caso
será minimizar el Makespan (definido en el punto 2.3 Objetivos de optimización).
44
También hay que tener en cuenta que, para este trabajo, el uso de las máquinas se
hace derivando los trabajos a aquella máquina menos saturada, es decir, los
trabajos se irán adjudicando a aquella maquina cuyo tiempo de finalización de los
trabajos ya adjudicados sea menor.
Para la primera iteración k=1 se extrae únicamente el primer trabajo de la
secuencia decreciente del paso 2, es decir, esta primera secuencia estaría
formada únicamente por el trabajo 1 -> {1}.
Para la segunda iteración k=2 se combina la secuencia obtenida de la primera
iteración con el trabajo 3, insertando este trabajo en tantas posiciones como
sea posible de la secuencia de la iteración.
Por tanto, existe dos secuencias a analizar: {1,3} y {3,1}. En el primer caso J1
sería realizado en la M1 siendo el tiempo de proceso 5 y J3 seria realizado en la
M2 siendo el tiempo de proceso 1. Por tanto, el Makespan con esta secuencia
seria de 5.
En cambio, con la segunda secuencia el J3 seria realizado en la M1 siendo el
tiempo de proceso 4 y el J1 sería realizado en la M2 siendo el tiempo de
proceso 3. Por tanto, el Makespam sería de 4 y al mejorar la otra opción de
esta segunda iteración nos quedaríamos con esta secuencia {3,1}.
Para la tercera iteración k=3 se combina la secuencia obtenida de la iteración 2,
con el último trabajo de la secuencia decreciente, el 2, insertando este trabajo
en tantas posiciones como sea posible de la secuencia de la iteración.
Por tanto, ahora existen tres secuencias posibles: {2,3,1}, {3,2,1}, {3,1,2}. En el
primer caso J2 seria realizado en M1 con tiempo de proceso de 1, J3 sería
realizado en M2 con tiempo de proceso 1 y J1 seria realizado en M1 con tiempo
de proceso 5. Por tanto, el Makespan de esta secuencia sería de 6.
Realizando este mismo proceso para la secuencia {3,2,1} con un resultado de
Makespan de 5 y {3,1,2} con un resultado del Makespan de 5, concluiríamos
que las dos últimas secuencias serían la solución de la heurística NEH para este
ejercicio puesto que con ambas se obtiene el mismo resultado y son mejores
que la primera secuencia de esta última iteración.
45
CÓDIGO EN C DE LA HEURÍSTICA NEH 6.3
A continuación se expone la programación realizada para la heurística NEH, la cual es
realmente importante en el estudio como ya se ha explicado anteriormente pues nos
permite estimar una buena solución a los objetivos y nos permite a su vez comparar el
conjunto de reglas de despacho expuestas.
En este caso en concreto se está calculando para el objetivo suma de tiempos de
finalización (Total completion time):
46
47
Ilustración 7: Algoritmo de la heurística NEH realizado en Code::Blocks. Elaboración propia.
48
7. RESULTADOS
En este apartado presentaremos los resultados obtenidos, analizando cómo funcionan las
distintas reglas de despacho para cada una de las funciones objetivo, estableciendo
posteriormente una comparación entre ellas en función de lo favorables que sea el uso de
cada una de ellas en función del objetivo que se tenga en la fábrica. Además, dentro de
cada uno de los objetivos estableceremos diferencias en función de las características de
los escenarios planteados, es decir, según el número de trabajos y el número de máquinas
que presentan estos y también la influencia que hacen tanto el factor T y el factor R
empleados en la creación de las fechas de entrega.
En resumen, se hará un análisis exhaustivo de todos los resultados obtenidos de la
programación realizada, intentando a su vez combinar las distintas variables que forman
parte de cada uno de los escenarios, para obtener así, un mayor número de conclusiones
que sean realmente útiles.
Por tanto, para cada objetivo, se presentarán tres tablas, cada una de las cuales
pertenecientes a los tres grandes grupos en los que se engloban las reglas de despacho ya
explicados anteriormente, siendo estos, la suma de los tiempos para cada uno de los
trabajos de todas las maquinas en las que pueden ser procesados, el tiempo mínimo de
cada trabajo de entre todas las máquinas en que puede ser procesado y las fechas de
entrega, teniendo cada grupo 8 reglas de despacho, dando lugar a las 24 reglas de
despacho totales objeto de estudio.
En cada una de estas tablas se mostrarán los valores de ARPD obtenidos en cada uno de
los posibles escenarios creados para el trabajo.
Además para cada objetivo se creará un gráfico que mostrará los resultados obtenidos a
fin de poder establecer diferencias entre las 24 reglas de despacho.
FACTOR ARPD 7.1
49
Como ya hemos comentado anteriormente, el principal objetivo pasa por comparar y
analizar cada regla de despacho y saber funcionan estas respecto a cada función objetivo.
Por una parte, tenemos el valor NEH de cada función objetivo, es decir una aproximación
al óptimo de este, y por otro lado, tenemos el valor de cada regla de despacho para cada
función objetivo. Ahora tenemos que saber cuánto se acerca ese valor calculado para cada
regla de despacho al resultado de la heurística NEH, pudiendo concluir así que cuanto más
se acerque a ese valor, mejor se comportará dicha regla de despacho para ese objetivo y
permitiendo además establecer diferencias entre las reglas de despacho.
Para establecer esta aproximación entre ambos valores haremos uso del factor ARPD, el
cual simplemente es un porcentaje de dicha aproximación y el cual se calcula:
Siendo:
FO: El valor de la función objetivo para una regla de despacho concreta, y con unas
características concretas del escenario objeto de estudio tales como N.º trabajos, N.º
máquinas,..
NEH: El valor aproximado al óptimo de la función.
RESULTADOS PARA EL MAKESPAN 7.2
Analizamos este primer objetivo, el makespan, es decir, el tiempo de finalización del
último trabajo en ser procesado, empezando por las reglas de despacho derivadas de la
suma de tiempos de proceso para cada trabajo de todas las máquinas, siendo los
resultados obtenidos, los siguientes:
50
Tabla 2: ARPD Makespan - Reglas de despacho derivada de la suma de tiempos de procesos ( ).
En este caso es visible la igualdad en los resultados dentro de las distintas reglas de
despacho situándose el ARPD en un rango de (63.01,65.06) siendo así la diferencia
máxima de 2 puntos.
Como primera opción, siendo la que más se acerca a la heurística NEH tendríamos la
Secuencia Valley, prácticamente igualada con la función Decreciente, por otro lado, como
último lugar se situaría la función Hill, la cual con un ARPD=65,05 estaría más alejada de la
heurística NEH.
Analizamos ahora las reglas de despacho derivadas del tiempo mínimo para cada trabajo
de entre todas las máquinas en las que puede ser procesado:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 71,09 73,95 71,67 71,28 73,34 73,57 73,43 73,85
50 10 69,59 72,52 73,82 71,33 73,65 71,60 75,16 71,73
50 20 47,65 52,44 55,85 46,81 52,21 49,06 55,66 50,38
100 5 69,97 72,02 73,05 69,56 71,03 72,01 71,99 72,31
100 10 69,48 71,42 72,56 70,28 72,49 72,24 72,93 72,74
100 20 55,19 56,39 55,43 53,27 56,65 52,91 56,20 57,02
200 5 67,70 69,26 69,23 66,27 67,61 68,26 69,24 69,16
200 10 65,71 66,32 67,36 67,85 67,41 66,51 68,06 67,18
200 20 55,21 55,75 54,44 54,54 55,24 54,28 55,28 55,50
500 5 65,51 66,48 67,24 65,49 65,82 65,92 65,70 65,91
500 10 63,76 64,25 63,79 64,04 64,59 62,67 55,78 62,29
500 20 55,75 56,25 56,23 55,36 56,63 57,12 55,78 56,00
63,05 64,75 65,06 63,01 64,72 63,85 64,60 64,51
REGLAS DE DESPACHO
Suma de tiempos para cada trabajo de todas las maquinasN.º
TRABAJOS
N.º
MAQUINAS
Media
51
Tabla 3: ARPD Makespan - Reglas de despacho derivada del tiempo minimo de proceso para cada trabajo
( ).
Para este grupo de reglas de despacho el rango del ARPD está situado entre (63.32,64.66),
lo que muestran de forma aún más clara la igualdad dentro de las distintas reglas de
despacho para este objetivo. Como mejor resultado estaría el obtenido mediante la
HI/HILO inversa mientras que el peor resultado sería el de la regla de despacho Hill.
Analizamos por último el grupo de las reglas de despacho derivadas de las fechas de
entrega:
Tabla 4: ARPD Makespan - Reglas de despacho derivada de las fechas de entrega ( ).
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 71,24 73,00 73,68 74,13 74,13 71,68 74,68 75,08
50 10 71,95 70,11 74,24 73,60 70,47 70,09 73,34 74,95
50 20 52,71 48,43 50,18 52,02 48,89 50,05 48,51 46,86
100 5 72,70 71,80 70,53 73,20 71,96 73,20 70,92 73,65
100 10 72,37 70,77 71,28 69,93 70,70 72,33 69,41 70,73
100 20 55,21 55,04 56,13 55,90 58,74 57,01 54,93 54,65
200 5 67,69 68,38 70,84 68,96 68,63 69,64 69,02 68,84
200 10 68,12 68,59 68,86 67,65 67,61 66,83 66,57 66,24
200 20 56,80 55,07 54,96 53,27 55,49 56,39 55,49 56,96
500 5 65,69 66,29 66,20 66,13 65,76 65,92 66,57 65,07
500 10 62,78 63,12 63,52 64,29 64,00 64,45 55,20 63,80
500 20 56,85 55,90 55,47 56,24 55,50 55,11 55,20 56,13
64,51 63,87 64,66 64,61 64,32 64,39 63,32 64,41
N.º
TRABAJOS
REGLAS DE DESPACHO
Tiempo minimo para cada trabajo de entre todas las maquinas N.º
MAQUINAS
Media
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 68,47 72,48 73,51 77,99 71,21 73,91 72,65 71,01
50 10 72,72 72,91 74,26 73,24 71,91 69,55 66,83 71,65
50 20 48,87 49,47 51,22 51,51 54,00 50,43 50,31 52,12
100 5 70,92 72,64 70,76 70,64 69,50 72,05 71,39 71,47
100 10 70,42 70,72 69,58 69,36 72,69 71,07 71,05 71,49
100 20 58,38 55,70 54,11 55,54 54,97 54,80 54,34 53,51
200 5 69,42 67,89 68,20 70,30 67,80 67,90 67,79 68,06
200 10 67,46 67,54 66,66 67,39 66,70 67,50 66,51 66,96
200 20 55,15 54,24 55,07 55,33 54,41 54,02 53,58 55,40
500 5 66,00 65,65 65,55 65,32 66,40 66,81 65,40 66,01
500 10 62,92 64,22 62,93 64,14 64,17 63,44 55,37 63,00
500 20 55,86 55,89 57,20 54,96 55,70 56,78 55,37 56,67
63,88 64,11 64,09 64,64 64,12 64,02 62,55 63,95
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Fechas de entrega para cada trabajo
Media
52
Para estas 8 reglas de despacho los resultados obtenidos varían en un rango de
(62.55,64.64). El mejor resultado se obtendría con la regla de despacho HI/HILO inversa,
mientras el más alejado del resultado obtenido por la heurística NEH sería el de Valley.
Gráficas 2: ARPD para las 24 reglas de despacho - Objetivo Makespan
61,00 62,00 63,00 64,00 65,00 66,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.Su
ma
de
tie
mp
os
par
a ca
da
trab
ajo
de
tod
as la
s m
aqu
inas
Tie
mp
o m
inim
o p
ara
cad
a tr
abaj
od
e e
ntr
e t
od
as la
s m
aqu
inas
Fech
as d
e e
ntr
ega
par
a ca
da
trab
ajo
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
53
Por tanto, podemos destacar que las reglas de despacho más favorables dentro de las 24
reglas de despacho analizadas en este trabajo para este objetivo serian:
HI/HILO inversa derivada de las fechas de entrega
Valley derivada de la suma de tiempos de proceso para cada trabajo de entre
todas las maquinas en las que puede ser procesado.
Decreciente derivada de la suma de tiempos de proceso para cada trabajo de entre
todas las maquinas en las que puede ser procesado.
Por el contrario aquellas reglas de despacho que obtienen un mayor porcentaje de ARPD
y que por tanto más se distancian de la mejor solución, la de la heurística NEH serían
principalmente las siguientes:
Hill derivada de la suma de tiempos de proceso para cada trabajo de entre todas
las maquinas en las que puede ser procesado.
Creciente derivada de la suma de tiempos de proceso para cada trabajo de entre
todas las maquinas en las que puede ser procesado.
HI/HILO derivada de la suma de tiempos de proceso para cada trabajo de entre
todas las maquinas en las que puede ser procesado.
RESULTADOS PARA LA TARDANZA TOTAL 7.3
En este apartado presentaremos los resultados de la tardanza total, que como ya hemos
explicado anteriormente es el sumatorio del resultado de restar a cada tiempo de
finalización de cada trabajo la fecha de entrega del mismo siempre que la fecha de
entrega sea anterior a dicho resultado de finalización.
Empezamos analizando las primeras 8 reglas de despacho derivadas de la suma de
tiempos para cada trabajo de todas las maquina:
54
Tabla 5: ARPD Tardanza total - Reglas de despacho derivada de la suma de tiempos de procesos ( ).
Para este objetivo podemos observar como algunas de las reglas de despacho tienen
resultados dispares entre ellos. El rango para el ARPD es de (69.83,105.28). Así, las dos
primeras reglas de despacho, la decreciente y la creciente reflejan el peor y el mejor
resultado respectivamente.
Mostramos ahora la tabla de las reglas de despacho pertenecientes al tiempo de proceso
mínimo para cada trabajo:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 114,77 61,55 85,99 88,40 89,00 87,08 85,04 85,04
50 10 141,16 100,66 122,53 120,84 121,84 116,72 120,07 120,07
50 20 128,43 112,27 126,31 111,39 113,78 109,53 126,67 126,67
100 5 89,62 43,01 65,48 64,30 65,05 64,10 62,17 62,17
100 10 119,33 82,06 101,29 101,47 102,62 100,50 102,28 102,28
100 20 124,21 100,73 108,78 107,26 112,50 105,02 112,27 112,27
200 5 74,57 30,81 53,44 50,65 50,88 52,33 51,97 51,97
200 10 100,84 63,57 84,30 85,42 82,90 81,44 84,44 84,44
200 20 111,10 85,19 95,77 98,26 95,72 96,71 97,12 97,12
500 5 69,11 27,45 49,68 48,60 48,54 48,56 47,72 47,72
500 10 90,46 55,11 72,58 73,25 72,56 70,66 85,69 70,36
500 20 99,81 73,10 86,20 85,35 86,92 87,58 85,69 85,69
105,28 69,63 87,70 86,27 86,86 85,02 88,43 87,15Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Suma de tiempos para cada trabajo de todas las maquinas
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 97,77 67,72 87,05 86,35 93,60 87,17 82,98 82,83
50 10 124,80 105,57 117,97 119,77 120,45 118,07 118,42 120,85
50 20 123,04 111,02 115,31 116,73 110,69 116,56 112,94 109,45
100 5 80,38 48,55 63,87 65,99 69,68 68,31 58,65 64,09
100 10 108,94 89,31 99,62 99,44 101,15 100,76 92,69 96,12
100 20 115,05 105,04 112,00 110,55 117,86 113,28 109,93 107,77
200 5 65,22 37,49 53,97 53,40 56,03 56,80 48,60 48,92
200 10 93,07 77,61 85,38 84,16 86,63 85,98 80,35 81,33
200 20 103,72 92,09 96,50 96,37 98,84 99,21 96,90 98,36
500 5 61,60 35,14 48,77 48,66 52,55 52,22 44,44 44,00
500 10 78,74 63,84 71,56 72,63 75,23 75,45 83,98 68,83
500 20 91,00 81,13 85,55 86,05 87,07 86,31 83,98 85,02
95,28 76,21 86,46 86,67 89,15 88,34 84,49 83,96
REGLAS DE DESPACHO
Tiempo minimo para cada trabajo de entre todas las maquinas
Media
N.º
TRABAJOS
N.º
MAQUINAS
55
Tabla 6: ARPD Tardanza total - Reglas de despacho derivada del tiempo mínimo de proceso para cada
trabajo ( ).
En este caso, al igual que pasa con las reglas de despacho derivadas de la suma de tiempo
de proceso, se pueden observar diferencias notables entre las distintas reglas de
despacho. El rango de ARPD está situado entre (76.21, 95.28) siendo en este caso también
la decreciente y la creciente las que obtienen el peor y el mejor resultado
respectivamente.
Entre el resto de reglas de despacho también se aprecian ligeras diferencias en los
resultados mostrándose peores candidatas tanto la HI/HILO y la HI/LOHI. En cambio las
respectivas reglas de despacho inversas de las anteriores muestran unos mejores
resultados generales, situándose las reglas Hill y Valley en valores intermedios.
Analizamos por último las reglas de despacho pertenecientes al grupo de las fechas de
entrega:
Tabla 7: ARPD Tardanza total - Reglas de despacho derivada de las fechas de entrega ( ).
En este caso las reglas de despacho reflejan resultados muy similares, obteniéndose un
rango del ARPD de (85.64,87.06) lo que demuestra que ninguna de ellas se podría tomar
como solución notablemente mejor que el resto.
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 82,47 84,27 91,38 91,89 85,72 88,29 84,85 85,51
50 10 114,73 122,34 120,54 121,92 119,79 119,43 112,31 118,88
50 20 114,45 112,75 119,70 117,00 123,07 112,74 118,92 117,52
100 5 64,20 63,97 65,45 60,98 64,54 66,60 64,15 64,29
100 10 98,77 100,32 98,34 97,93 101,48 101,94 101,24 99,31
100 20 112,92 111,76 108,89 109,55 110,46 107,99 108,69 107,46
200 5 54,34 49,95 52,48 53,67 51,83 51,93 51,67 51,24
200 10 84,13 82,83 83,40 83,40 82,34 83,19 82,49 83,38
200 20 96,05 96,19 95,99 97,72 96,32 95,28 94,93 98,06
500 5 48,65 48,06 48,79 47,57 48,97 49,23 47,81 48,97
500 10 71,24 71,97 71,58 72,15 72,88 71,83 84,70 71,39
500 20 85,72 86,28 88,14 85,42 84,64 87,33 84,70 86,61
85,64 85,89 87,06 86,60 86,84 86,32 86,37 86,05
REGLAS DE DESPACHO
Fechas de entrega para cada trabajo
Media
N.º
TRABAJOS
N.º
MAQUINAS
56
En todo caso la que obtendría una mejor solución general con escasa diferencia seria la
decreciente, siendo la Hill la que mostraría un peor resultado.
Analizando las 24 reglas de despacho en conjunto podemos concluir que principalmente
son las reglas de despacho crecientes y decrecientes derivadas tanto del grupo de la suma
de tiempos como del grupo de tiempos mínimos para cada trabajo, las que reflejan unos
resultados más dispares, situándose el resto en valores intermedios.
Gráficas 3:ARPD para las 24 reglas de despacho - Objetivo Tardanza total.
40,00 50,00 60,00 70,00 80,00 90,00 100,00 110,00 120,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
Sum
a d
e t
iem
po
s p
ara
cad
a tr
abaj
od
e to
das
las
maq
uin
as T
iem
po
min
imo
par
a ca
da
trab
ajo
de
en
tre
to
das
las
maq
uin
asFe
chas
de
en
tre
ga p
ara
cad
atr
abaj
o
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
57
Así las más favorables de las 24 reglas de despacho serían:
Creciente derivada de la suma de tiempos de proceso.
Creciente derivada del tiempo mínimo de proceso para cada trabajo.
HI/LOHI inversas derivada del tiempo mínimo de proceso para cada trabajo.
Además, en este caso habría que destacar las siguientes reglas de despacho como aquellas
que responden peor al objetivo de la tardanza total las siguientes:
Decreciente derivada de la suma de tiempos de proceso.
Decreciente derivada del tiempo mínimo de proceso para cada trabajo.
HI/HILO derivada del tiempo mínimo de proceso para cada trabajo.
RESULTADOS PARA RETRASO TOTAL 7.4
Analizamos ahora los resultados obtenidos para la función objetivo del retraso total,
siendo este la diferencia entre la fecha de entrega y la fecha de finalización del trabajo, y
por lo tanto pudiendo ser este tanto positivo como negativo.
A continuación, se reflejan los datos extraídos para las reglas de despacho derivadas de la
suma de tiempos para cada trabajo de todas las maquinas en las que puede ser
procesado:
Tabla 8: ARPD Retraso total - Reglas de despacho derivada de la suma de tiempos de procesos ( ).
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 147,20 82,42 41,00 65,90 64,54 64,53 64,58 63,59
50 10 153,18 109,50 68,77 87,90 88,55 87,85 85,78 85,44
50 20 132,30 115,65 80,90 94,69 93,76 95,38 96,06 94,09
100 5 112,76 59,19 112,96 114,26 116,13 113,96 111,51 113,11
100 10 129,54 89,74 133,31 131,00 132,40 126,71 130,64 125,69
100 20 128,02 103,98 130,13 114,68 117,19 112,96 130,48 122,01
200 5 97,77 47,46 85,38 83,42 84,73 83,65 81,53 84,14
200 10 117,75 77,17 110,62 110,21 111,67 109,63 111,55 109,92
200 20 117,29 90,50 112,26 110,54 116,01 108,40 115,75 114,50
500 5 87,46 47,46 73,72 70,13 70,68 72,42 71,77 71,53
500 10 107,39 77,17 99,92 100,84 98,21 96,63 102,88 97,93
500 20 108,92 90,50 101,45 103,92 101,30 102,39 102,88 104,03
119,96 82,56 95,87 98,96 99,60 97,88 100,45 98,83
Suma de tiempos para cada trabajo de todas las maquinas
Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
58
En este caso se observa como el rango para el ARPD entre las 8 variaciones se sitúa entre
(82.56,119.96) siendo en este caso la que mejores resultados obtiene la creciente seguida
de la Hill. Por otra parte la que peores resultados obtiene, alejada del resto de funciones,
sería la decreciente.
Por último el resto de funciones obtienen resultados muy similares entre ellas.
Reflejamos ahora los resultados obtenidos en las reglas de despacho derivadas del tiempo
mínimo de proceso para cada trabajo:
Tabla 9: ARPD Retraso total - Reglas de despacho derivada del tiempo mínimo de proceso para
cada trabajo ( ).
En este caso el rango para el ARPD está en (90.24,109.03). Al igual que en el caso anterior
la función creciente obtiene los mejores resultados y por tanto es la que mejor se
comporta dentro de este grupo.
En el caso contrario, se encuentra la función decreciente la cual obtiene el peor resultado.
No obstante, en este caso los resultados obtenidos son más variados que en el grupo
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 126,90 90,89 49,70 64,86 64,64 69,00 68,73 60,00
50 10 135,94 114,69 78,43 86,81 87,94 90,70 91,07 83,17
50 20 126,92 114,11 89,39 94,01 94,52 95,40 94,79 92,35
100 5 102,13 66,07 114,65 112,03 121,23 113,97 108,32 108,10
100 10 118,40 97,77 128,21 130,16 131,05 128,75 128,98 131,12
100 20 118,65 108,31 118,90 120,03 114,03 120,04 116,38 112,74
200 5 87,10 55,34 83,61 85,47 89,97 88,45 77,24 83,39
200 10 109,28 92,43 108,72 108,25 109,88 110,09 100,97 104,69
200 20 109,66 97,76 115,59 113,94 121,27 116,96 113,53 111,16
500 5 79,10 55,34 74,27 73,47 76,45 77,61 67,93 68,33
500 10 94,63 92,43 100,89 99,60 102,01 101,60 102,66 96,49
500 20 99,67 97,76 102,23 102,02 104,52 105,07 102,66 104,07
109,03 90,24 97,05 99,22 101,46 101,47 97,77 96,30
Tiempo minimo para cada trabajo de entre todas las maquinas
Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
59
anterior comportándose algo peor las funciones Valley, HI/HILO y HI/LOHI que las inversas
e estas dos últimas y la función Hill.
Por último, mostramos los resultados obtenidos en el grupos de reglas de despacho
derivadas de las fechas de entrega:
Tabla 10 : ARPD Retraso total - Reglas de despacho derivadas de las fechas de entrega ( ).
En este caso el rango del ARPD se sitúa en (97.85,100.95) lo cual nos indica de la igualdad
de entre las 8 reglas de despacho. En todo caso, sería la función decreciente la que se
presenta como la mejor opción entre las 8 aunque de manera mínima.
Por otro lado, sería la función creciente en este caso la que obtendría los peores
resultados y por tanto la que podría comportarse peor de entre todas las del grupo
derivado de las fechas de entrega.
Como balance general dentro del objetivo del retraso total, y analizando las 24 reglas de
despacho en conjunto podemos destacar la mayor disparidad que se produce dentro del
objetivo de retraso total entre ellas. Además, en este caso el resto de funciones que se
derivan de la creciente y la decreciente también toman entre ellas valores más
diferenciados.
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 106,14 112,57 64,20 64,74 63,62 64,99 65,30 63,69
50 10 123,90 133,61 87,32 86,66 87,51 88,14 87,01 86,45
50 20 117,79 116,32 94,80 96,61 93,89 92,99 95,85 93,07
100 5 82,65 83,97 117,93 120,88 112,02 114,31 111,00 111,67
100 10 107,31 109,42 130,48 132,70 130,06 129,52 122,06 128,66
100 20 116,31 115,25 123,27 120,46 126,71 116,06 122,35 120,95
200 5 74,09 69,89 84,33 80,77 83,87 86,18 83,68 83,74
200 10 99,34 98,26 106,81 107,09 110,51 110,85 110,38 108,38
200 20 101,70 102,00 112,19 113,09 113,81 111,31 112,15 110,80
500 5 64,54 69,89 72,06 74,11 71,51 71,67 71,61 71,02
500 10 86,33 98,26 98,37 98,84 97,44 98,49 100,54 98,74
500 20 94,09 102,00 101,65 103,51 101,99 100,84 100,54 103,78
97,85 100,95 99,45 99,96 99,41 98,78 98,54 98,41
Fechas de entrega para cada trabajo
Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
60
Gráficas 4: ARPD para las 24 reglas de despacho - Objetivo Retraso total
Así las más favorables de las 24 reglas de despacho serían:
40,00 60,00 80,00 100,00 120,00 140,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
Sum
a d
e t
iem
po
s p
ara
cad
a tr
abaj
od
e to
das
las
maq
uin
as T
iem
po
min
imo
par
a ca
da
trab
ajo
de
en
tre
to
das
las
maq
uin
asFe
chas
de
en
tre
ga p
ara
cad
atr
abaj
o
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
61
Creciente derivada de la suma de tiempos de proceso.
Creciente derivada del tiempo mínimo de proceso para cada trabajo.
Hill derivada de la suma de tiempos de proceso.
En cambio, habría que destacar como aquellas que peor comportamiento tienen para este
objetivo las siguientes:
Decreciente derivada de la suma de tiempos de proceso.
Decreciente derivada del tiempo mínimo de proceso para cada trabajo.
HI/HILO y HI/LOHI derivada del tiempo mínimo de proceso para cada trabajo,
ambas con resultados parecidos.
RESULTADOS PARA SUMATORIO DE LOS TIEMPOS DE 7.5
FINALIZACION TOTAL
En este capítulo analizaremos los resultados obtenido en la programación para el objetivo
de fechas de finalización total, siendo este la suma de los tiempos de finalización de todos
y cada uno de los trabajos, observaremos de entre las reglas de despacho cual es la que
tiene un mejor comportamiento para minimizarlo.
Así, como en el resto de objetivos empezaremos reflejando los datos obtenidos para las
primeras 8 reglas de despacho, siendo estas las que derivan de la suma de tiempos de
proceso para cada trabajo de todas las máquinas en las que puede ser procesado, siendo
los siguientes:
62
Tabla 11: ARPD Tiempo finalización total - Reglas de despacho derivadas de la suma de tiempos de procesos ( ).
En este caso el rango para el ARPD está en (73.25,107.29). Como se puede observar de la
anterior tabla la regla de despacho que tiene un mejor comportamiento para este
objetivo, y que por tanto obtiene unos mejores resultados para la suma de los tiempos de
finalización seria la función creciente.
Por el contrario sería la regla de despacho decreciente la que obtendría peores resultados.
El resto de reglas de despacho obtendrían resultados bastante parejos entre ellas, aunque
habría que destacar principalmente la función Hill que refleja resultados relativamente
mejores que el resto.
A continuación mostraremos las reglas de despacho derivadas del tiempo mínimo de
proceso para cada trabajo:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 113,11 63,45 40,16 64,54 63,20 63,20 63,25 62,29
50 10 122,17 87,33 67,40 86,15 86,78 86,10 84,07 83,74
50 20 108,69 94,79 79,08 92,54 91,64 93,24 93,90 91,98
100 5 100,05 52,55 87,08 88,06 89,29 87,67 85,71 87,05
100 10 116,53 80,81 106,21 104,37 105,56 101,03 104,20 100,35
100 20 114,56 92,91 106,88 94,56 96,55 92,99 107,43 100,27
200 5 92,48 44,91 75,77 73,95 75,19 74,23 72,31 74,56
200 10 111,82 73,26 99,54 99,17 100,54 98,61 100,29 99,01
200 20 110,73 85,44 100,57 98,95 103,97 97,05 103,69 102,57
500 5 85,65 44,91 69,75 66,35 66,86 68,47 67,90 67,66
500 10 105,25 73,26 94,84 95,74 93,25 91,77 97,15 93,01
500 20 106,46 85,44 95,79 98,16 95,69 96,67 97,15 98,24
107,29 73,25 85,26 88,55 89,04 87,59 89,75 88,39Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Suma de tiempos para cada trabajo de todas las maquinas
63
Tabla 12: ARPD Tiempo finalización total - Reglas de despacho derivadas del tiempo minimo de proceso
para cada trabajo ( ).
En este caso las 8 reglas de depacho muestran un intervalo del ARPD situado entre
(80.31,97.64). Por una parte la función que mejores resultados obtiene sería la creciente,
siendo por el contrario la decreciente la que peor resultado obtiene.
Por otra parte el resto de reglas de despacho obtienen valores intermedios entre estas
dos anteriormente mencionadas, teniendo por tanto resultados que no se alejan de
manera sustancial y agrupándose este grupo de 8 reglas de despacho en un intervalo
menor que el grupo anteriormente expuesto.
En último lugar, se obtienen los resultados derivados de las reglas de despacho que
provienen de las fechas de entrega, siendo estos los siguientes:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 97,77 69,80 48,67 63,52 63,30 67,58 67,30 58,76
50 10 108,29 91,48 76,87 85,08 86,19 88,89 89,25 81,52
50 20 104,50 94,08 87,38 91,88 92,39 93,25 92,66 90,27
100 5 90,70 58,56 88,37 86,41 93,52 88,06 83,26 82,93
100 10 106,57 87,93 102,57 103,51 104,45 102,61 102,83 104,33
100 20 106,42 96,99 97,94 98,81 94,03 98,95 96,02 92,57
200 5 82,40 52,37 74,19 75,88 79,85 78,48 68,55 74,02
200 10 103,78 87,80 97,83 97,40 98,88 99,03 90,96 94,24
200 20 103,55 92,29 103,47 102,07 108,63 104,66 101,55 99,57
500 5 77,47 52,37 70,24 69,48 72,33 73,39 64,28 64,64
500 10 92,74 87,80 95,84 94,57 96,88 96,50 96,89 91,59
500 20 97,43 92,29 96,54 96,34 98,67 99,22 96,89 98,25
97,64 80,31 86,66 88,75 90,76 90,88 87,54 86,06Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Tiempo minimo para cada trabajo de entre todas las maquinas
64
Tabla 13: ARPD Tiempo finalización total - Reglas de despacho derivadas de las fechas de entrega ( ).
Para este último grupo de reglas de despacho derivadas de las fechas de entrega,
podemos ver que los resultados obtenidos en cuanto a ARPD para el objetivo de tiempo
de finalización final se sitúan en un intervalo entre (87.64,89.71), siendo por tanto muy
similares entre ellos.
Por una parte el mejor resultado sería el de la función creciente, siendo el de la
decreciente el peor de las 8 reglas de despacho, no obstante, como ya hemos explicado
anteriormente, presentan entre ellas diferencias mínimas.
Como balance general dentro del objetivo del tiempo de finalización total, y analizando las
24 reglas de despacho en conjunto podemos distinguir como existen algunas reglas de
despacho que reflejan comportamientos tanto peores o mejores, pero en todo caso
alejado del resto de reglas de despacho las cuales obtienen resultados similares entre ellas
siendo las diferencias mínimas.
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 81,54 86,37 62,87 63,41 62,31 63,65 63,95 62,38
50 10 98,78 106,28 85,58 84,95 85,77 86,40 85,28 84,73
50 20 97,19 96,05 92,66 94,43 91,77 90,90 93,67 90,97
100 5 73,40 74,56 90,65 92,83 86,11 88,18 85,46 86,20
100 10 96,53 98,60 103,72 105,59 103,42 103,13 97,60 102,85
100 20 104,08 103,27 101,50 99,50 104,22 95,44 100,86 99,62
200 5 70,09 66,13 74,86 71,75 74,40 76,40 74,25 74,40
200 10 94,30 93,28 96,12 96,30 99,45 99,77 99,24 97,43
200 20 95,99 96,28 100,42 101,28 101,95 99,69 100,34 99,32
500 5 63,21 66,13 68,18 70,10 67,68 67,79 67,75 67,20
500 10 84,61 93,28 93,42 93,85 92,53 93,50 94,92 93,75
500 20 91,97 96,28 95,95 97,75 96,30 95,22 94,92 97,96
87,64 89,71 88,83 89,31 88,82 88,34 88,19 88,07Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Fechas de entrega para cada trabajo
65
Gráficas 5: ARPD para las 24 reglas de despacho - Objetivo Sumatorio de los tiempos de finalización
Así las más favorables de las 24 reglas de despacho serían:
Creciente derivada de la suma de tiempos de proceso.
Creciente derivada del tiempo mínimo de proceso para cada trabajo.
Hill derivada de la suma de tiempos de proceso.
40,00 60,00 80,00 100,00 120,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
Sum
a d
e t
iem
po
s p
ara
cad
atr
abaj
o d
e t
od
as la
s m
aqu
inas
Tie
mp
o m
inim
o p
ara
cad
a tr
abaj
od
e e
ntr
e t
od
as la
s m
aqu
inas
Fech
as d
e e
ntr
ega
par
a ca
da
trab
ajo
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
66
En cambio, habría que destacar como aquellas que peor comportamiento tienen para este
objetivo las siguientes:
Decreciente derivada de la suma de tiempos de proceso.
Decreciente derivada del tiempo mínimo de proceso para cada trabajo.
HI/HILO y HI/LOHI derivada del tiempo mínimo de proceso para cada trabajo,
ambas con resultados parecidos.
RESULTADOS DE RETRASO MÁXIMO 7.6
En el siguiente subcapítulo vamos a reflejar y analizar los resultados obtenidos en el
objetivo de retraso máximo, es decir, aquel trabajo cuya diferencia entre el tiempo de
finalización y el de la fecha de entrega es mayor, comparando todas las reglas de
despacho entre ellas y obteniendo aquellas que permiten obtener mejores resultados así
como las que por el contrario, son peores en este objetivo.
En la siguiente tabla se muestran los valores de ARPD obtenidos para el primer grupo de
reglas de despacho derivadas de la suma de tiempos de proceso para cada trabajo de
entre todas las máquinas:
Tabla 14: ARPD Retraso máximo - Reglas de despacho derivada de la suma de tiempos de procesos ( ).
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 67,68 69,33 68,29 68,59 68,85 69,35 69,50 69,41
50 10 69,63 74,97 68,59 71,10 72,57 69,82 73,22 70,70
50 20 52,05 57,78 61,19 51,08 56,05 52,82 60,62 54,86
100 5 64,62 66,64 66,68 63,28 65,65 66,43 65,37 66,03
100 10 67,69 69,76 70,70 68,54 70,43 70,23 71,41 70,43
100 20 56,03 57,49 55,49 53,44 56,07 51,68 56,27 57,52
200 5 63,01 65,29 64,46 61,57 62,64 63,51 64,35 64,24
200 10 65,21 65,69 66,77 67,40 66,48 65,89 67,58 66,54
200 20 56,62 58,38 55,87 56,12 56,35 55,79 56,89 57,11
500 5 60,37 71,87 61,98 60,34 60,66 60,66 60,55 60,76
500 10 63,75 65,17 63,71 64,02 64,49 62,57 56,77 62,21
500 20 56,70 58,27 57,24 56,29 57,60 58,11 56,77 56,91
60,95 65,05 63,41 61,81 63,15 62,24 63,27 63,06
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Suma de tiempos para cada trabajo de todas las maquinas
Media
67
En este caso se observa que el rango para el ARPD está situado en el intervalo (60.95,
65.05), lo que refleja la similitud de las reglas de despacho, no obstante, hay que destacar
que función decreciente refleja un comportamiento ligeramente mejor para este objetivo,
situándose el resto en porcentajes similares aunque algo más altos, siendo la función
creciente la de mayor valor entre las 8 reglas de despacho.
Ahora, nos centraremos en las reglas de despacho derivadas del tiempo mínimo para cada
trabajo de entre todas las máquinas en que puede ser procesado:
Tabla 15: ARPD Retraso máximo - Reglas de despacho derivada del tiempo minimo de proceso para cada
trabajo ( ).
En este caso el porcentaje de ARPD para las 8 reglas de despacho está situado en el
intervalo de (60.70, 64.44).
Así, el valor obtenido por la función creciente es el mejor entre las 8.Por el contrario la
peor de las reglas de despacho en este caso sería la función Decreciente.
El resto de funciones se presentan en valores intermedios entre estas dos anteriormente
mencionada.
Por ultimo presentamos la tabla donde se indican los resultados del ARPD para las reglas
de despacho derivadas de las fechas de entrega:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 66,47 69,58 69,39 69,37 69,96 65,45 70,44 71,08
50 10 68,19 74,97 69,37 72,97 70,52 68,99 71,90 74,78
50 20 56,90 57,78 54,76 56,42 53,50 53,87 52,84 51,64
100 5 66,29 66,64 64,82 67,57 66,30 67,07 64,65 67,83
100 10 68,32 68,61 69,05 68,38 69,06 70,81 66,44 69,26
100 20 52,52 55,48 55,83 56,85 58,80 55,85 53,31 56,02
200 5 62,48 63,48 65,98 64,21 63,78 64,86 64,10 64,03
200 10 66,17 68,06 68,46 67,32 67,22 66,09 65,67 65,90
200 20 54,80 56,85 56,81 55,59 56,84 57,18 56,00 58,80
500 5 60,44 71,87 61,02 60,97 60,60 60,74 61,37 59,96
500 10 62,00 63,08 63,45 64,31 63,98 64,38 55,95 63,79
500 20 55,80 56,91 56,45 57,28 56,47 56,02 55,95 57,19
60,70 64,44 61,95 63,44 63,09 62,61 61,55 63,36
Tiempo minimo para cada trabajo de entre todas las maquinas
Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
68
Tabla 16: ARPD Retraso máximo - Reglas de despacho derivadas de las fechas de entrega ( ).
En este caso el intervalo de valores en los que se sitúa el ARPD es (61.50,63.65) siendo la
función HI/HILO inversa la que obtiene los valores mejores para este objetivo, seguida
muy de cerca de la función decreciente.
Por otra parte la función creciente es la que refleja los peores resultados, siendo el resto
de las funciones valores intermedios y muy próximos entre todas ellas.
Así las más favorables dentro de las 24 reglas de despacho para este objetivo del retraso
máximo serian:
Función decreciente derivada del tiempo mínimo de proceso para cada trabajo.
Función decreciente derivada de la suma de tiempos de proceso.
Función HI/HILO inversa derivada de fechas de entrega.
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 64,27 66,58 69,53 73,61 66,04 69,03 69,23 67,33
50 10 70,89 69,31 73,61 73,56 70,37 69,97 66,66 71,41
50 20 55,35 50,29 52,95 58,02 58,28 54,94 55,47 57,54
100 5 65,38 66,20 64,60 64,57 63,60 66,24 65,86 65,75
100 10 68,07 67,29 67,64 67,91 70,19 68,10 68,96 69,72
100 20 57,86 53,64 54,04 56,65 54,36 53,84 54,65 53,10
200 5 64,46 62,66 63,25 65,43 63,06 63,11 63,00 63,23
200 10 66,73 66,48 66,32 66,93 66,18 67,06 65,95 66,49
200 20 56,53 54,57 56,67 56,93 56,08 55,41 55,22 56,97
500 5 60,79 60,46 60,38 60,11 61,22 61,62 60,21 60,84
500 10 62,84 64,20 62,94 64,14 64,15 63,37 56,40 63,01
500 20 56,80 56,71 58,22 55,95 56,45 57,65 56,40 57,58
62,50 61,53 62,51 63,65 62,50 62,53 61,50 62,75Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Fechas de entrega para cada trabajo
69
Gráficas 6: ARPD para las 24 reglas de despacho - Objetivo Retraso máximo.
Por el contrario aquellas que peor comportamiento han reflejado para este mismo
objetivo serian:
Función creciente derivada de la suma de tiempos de proceso.
Función creciente derivada del tiempo mínimo de proceso para cada trabajo.
Función valley derivada de las fechas de entrega para cada trabajo.
58,00 59,00 60,00 61,00 62,00 63,00 64,00 65,00 66,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
Sum
a d
e t
iem
po
s p
ara
cad
atr
abaj
o d
e t
od
as la
s m
aqu
inas
Tiem
po
min
imo
par
a ca
da
trab
ajo
de
en
tre
tod
as la
sm
aqu
inas
Fech
as d
e e
ntr
ega
par
a ca
da
trab
ajo
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
70
RESULTADOS PARA EL SUMATORIO DE TRABAJOS TARDÍOS 7.7
En este apartado pasaremos a presentar los resultados obtenidos para el objetivo de
optimización de trabajos tardíos totales, que muestra el número total de trabajos
procesados en el periodo de tiempo posterior a las fechas de entrega de los mismos,
estableciendo como en el resto de objetivos las diferencias entre las distintas reglas de
despacho así como el análisis final donde se muestran los resultados en conjunto de todas
ellas.
En esta primera tabla se muestran los resultados obtenidos para las reglas de despacho
derivadas del grupo de la suma de tiempos de proceso para cada trabajo de entre todas
las maquinas en las que puede ser procesado:
Tabla 17: ARPD Sumatorio trabajos tardíos - Reglas de despacho derivadas de la suma de tiempos de procesos ( ).
En este caso vemos que el ARPD se sitúa en el intervalo (5.78,7.42).
Hay que destacar en este objetivo los valores de ARPD que en conjunto son
considerablemente menor que la mayoría de apartados anteriormente analizados hasta el
momento. Esto se debe a que las cifras empleadas en este caso son mucho menores y por
tanto la diferencia respecto al NEH también son considerablemente menores.
En este grupo de reglas de despacho se refleja, a pesar de la poca amplitud del intervalo,
diferencias importantes, siendo la función creciente la que obtiene un mejor resultado, en
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 14,55 9,92 13,77 11,42 12,38 12,45 12,22 11,92
50 10 15,83 11,64 15,87 13,12 14,16 13,31 14,42 13,49
50 20 16,77 23,06 25,23 23,39 24,62 23,63 25,47 24,60
100 5 5,54 3,42 5,86 3,93 4,70 4,55 4,91 5,00
100 10 6,94 5,11 7,06 4,92 6,36 6,46 6,31 6,06
100 20 9,61 7,92 9,11 7,94 8,80 8,59 8,72 8,62
200 5 2,16 0,92 2,08 1,26 1,72 1,76 1,63 1,65
200 10 2,84 1,99 2,88 2,04 2,52 2,58 2,30 2,24
200 20 4,80 3,96 4,80 4,01 4,24 4,36 4,44 4,38
500 5 0,44 0,05 0,44 0,07 0,26 0,26 0,20 0,21
500 10 0,70 0,40 0,71 0,45 0,55 0,56 1,13 0,68
500 20 1,19 0,89 1,21 0,85 1,10 1,06 1,13 1,12
6,78 5,78 7,42 6,12 6,78 6,63 6,91 6,66
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Suma de tiempos para cada trabajo de todas las maquinas
Media
71
cambio la función Hill es en este caso la que peor comportamiento tiene respecto al
objetivo y por tanto con respecto a la heurística NEH.
A continuación se exponen la tabla del grupo de reglas de despacho derivadas del tiempo
mínimo de proceso de cada trabajo:
Tabla 18: ARPD Sumatorio trabajos tardíos - Reglas de despacho derivadas del tiempo mínimo de proceso
para cada trabajo ( ).
Para este grupo de reglas de despacho el intervalo de ARPD se sitúa en (6.39,7.45), siendo
resultados realmente parejos entre todas ellas. No obstante, se aprecia como la función
creciente tiene mejores resultados algo también visible en el resto de funciones que
derivan de esta, con respecto a la función decreciente y el resto que derivan de la misma.
Reflejamos ahora los datos de las reglas de despacho derivadas de las fechas de entrega
de cada trabajo:
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 13,86 11,09 13,50 11,06 12,78 13,60 11,24 11,16
50 10 15,46 12,98 14,66 13,68 14,53 14,94 14,47 14,17
50 20 26,49 22,03 25,06 23,60 24,48 25,00 24,41 23,45
100 5 5,25 4,50 4,87 4,46 4,70 5,16 4,29 4,43
100 10 6,57 5,83 6,55 5,73 5,35 6,77 5,85 5,95
100 20 9,73 8,65 9,46 8,44 8,59 9,90 9,17 8,50
200 5 2,02 1,38 1,84 1,45 1,74 1,99 1,43 1,48
200 10 2,80 2,62 2,76 2,41 2,06 3,08 2,41 2,22
200 20 4,84 5,11 4,79 4,52 3,64 5,00 4,52 4,21
500 5 0,42 0,20 0,41 0,13 0,30 0,41 0,25 0,22
500 10 0,71 0,78 0,74 0,65 0,46 0,85 1,16 0,55
500 20 1,18 1,53 1,10 1,39 0,07 1,32 1,16 1,10
7,45 6,39 7,14 6,46 6,56 7,34 6,70 6,45Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Tiempo minimo para cada trabajo de entre todas las maquinas
72
Tabla 19:ARPD Sumatorio trabajos tardíos - Reglas de despacho derivadas de las fechas de entrega ( ).
En este caso el intervalo del ARPD está situado entre (5.93,7.63) reflejando por tanto las
mayores diferencias entre todas las reglas de despacho. Así, la función decreciente
obtiene en este caso los mejores resultados, siendo por el contrario la función creciente
en este caso la que obtiene unos resultados peores.
También se pueden observar como en las siguientes dos funciones, la Hill y la Valley,
derivadas de la decreciente y la creciente respectivamente, reflejan también diferencias
siendo también la Hill la que obtiene mejores resultados frente a la Valley.
El resto de funciones al presentar menor influencia de la creciente y la decreciente
presentan también valores medios y similares entre ellas.
Como resultado global de las 24 reglas de despacho para el objetivo del sumatorio de
trabajos tardíos podemos resumir que existe una gran variedad de resultados dentro del
pequeño intervalo en el que se encuentran todas ellas.
decreciente creciente Hill valley HI/Hilo Hi/lohi HI/Hilo inv. HI/lohi inv.
50 5 10,04 14,80 11,80 14,19 12,43 12,27 11,32 11,53
50 10 11,99 15,75 14,19 15,16 13,84 13,69 13,76 13,73
50 20 23,90 24,80 24,33 25,05 24,23 24,32 24,38 23,89
100 5 3,62 6,04 4,27 5,38 4,60 4,58 4,48 4,69
100 10 4,75 7,37 5,45 6,87 5,92 5,95 6,21 5,97
100 20 8,18 9,78 8,40 9,34 8,64 8,65 8,99 8,67
200 5 1,18 2,29 1,54 1,98 1,54 1,51 1,75 1,75
200 10 1,93 2,96 1,97 2,97 2,35 2,44 2,27 2,38
200 20 4,21 5,05 4,19 4,91 4,65 4,24 4,21 4,21
500 5 0,17 0,53 0,27 0,43 0,33 0,33 0,11 0,14
500 10 0,39 0,84 0,48 0,77 0,60 0,61 1,07 0,67
500 20 0,82 1,39 0,83 1,35 1,08 1,02 1,07 1,07
5,93 7,63 6,48 7,37 6,69 6,63 6,63 6,56Media
N.º
TRABAJOS
N.º
MAQUINAS
REGLAS DE DESPACHO
Fechas de entrega para cada trabajo
73
Gráficas 7:ARPD para las 24 reglas de despacho - Objetivo Sumatorio de trabajos tardios.
Así las más favorables dentro de las 24 reglas de despacho para este objetivo del
sumatorio de trabajos tardíos serían:
Función creciente derivada de la suma de tiempos de proceso.
Función decreciente derivada de las fechas de entrega para cada trabajo.
Función Valley derivada de la suma de tiempos de proceso.
0,00 1,00 2,00 3,00 4,00 5,00 6,00 7,00 8,00 9,00
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
decreciente
creciente
Hill
valley
HI/Hilo
Hi/lohi
HI/Hilo inv.
HI/lohi inv.
Sum
a d
e t
iem
po
s p
ara
cad
atr
abaj
o d
e t
od
as la
s m
aqu
inas
Tiem
po
min
imo
par
a ca
da
trab
ajo
de
en
tre
to
das
las
maq
uin
asFe
chas
de
en
tre
ga p
ara
cad
atr
abaj
o
REG
LAS
DE
DES
PA
CH
O
ARPD (%)
74
Por el contrario aquellas que peor comportamiento han reflejado para este mismo
objetivo serian:
Función creciente derivada de las fechas de entrega para cada trabajo.
Función decreciente derivada del tiempo mínimo de proceso.
Función Hill derivada de las fechas de entrega para cada trabajo.
75
8. CONCLUSIONES
En este apartado se pretenden analizar de forma más general los resultados obtenidos en
el capítulo de resultados anteriormente descrito y establecer un estudio de cuáles serían
las reglas de despacho mejores en cada caso de objetivo de optimización con el objetivo
de establecer las diferencias entre ellas y obtener unas conclusiones detalladas que nos
permitan reconocer aquellas más favorables y por el contrario aquellas que son menos
favorables.
Por una parte se establecerán los ARPD medios de cada una de las reglas de despacho y la
media para cada una de ellas para el total de los 6 objetivos de optimización estudiados
en el presente trabajo.
Así, se pueden observar en las próximas dos tablas como hay algunas reglas de despacho
que destacan respecto a otras de manera global.
Las reglas de despacho que mejor comportamiento han obtenido de manera global son:
Función creciente derivada de la suma de tiempos de proceso para cada trabajo
de entre todas las máquinas en las que puede ser procesado.
Esta regla de despacho obtiene en el ranking de las posiciones la mejor posición.
Por una parte obtiene en tres de los seis objetivos el mejor resultado de entre
todas las reglas de despacho.
Por otra parte en una de los objetivos de optimización estudiados obtiene el peor
puesto.
Función creciente derivada del tiempo mínimo de proceso para cada trabajo de
entre todas las máquinas en las que puede ser procesado.
Esta regla de despacho es la segunda en el ranking de posiciones. En este caso se
presenta el segundo mejor resultado para dos de los objetivos, estando entre los
seis mejores en otros tres de los objetivos.
76
Las funciones que peor comportamiento han obtenido de manera global son:
Función decreciente derivada de la suma de tiempos de proceso para cada
trabajo de entre todas las máquinas en las que puede ser procesado.
Esta función creciente obtiene el primer puesto en tres de los seis objetivos
estudiados, siendo la que peor se comporta de manera general. Estos la tardanza
total, el retraso total y el retraso máximo. Hay que destacar también que en dos de
los otros tres objetivos tiene resultados que la sitúan entre las 4 mejores.
Función decreciente derivada del tiempo mínimo de proceso para cada trabajo
de entre todas las máquinas en las que puede ser procesado.
En este caso, la función obtiene cuatro de los objetivos estudiados entre los tres
peores resultados de todas las reglas de despacho utilizadas, obteniendo por el
contrario en uno de sus objetivos el mejor resultado.
Hay que destacar que muchas de las reglas de despacho toman valores intermedios y muy
parecidos entre ellas debido fundamentalmente a que las secuencias que las forman
tienen muy distribuidos los distintos valores que las forman, ello hace por una parte que
no tomen resultados ni realmente buenos ni malos y que se aproximen a otras.
Por otra parte las reglas de despacho formadas por las funciones creciente y decreciente
se pueden observar que si reflejan resultados muy dispares entre ellas situándose en
posiciones extremas, es decir o se obtienen resultados realmente buenos o por el
contrario los resultados obtenidos son nefastos.
77
Tabla 20: ARPD medio de cada regla de despacho para cada objetivo.
MakespanTardanza
totalRetraso total
Suma tiempos
de
finalización
Suma trabajos
tardios
Máximo
retraso
decreciente 63,05 105,28 119,96 7,49 107,29 60,95 77,34
creciente 64,75 69,63 82,56 5,78 73,25 65,05 60,17
Hill 65,06 87,70 95,87 7,24 85,26 63,41 67,42
valley 63,01 86,27 98,96 6,12 88,55 61,81 67,45
HI/Hilo 64,72 86,86 99,60 6,78 89,04 63,15 68,36
Hi/lohi 63,85 85,02 97,88 6,63 87,59 62,24 67,20
HI/Hilo inv. 64,60 88,43 100,45 6,91 89,75 63,27 68,90
HI/lohi inv. 64,51 87,15 98,83 6,66 88,39 63,06 68,10
decreciente 64,51 95,28 109,03 7,45 97,64 60,70 72,43
creciente 63,87 76,21 90,24 6,39 80,31 64,44 63,58
Hill 64,66 86,46 97,05 7,14 86,66 61,95 67,32
valley 64,61 86,67 99,22 6,46 88,75 63,44 68,19
HI/Hilo 64,32 89,15 101,46 6,56 90,76 63,09 69,22
Hi/lohi 64,39 88,34 101,47 7,34 90,88 62,61 69,17
HI/Hilo inv. 63,32 84,49 97,77 6,70 87,54 61,55 66,89
HI/lohi inv. 64,41 83,96 96,30 6,45 86,06 63,36 66,76
decreciente 63,88 85,64 97,85 5,93 87,64 62,50 67,24
creciente 64,11 85,89 100,95 7,63 89,71 61,53 68,31
Hill 64,09 87,06 99,45 6,48 88,83 62,51 68,07
valley 64,64 86,60 99,96 7,37 89,31 63,65 68,59
HI/Hilo 64,12 86,84 99,41 6,69 88,82 62,50 68,06
Hi/lohi 64,02 86,32 98,78 6,63 88,34 62,53 67,77
HI/Hilo inv. 62,55 86,37 98,54 6,63 88,19 61,50 67,30
HI/lohi inv. 63,95 86,05 98,41 6,56 88,07 62,75 67,63
Funciones objetivo
Media TotalTabla con ARPD medio para cada
Regla de despacho
Fechas de
entrega
para cada
trabajo
REGLAS DE
DESPACHO
Suma de
tiempos
para cada
trabajo de
todas las
maquinas
Tiempo
minimo
para cada
trabajo de
entre todas
las
maquinas
78
Tabla 21: Ranking de posición global de cada Regla de despacho.
MakespanTardanza
totalRetraso total
Suma tiempos
de
finalización
Suma trabajos
tardios
Máximo
retraso
decreciente 3 24 24 23 24 2
creciente 23 1 1 1 1 24
Hill 24 19 3 19 3 20
valley 2 9 13 3 13 6
HI/Hilo 22 16 17 16 17 17
Hi/lohi 5 5 8 10 7 8
HI/Hilo inv. 18 21 19 17 20 18
HI/lohi inv. 16 18 12 13 12 15
decreciente 17 23 23 22 23 1
creciente 6 2 2 4 2 23
Hill 21 12 5 18 5 7
valley 19 14 14 6 14 21
HI/Hilo 13 22 21 9 21 16
Hi/lohi 14 20 22 20 22 13
HI/Hilo inv. 4 4 6 15 6 5
HI/lohi inv. 15 3 4 5 4 19
decreciente 7 6 7 2 8 9
creciente 11 7 20 24 19 4
Hill 10 17 16 7 16 11
valley 20 13 18 21 18 22
HI/Hilo 12 15 15 14 15 10
Hi/lohi 9 10 11 12 11 12
HI/Hilo inv. 1 11 10 11 10 3
HI/lohi inv. 8 8 9 8 9 14
Ranking de posiciones por objetivos
Funciones objetivo
REGLAS DE
DESPACHO
Suma de
tiempos
para cada
trabajo de
todas las
maquinas
Tiempo
minimo
para cada
trabajo de
entre todas
las
maquinas
Fechas de
entrega
para cada
trabajo
79
9. BIBLIOGRAFI A
Michael L.Pinedo. Scheduling Theory, Algorithms, and Systems. 4ª Edición. Nueva York:
Springer, 2012.
J.Santos Organización de la producción II. Planificacion de procesos industriales, Unicopia,
Tecnun, 2007.
J. M. Framinan , R. Leisten & C. Rajendran (2003): Different initial sequences for the
heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the
static permutation flowshop sequencing problem, International Journal of Production
Research, 41:1, 121-148
Velasco Sánchez, Juan, Gestión de la producción en la empresa: planificación,
programación y control, Ed. Pirámide, 2013.
Wollmann, Thomas E.; Berry, Willian L.; Whybark, D. Clay: Gerencia Sistemas de
Planificación y Control de la Producción. Ed. Irwin.
Vinicius A. Armentano; Débora P. Ronconi (1998) Tabu search for total tardiness
minimization in flowshop scheduling problems, computers & operations research,26, 219-
235.
C.N Potts; L.N Van Wassenhove (1982) A descomposition algorithm for the single machine
total tardiness problem,1.
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Optimization and Approx-imation in Deterministic Sequencing and Scheduling: A Survey. Annals of Discrete Mathematics,5:287–326, 1979.
[En linea] http://www.codeblocks.org/ Code::Blocks IDE User Guide JN-UG-3028
[En linea] http://www.gestiondeoperaciones.net/programacion-de-trabajos/reglas-de-
prioridad-para-la-programacion-de-n-trabajos-en-una-maquina/
[En línea ] http://pert-cpm-operaciones.blogspot.com.es/2010/12/secuenciacion.html
80
[En línea] https://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-
industrial/producci%C3%B3n/programaci%C3%B3n-a-corto-plazo/
[En línea] https://www.gestiopolis.com/proceso-de-planificacion-programacion-y-control-
de-la-produccion/