DISEÑO DE UN PROCEDIMIENTO BASADO EN ALGORITMOS ...repository.udistrital.edu.co/bitstream/11349/2785/1... · diseÑo de un procedimiento basado en algoritmos genÉticos para dar

DISEÑO DE UN PROCEDIMIENTO BASADO EN ALGORITMOS GENÉTICOS PARA DAR SOLUCIÓN AL PROBLEMA DE SCHEDULING ADMITIENDO RECHAZOS EN ESCENARIOS FLEXIBLE FLOW SHOP

VIVIANA ALEXANDRA PEREA GONZÁLEZ Código: 20131196022

UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS FACULTAD DE INGENIERÍA

MAESTRÍA EN INGENIERÍA INDUSTRIAL BOGOTÁ D.C.

2015

DISEÑO DE UN PROCEDIMIENTO BASADO EN ALGORITMOS GENÉTICOS

PARA DAR SOLUCIÓN AL PROBLEMA DE SCHEDULING ADMITIENDO RECHAZOS EN ESCENARIOS FLEXIBLE FLOW SHOP

VIVIANA ALEXANDRA PEREA GONZÁLEZ Código: 20131196022

PROYECTO DE GRADO PARA OPTAR POR EL TÍTULO DE MAGÍSTER EN INGENIERÍA INDUSTRIAL

Director del Proyecto: Ing. JAIRO HUMBERTO TORRES ACOSTA, P.Ph.D

UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS FACULTAD DE INGENIERÍA

MAESTRÍA EN INGENIERÍA INDUSTRIAL BOGOTÁ D.C.

2015

“Learning is the only thing the mind never exhausts, never fears and never regrets”

- Leonardo da Vinci

~ 1 ~

TABLA DE CONTENIDO

ÍNDICE DE TABLAS .......................................................................................... 4

ÍNDICE DE GRÁFICOS ...................................................................................... 6

INTRODUCCIÓN ................................................................................................ 8

OBJETIVOS ..................................................................................................... 10

1. OBJETIVO GENERAL ................................................................... 10

2. OBJETIVOS ESPECÍFICOS .......................................................... 10

CAPÍTULO 1. MARCO TEÓRICO DE LA INVESTIGACIÓN ........................... 11

1.1 ESTRATEGIA PARA LA CONSTRUCCIÓN DEL MARCO

TEÓRICO ...................................................................................................... 11

1.2 DEFINICIÓN GENERAL DEL PROBLEMA DE SCHEDULING ..... 15

1.2.1 Evolución Histórica ........................................................................ 15

1.2.2 Definición formal de los problemas de Scheduling ........................ 19

1.2.3 Entornos de Máquinas .................................................................. 21

1.2.4 Características de Procesamiento ................................................. 25

1.2.5 Criterio de Optimización ................................................................ 26

1.2.6 Aplicación de este dominio de conocimiento en el desarrollo de la

investigación ............................................................................................... 27

1.3 ACEPTACIÓN DE ÓRDENES Y SCHEDULING ........................... 28

1.4 ALGORITMOS GENÉTICOS ......................................................... 30

1.4.1 La teoría de Holland ...................................................................... 31

1.4.2 Terminología y Operadores de los Algoritmos Genéticos ............. 32

1.4.3 Terminación de la búsqueda. Criterios de convergencia. .............. 39

1.4.4 Construcción de un Algoritmo Genético: Diagrama de flujo. ......... 40

1.4.5 Aplicación de los Algoritmos Genéticos ........................................ 43

1.5 ESTADO DEL ARTE: APLICACIÓN DE ALGORITMOS

GENÉTICOS PARA DAR SOLUCIÓN AL PROBLEMA DE SCHEDULING

ADMITIENDO RECHAZOS ........................................................................... 43

1.6 CONCLUSIONES PARCIALES ..................................................... 44

1.7 BIBLIOGRAFÍA .............................................................................. 45

CAPÍTULO 2. PROCEDIMIENTO PROPUESTO PARA EL ESCENARIO DE

ACEPTACIÓN DE ÓRDENES Y SCHEDULING EN AMBIENTES FLEXIBLE

FLOW SHOP .................................................................................................... 51

~ 2 ~

2.1 MODELO MATEMÁTICO FORMULADO ....................................... 53

2.1.1 Notación ........................................................................................ 54

2.1.2 Modelo de Programación Entera Mixta ......................................... 55

2.1.3 Generación de datos y límite superior del Modelo de Programación

Entera Mixta propuesto .............................................................................. 59

2.2 APROXIMACIÓN HEURÍSTICA .................................................... 60

2.3 PROCEDIMIENTO PROPUESTO RESULTADO DE LA

INVESTIGACIÓN........................................................................................... 63

2.3.1 Construcción de la Población Inicial .............................................. 65

2.3.2 Generaciones sucesivas ............................................................... 66

2.3.3 Cruce ............................................................................................. 66

2.3.4 Diversidad de la población ............................................................ 67

2.3.5 Criterio de Terminación ................................................................. 68

2.3.6 Parámetros del Algoritmo Genético ............................................... 68

2.4 CONCLUSIONES PARCIALES ..................................................... 73

2.5 BIBLIOGRAFÍA .............................................................................. 74

CAPÍTULO 3. VERIFICACIÓN DEL PROCEDIMIENTO PROPUESTO PARA

EL ESCENARIO DE ACEPTACIÓN DE ÓRDENES Y SCHEDULING EN

AMBIENTES FLEXIBLE FLOW SHOP ............................................................ 76

3.1 COMPARACIÓN DEL MODELO DE PROGRAMACIÓN ENTERA

MIXTA Y EL PROCEDIMIENTO PROPUESTO ............................................ 77

3.1.1 Instancia de 7 órdenes × 5 estaciones ......................................... 78

3.1.2 Instancia de 8 órdenes × 7 estaciones ......................................... 86

3.2 VERIFICACIÓN DEL DESEMPEÑO DEL PROCEDIMIENTO

PROPUESTO ................................................................................................ 96

3.3 CONCLUSIONES PARCIALES ................................................... 100

3.4 BIBLIOGRAFÍA ............................................................................ 101

CAPÍTULO 4. CONCLUSIONES Y RECOMENDACIONES .......................... 102

4.1 CONCLUSIONES ........................................................................ 102

4.2 RECOMENDACIONES ................................................................ 106

APÉNDICE A. LÍMITE SUPERIOR DEL MODELO DE PROGRAMACIÓN

ENTERA MIXTA PROPUESTO ...................................................................... 108

~ 3 ~

APÉNDICE B. RESULTADOS EXPERIMENTALES DEL DISEÑO

FACTORIAL 𝟐𝟑 PROPUESTO PARA ESTABLECER LOS PARÁMETROS

DEL ALGORITMO GENÉTICO ...................................................................... 116

~ 4 ~

ÍNDICE DE TABLAS

Tabla 2.1. Generaciones requeridas para encontrar las mejores soluciones.... 68

Tabla 2.2. Arreglo general de un diseño bi-factorial .......................................... 70

Tabla 2.3. Factores y niveles analizados .......................................................... 73

Tabla 3.1. Datos obtenidos Instancia 7 órdenes y 5 estaciones ....................... 80

Tabla 3.2. Estadísticos valores Función Objetivo Instancia de 7 órdenes y 5

estaciones ......................................................................................................... 81

Tabla 3.3. Prueba de normalidad valores Función Objetivo Instancia de 7

órdenes y 5 estaciones ..................................................................................... 82

Tabla 3.4. Prueba t muestras pareadas. Valores Función Objetivo Instancia de

7 órdenes y 5 estaciones .................................................................................. 83

Tabla 3.5. Estadísticos Tiempo de Corrida Instancia de 7 órdenes y 5

estaciones ......................................................................................................... 84

Tabla 3.6. Prueba de normalidad Tiempo de Corrida Instancia de 7 órdenes y 5

estaciones ......................................................................................................... 85

Tabla 3.7. Prueba t muestras pareadas. Tiempo de corrida Instancia de 7


Tabla 3.8. Datos obtenidos Instancia 8 órdenes y 7 estaciones ....................... 87

Tabla 3.9. Estadísticos valores Función Objetivo Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 89

Tabla 3.10. Prueba de normalidad valores Función Objetivo Instancia de 8


Tabla 3.11. Prueba t muestras pareadas. Valores Función Objetivo Instancia de

8 órdenes y 7 estaciones .................................................................................. 90

Tabla 3.12. Estadísticos Tiempo de Corrida Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 92

Tabla 3.13. Prueba de normalidad Tiempos de Corrida Instancia de 8 órdenes y

7 estaciones ...................................................................................................... 93

Tabla 3.14. Prueba de normalidad Tiempos de Corrida Ajustados Instancia de 8


Tabla 3.15. Prueba de Wilcoxon Tiempos de Corrida Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 94

Tabla 3.16. Prueba de Wilcoxon Tiempos de Corrida Ajustados Instancia de 8


Tabla 3.17. Estadísticos Tiempos de Corrida Ajustados Instancia de 8 órdenes

y 7 estaciones ................................................................................................... 95

Tabla 3.18. Datos obtenidos Instancia 20 órdenes y 10 estaciones ................. 97

Tabla 3.19. Datos obtenidos Instancia 30 órdenes y 10 estaciones ................. 99

Tabla A.1. Prueba piloto diseñada .................................................................. 109

Tabla A.2. Configuraciones consideradas en las pruebas computacionales del

modelo formulado ........................................................................................... 110

~ 5 ~

Tabla A.3. Tiempo promedio de corrida para 5 órdenes ................................. 111





Tabla B.1. Factores y niveles analizados ........................................................ 117

Tabla B.2. Estadísticos descriptivos Función Objetivo .................................... 118

Tabla B.3. Análisis de varianzas – ANOVA Función Objetivo ......................... 120

Tabla B.4. Estimaciones de Función Objetivo respecto al Tamaño de la

Población ........................................................................................................ 120

Tabla B.5. Estimaciones de Función Objetivo respecto a la Probabilidad de

Cruce .............................................................................................................. 121

Tabla B.6. Estimaciones de Función Objetivo respecto a la Probabilidad de

Mutación ......................................................................................................... 122

Tabla B.7. Estadísticos Descriptivos Tiempo de Corrida ................................ 124

Tabla B.8. Análisis de Varianzas – ANOVA Tiempo de Corrida ..................... 125

Tabla B.9. Resultados Ajuste Factorial para Tiempo de Corrida - Minitab 15 . 126

Tabla B.10. Contraste de Levene sobre la igualdad de varianzas .................. 127

Tabla B.11. Diferencia de muestras de Scheffé Tamaño de la Población ...... 128

Tabla B.12. Estimaciones de Tiempo de Corrida respecto al Tamaño de la

Población ........................................................................................................ 128

Tabla B.13. Diferencia de muestras de Scheffé Probabilidad de Cruce ......... 130

Tabla B.14. Estimaciones de Tiempo de Corrida respecto a la Probabilidad de

Cruce .............................................................................................................. 130

Tabla B.15. Diferencia de muestras de Scheffé Probabilidad de Mutación .... 132

Tabla B.16. Estimaciones de Tiempo de Corrida respecto a la Probabilidad de

Mutación ......................................................................................................... 132

Tabla B.17. Estimaciones de Tiempo de Corrida respecto al Tamaño de la

Población * Probabilidad de Cruce ................................................................. 133

Tabla B.18. Prueba de normalidad de residuales ........................................... 135

~ 6 ~

ÍNDICE DE GRÁFICOS

Gráfico 1.1. Hilo conductor de la investigación ................................................. 12

Gráfico 1.2. Flujo de información a lo largo del proyecto .................................. 14

Gráfico 1.3. Diagrama de flujo de información en un sistema de manufactura. 19

Gráfico 1.4. Diagramas de Gantt orientados a los trabajos (a) y las máquinas

(b) ..................................................................................................................... 20

Gráfico 1.5. Flow Shop Scheduling ................................................................... 24

Gráfico 1.6. Flexible Flow Shop ........................................................................ 24

Gráfico 1.7. Representación del Genotipo y Fenotipo ...................................... 33

Gráfico 1.8. Población ....................................................................................... 34

Gráfico 1.9. Representación de un gen ............................................................ 35

Gráfico 1.10. Operador de Cruce ...................................................................... 36

Gráfico 1.11. Operador de Mutación ................................................................. 37

Gráfico 1.12. Ciclo de los Algoritmos Genéticos ............................................... 39

Gráfico 1.13. Diagrama de flujo de un Algoritmo Genético ............................... 41

Gráfico 1.14. Representación gráfica del diagrama de flujo de un Algoritmo

Genético............................................................................................................ 42

Gráfico 2.1. Metodología diseñada para el Capítulo 2 ...................................... 52

Gráfico 2.2. Función de utilidad para la orden 𝒋 ................................................ 53

Gráfico 2.3. Diagrama de Flujo Algoritmo Genético propuesto ......................... 64

Gráfico 2.4. Vista geométrica del diseño........................................................... 71

Gráfico 2.5. Matriz del diseño ........................................................................... 72

Gráfico 3.1. Metodología diseñada para el Capítulo 3 ...................................... 76

Gráfico 3.2. Resultados Función Objetivo Instancia de 7 órdenes y 5 estaciones

.......................................................................................................................... 80

Gráfico 3.3. Resultados Tiempo de Corrida Instancia de 7 órdenes y 5

estaciones ......................................................................................................... 80

Gráfico 3.4. Media de valores Función Objetivo Instancia de 7 órdenes y 5

estaciones ......................................................................................................... 81

Gráfico 3.5. Media de Tiempo de Corrida Instancia de 7 órdenes y 5 estaciones

.......................................................................................................................... 84


.......................................................................................................................... 88

Gráfico 3.7. Resultados Tiempo de Corrida Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 88

Gráfico 3.8. Media de valores Función Objetivo Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 89

Gráfico 3.9. Valores Ajustados Función Objetivo Instancia 8 órdenes y 7

estaciones ......................................................................................................... 91

Gráfico 3.10. Media de Tiempo de Corrida Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 92

~ 7 ~

Gráfico 3.11. Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7

estaciones ......................................................................................................... 95

Gráfico 3.12. Media de Tiempos de Corrida Ajustados Instancia de 8 órdenes y

7 estaciones ...................................................................................................... 96

Gráfico 3.13. Desempeño Procedimiento Vs. Heurística Instancia 20 órdenes y

10 estaciones .................................................................................................... 98

Gráfico 3.14. Desempeño Procedimiento Vs. Heurística Instancia 30 órdenes y

10 estaciones .................................................................................................... 99

Gráfico A.1. Metodología del experimento ...................................................... 108

Gráfico B.1. Metodología del experimento ...................................................... 116

Gráfico B.2. Gráfico de Perfil Función Objetivo respecto al Tamaño de la

Población ........................................................................................................ 121

Gráfico B.3. Gráfico de Perfil Función Objetivo respecto a la Probabilidad de

Cruce .............................................................................................................. 122

Gráfico B.4. Gráfico de Perfil Función Objetivo respecto a la Probabilidad de

Mutación ......................................................................................................... 123

Gráfico B.5. Gráfico de Perfil Tiempo de Corrida respecto al Tamaño de la

Población ........................................................................................................ 129

Gráfico B.6. Gráfico de Perfil Tiempo de Corrida respecto a la Probabilidad de

Cruce .............................................................................................................. 131

Gráfico B.7. Gráfico de Perfil Tiempo de Corrida respecto a la Probabilidad de

Mutación ......................................................................................................... 133

Gráfico B.8. Gráfico de Perfil Tiempo de Corrida respecto al Tamaño de

Población * Probabilidad de Cruce ................................................................ 134

Gráfico B.9. Q-Q Plot Residuo Estandarizado ................................................ 135

Gráfico B.10. Histograma de Residuo ............................................................. 136

Gráfico B.11. Diagrama de residuales respecto a su orden ............................ 136

Gráfico B.12. Series de tiempo de Residuo tipificado ..................................... 137

Gráfico B.13. Diagrama de residuos vs. valores ajustados ............................. 137

~ 8 ~

INTRODUCCIÓN

Debido a los mercados globalizados y altamente competitivos en que se desenvuelven las industrias manufactureras en la actualidad, es cada vez más frecuente que se demanden productos con características únicas y personalizadas, que deben entregarse siguiendo estrictos requerimientos de los clientes, teniendo como agravante las limitaciones impuestas por la capacidad de producción. Es así como las decisiones relacionadas tanto con la aceptación de órdenes como la programación de los trabajos, deben tomarse de forma simultánea. Esto se debe a que, para emplear dicha capacidad de una forma más eficiente y asegurar la satisfacción de los clientes, es necesario determinar qué pedidos se aceptan y de qué manera se programan con el fin de maximizar las utilidades de la firma. En torno a este objetivo, la presente investigación se enfoca en un escenario de manufactura Flexible Flow Shop estático determinístico, donde todas las estaciones están conformadas por máquinas no relacionadas, esto debido a que en situaciones reales es común encontrar máquinas más modernas trabajando junto a otras más viejas o menos eficientes, las cuales se conservan en la línea debido a su alto costo de reemplazo y, aunque puedan ejecutar las mismas operaciones que las nuevas, necesitan un tiempo de operación mayor. Este escenario, denominado Aceptación de Órdenes y Scheduling (OAS) o Scheduling admitiendo rechazos (MSR), ha atraído gran atención desde el punto de vista académico y profesional, de forma que se encuentran en la literatura numerosos aportes considerando diferentes características y objetivos, empleándose varios métodos exactos para su resolución como programación entera y entera mixta, programación dinámica y algoritmos branch-and-bound. Sin embargo, debido a su complejidad, una solución óptima puede ser difícil de encontrar especialmente cuando el tamaño del problema es particularmente grande. Es por esto que los investigadores se han orientado a buscar heurísticas de aproximación que permitan encontrar soluciones cercanas al óptimo dentro de un tiempo computacional razonable, que incluyen optimización extrema, recocido simulado, búsqueda tabú, colonia de hormigas, algoritmo de optimización parcial y la elegida para realizar esta investigación, algoritmos genéticos. Sin embargo y como motivación para el desarrollo del presente proyecto, la revisión literaria realizada por el autor en torno a este problema demuestra que los aportes considerando un ambiente Flexible Flow Shop y en la aplicación de algoritmos genéticos en ambientes de una o varias máquinas, siguen siendo escasos. Bajo estos antecedentes, la presente investigación se enfocará en el Capítulo 1 en la revisión teórica del problema de Scheduling, su importancia y la evolución histórica que ha marcado el rumbo de su aplicación en industrias manufactureras. Así mismo, se abordará el problema de interés a través de un

~ 9 ~

recorrido histórico por los avances que se presentan en la literatura respecto a los mecanismos de solución propuestos. Finalmente, se presentará una aproximación al estado del arte relacionado con la aplicación de los algoritmos genéticos en este contexto. Una vez realizado el recorrido necesario para delimitar el problema bajo estudio, en el Capítulo 2 se presentarán las herramientas de ingeniería

diseñadas como mecanismo de solución. Particularmente, se expondrá el modelo de programación entera mixta (MIP) que lo caracteriza formalmente, así como la función de utilidad que se trabajará a lo largo del proyecto, compuesta por tres métricas a saber: las ganancias recibidas por las órdenes aceptadas, la penalización por aquellas que son rechazadas y el costo del tiempo ocioso de los recursos, que según el conocimiento del autor no ha sido estudiada. Posteriormente y debido a su complejidad, se presentará la aproximación heurística que servirá para guiar la búsqueda del algoritmo genético y acelerar su convergencia. Estas herramientas, servirán de insumo para desarrollar el procedimiento propuesto, resultado de la investigación, que busca aprovechar los beneficios de la recombinación de una población de soluciones y el criterio de elección de las máquinas que sigue la heurística. Posteriormente, en el Capítulo 3 se realizará la verificación teórica del

procedimiento propuesto mediante la comparación de los resultados obtenidos a través de su implementación en problemas simulados, lo que permitirá confirmar si el procedimiento brinda buenas soluciones en tiempos inferiores a los requeridos por el enfoque exacto. Finalmente, el Capítulo 4 expondrá las conclusiones arrojadas por el recorrido

teórico y experimental del autor en la construcción del procedimiento propuesto y se sentarán las bases para futuras investigaciones en esta área del conocimiento.

~ 10 ~

OBJETIVOS

Para el correcto desarrollo de esta investigación, se han establecido los siguientes objetivos, que permitirán evidenciar los alcances y aportes del estudio. 1. OBJETIVO GENERAL

Diseñar un procedimiento basado en Algoritmos Genéticos que dé solución en tiempos computacionales razonables al problema de Aceptación de Órdenes y Scheduling en escenarios Flexible Flow Shop maximizando las utilidades. 2. OBJETIVOS ESPECÍFICOS

Identificar las teorías y enfoques existentes en torno al problema de

Scheduling admitiendo rechazos, verificando la aplicación de algoritmos genéticos en diferentes ambientes de manufactura.

Diseñar un algoritmo genético que permita dar solución al problema de Aceptación de Órdenes y Scheduling en escenarios Flexible Flow Shop con máquinas no relacionadas y maximizando la utilidad.

Verificar el desempeño de la herramienta propuesta a través de programas computacionales que simulen problemáticas reales en manufactura.

~ 11 ~

CAPÍTULO 1

MARCO TEÓRICO DE LA INVESTIGACIÓN

La revisión bibliográfica especializada que se requiere para la construcción del marco referencial de esta investigación, así como la exploración del estado del arte en el área de estudio que la compete, constituyen la esencia del análisis teórico principal y se fundamentan en el escenario de Aceptación de Órdenes y Scheduling, ambientes de manufactura Flexible Flow Shop y la aplicación de Algoritmos Genéticos en el contexto de secuenciación de tareas. En este capítulo, se presentarán de manera inicial los tópicos contextuales que se han considerado de pertinencia para el desarrollo de este estudio, así como la información relacionada que se encuentra en la literatura, que además de sentar las bases de unificación de criterios, permitirá demostrar por qué se ha elegido analizar este ambiente en particular y la importancia del procedimiento propuesto. 1.1 ESTRATEGIA PARA LA CONSTRUCCIÓN DEL MARCO TEÓRICO El planteamiento del marco teórico y el hilo conductor que permitirá alcanzar los objetivos planteados en esta investigación, toma como fundamento los siguientes aspectos:

Revisión del marco conceptual en torno al contexto general de Scheduling y escenarios de máquinas en paralelo.

Análisis relacionado con los supuestos, restricciones, parámetros y funciones objetivo consideradas en el escenario de Aceptación de Órdenes y Scheduling.

Estudio del marco conceptual relacionado con la construcción de

Algoritmos Genéticos y su aplicación en ambientes de manufactura. El adelanto de las investigaciones preliminares que surten la revisión teórica en torno a estos referentes, analizan en última instancia, el desarrollo y el grado de aplicación de los Algoritmos Genéticos en el contexto de Scheduling admitiendo rechazos en un ambiente de manufactura Flexible Flow Shop, con el objetivo de verificar la necesidad de diseñar un procedimiento basado en esta herramienta, que se ajuste a los requerimientos de las industrias manufactureras reales. Por tanto, el diseño esquemático del hilo conductor de la investigación se construye tal como se muestra en el Gráfico 1.1.

~ 12 ~

Gráfico 1.1. Hilo conductor de la investigación

Fuente: Elaboración Propia.

Aceptación de Órdenes y Scheduling 1. Marco conceptual. 2. Supuestos, parámetros, funciones

objetivo y restricciones del sistema. 3. Herramientas de solución

empleadas.

Ambientes Flexible Flow Shop 1. Marco conceptual. 2. Conformación de cada etapa o

puesto de trabajo. 3. Caracterización de las máquinas “o

medios de trabajo”. 4. Configuración de la línea de

manufactura.

Alcance de investigaciones previas

Relación entre los resultados existentes y los esperados.

1. ¿Qué investigaciones se han

desarrollado?

2. ¿Qué resultados han arrojado?

3. ¿Qué problemas se han

encontrado?

4. ¿Qué se requiere desarrollar?

Alcance de la aplicación. 1. Utilidad de la investigación.

2. Complejidad de su aplicación.

3. Conclusiones.

Desarrollo. 1. Modelo de programación entera

mixta. 2. Procedimiento. 3. Verificación teórica. 4. Conclusiones y

Recomendaciones

HILO CONDUCTOR

Algoritmos Genéticos 1. Marco conceptual. 2. Aplicación en escenarios de

manufactura.

3. Construcción y configuración

respecto al escenario de estudio.

4. Puesta en marcha

~ 13 ~

De este modo, se revisará de manera inicial el marco conceptual relacionado con el problema general de Scheduling, su importancia al interior de las organizaciones manufactureras, así como la evolución histórica que ha marcado el rumbo de su aplicación en diferentes escenarios. Una vez sentadas las bases en torno al macro problema a resolver, se tomará como objeto principal de estudio una configuración particular de líneas de producción denominada Flexible Flow Shop, de la que se identificarán sus características en torno al flujo de productos, las propiedades de las máquinas, recursos o medios de trabajo, la configuración de estaciones y las relaciones existentes entre ellas. En este contexto, se involucrará el escenario de Aceptación de Órdenes y Scheduling o Scheduling admitiendo rechazos, analizando su importancia para las industrias reales y las restricciones adicionales que incluye dentro del sistema. Estos dos temas centrales configuran el escenario particular a través de un conjunto de variables, parámetros y restricciones que permitirán formular posteriormente un modelo de programación entera mixta que además de caracterizar formalmente el escenario de estudio, dará una solución exacta en instancias de tamaño moderado. Debido al carácter NP-Hard del ambiente considerado, se hace necesario involucrar una herramienta de aproximación como los Algoritmos Genéticos, de manera que se obtenga una solución en tiempos computacionalmente razonables a problemas de mayor tamaño. Alrededor de esta temática, la revisión teórica contemplará la evolución de la herramienta y sus ventajas respecto a otras técnicas de búsqueda, así como el pseudocódigo y los parámetros de entrada que rigen su construcción y las conclusiones derivadas de investigaciones previas en torno a su diseño y aplicación en escenarios de manufactura, particularmente bajo un ambiente que admite rechazos en las órdenes recibidas. Todo ello, servirá de piso del sistema para diseñar el procedimiento resultado de esta investigación. Finalmente y de manera adicional a los cuerpos teóricos básicos presentados, es crucial involucrar la teoría relacionada con el diseño de experimentos en problemas similares al escenario bajo estudio, de manera que sea posible llevar a cabo la verificación teórica de la herramienta propuesta. El siguiente gráfico, clarifica este flujo de información a lo largo de todo el proyecto, mostrando su importancia para el desarrollo de las herramientas computacionales esperadas, que por corresponder a capítulos posteriores, se muestran en línea segmentada.

~ 14 ~

DEFINICIÓN GENERAL DEL PROBLEMA DE SCHEDULING

ALGORITMOS GENÉTICOS

DISEÑO DE EXPERIMENTOS

Gráfico 1.2. Flujo de información a lo largo del proyecto


Características de los medios de trabajo.

Propiedades de las estaciones de manufactura.

Flujo de tareas. Variables, parámetros y

restricciones que caracterizan el escenario.

Tipos de máquinas: idénticas, con diferentes velocidades, no relacionadas.

FLEXIBLE FLOW SHOP

Aplicación en industrias manufactureras reales.

Funciones objetivo consideradas en la literatura.

Variables, parámetros y

restricciones impuestas al sistema.

Herramientas empleadas

para su solución.

Evolución Importancia para las industrias manufactureras Terminología y notación MÁQUINAS EN PARALELO ACEPTACIÓN DE ÓRDENES Y SCHEDULING

Función objetivo a considerar.

Variables Objetivos Parámetros Restricciones Características

de los trabajos: tiempos de alistamiento y procesamiento, fechas de entrega, penalizaciones, utilidad, otros.

Caracteriza formalmente el escenario bajo estudio.

Provee una solución óptima en instancias pequeñas.

MODELO DE

PROGRAMACIÓN

ENTERA MIXTA

BASE TEÓRICA GENERAL BASE TEÓRICA ESPECÍFICA

Desarrollo y evolución. Importancia. Ventajas sobre otras

herramientas de búsqueda. Pseudocódigo que rige su

construcción general. Parámetros de entrada y

calibración: tamaño de la población, operadores de cruce y mutación, criterio de parada.

Puesta en marcha en Visual Basic.

Casos de aplicación en escenarios de manufactura.

Aportes de literatura en torno a sus resultados en la búsqueda de buenas soluciones en el ambiente de Aceptación de Órdenes y Scheduling considerando máquinas en paralelo.

APROXIMACIÓN

HEURÍSTICA

Provee una buena solución en instancias de mayor tamaño.

Acelera y orienta la búsqueda del algoritmo genético.

Formas de diseñar el Algoritmo Genético en escenarios de manufactura bajo un ambiente de Aceptación de Órdenes y Scheduling

PROCEDIMIENTO

PROPUESTO

Pseudocódigo específico.

Inclusión aproximación heurística y características propias del escenario.

Calibración parámetros.

Resultados experimentales

Marco conceptual. Revisión de la literatura especializada e investigaciones previas relacionadas

con el diseño de experimentos en escenarios similares.

Verificación teórica del procedimiento propuesto

~ 15 ~

1.2 DEFINICIÓN GENERAL DEL PROBLEMA DE SCHEDULING

En este inciso, se pretende establecer una reseña sucinta sobre el problema general de Scheduling, definido como un proceso de toma de decisiones aplicable a cualquier tipo de industria manufacturera y de servicios, que juega un rol importante en producción, transporte y distribución e incluso en el procesamiento de información y las comunicaciones [1] que se encarga de asignar recursos a cada una de las tareas u operaciones que se deben realizar en un periodo de tiempo dado. Es evidente, que al ser estos medios limitados, es necesaria una programación eficiente con la cual se cumplan uno o varios objetivos empresariales. Tal como lo manifiesta Pinedo (2005), dichos recursos pueden variar de acuerdo a su naturaleza, por ejemplo, pueden incluir fuerza de trabajo, máquinas, herramientas, materiales o energía. De igual manera, las tareas a realizar pueden tener variedad de interpretaciones, desde el mecanizado de piezas en entornos de manufactura, hasta el procesamiento de información en los sistemas informáticos. Una tarea se caracteriza usualmente por factores como el tiempo de inicio, fecha de entrega, la prioridad que tenga respecto a otras, el tiempo de fabricación y el consumo de recursos requerido para que pueda llevarse a cabo. Por su parte, un conjunto de actividades, requerirá de una serie de restricciones de precedencia, que pueden ser definidas de múltiples maneras [2]. Así mismo, diferentes criterios para determinar el desempeño de la línea pueden tomarse en consideración; por lo general, el objetivo es una función del tiempo de finalización de los trabajos. Muchos de los problemas de Scheduling que se presentan en las industrias manufactureras son bastante complejos en cuanto a su naturaleza, por lo que presentan dificultades para ser solucionados con técnicas de optimización convencionales. Usualmente, este tipo situaciones son caracterizadas como un problema de optimización combinatoria [3], es decir, problemas con un número finito de soluciones factibles sujetos a restricciones de alta complejidad, por lo que pueden ser bastante difíciles de resolver óptimamente sobre todo, cuando su tamaño es particularmente grande. Debido a esto, se han clasificado como problemas de tipo NP-Hard [2] y han motivado el creciente interés en el uso de heurísticas, heurísticas híbridas, procesos sistemáticos, algoritmos de aproximación o una combinación de estas herramientas, que aseguran la posibilidad de encontrar soluciones cercanas al óptimo en tiempos computacionalmente razonables. 1.2.1 Evolución Histórica Comprender las formas en que se ha elaborado la programación en el pasado, es fundamental para analizar los sistemas actuales y encontrar formas de mejorarlos. Los dos problemas principales de la programación de la producción son, de acuerdo con Wight (1984), “prioridades” y “capacidades”, en otras palabras, ¿Qué debe hacerse primero? y ¿Quién debe hacerlo? [4].

~ 16 ~

Las instalaciones de fabricación de productos emergieron por primera vez a mediados del siglo XVIII, cuando la Primera Revolución Industrial creó un poder centralizado que dio origen a nuevas estructuras en las organizaciones. La dinámica al interior de molinos y talleres y los proyectos que se desarrollaban en su interior, fueron los precursores de las organizaciones manufactureras modernas y de las prácticas administrativas que emplean [4], gestionándose en la actualidad a través grupos especializados que luchan por el control de sistemas altamente complejos buscando alcanzar múltiples objetivos empresariales. Las primeras fábricas eran bastante simples y relativamente pequeñas y producían un escaso número de productos en grandes lotes. En los años 1800, las empresas manufactureras estaban preocupadas por maximizar la productividad de los costosos equipos de la fábrica, por lo que se instauró como objetivo la máxima utilización de los mismos. Los encargados dirigían la fábrica coordinando todas las actividades necesarias para el limitado número de productos de los que eran responsables: contrataron operarios, compraron materiales, planificaron la producción y entregaron los productos. A pesar de que las fábricas crecieron, éstas solo se hicieron más grandes, pero no más complejas [4]. Alrededor de 1890, todo cambió. Las empresas manufactureras comenzaron a elaborar una amplia gama de productos y esta variedad convirtió la producción en un campo complejo, que el mismo personal no estaba en capacidad de manejar. La separación que realizó Frederick Taylor de la planificación y la ejecución, justificó el uso formal de métodos de programación. Durante la Primera Guerra Mundial, Taylor propuso que se abriera una oficina dedicada a la planificación de la producción, en la que se requerían muchas personas para crear planes, gestionar el inventario y controlar las operaciones. La “producción dependiente” creó un plan maestro de producción basado en órdenes reales y capacidades. Ante esta necesidad, los primeros trabajos sobre Scheduling se iniciaron desde el campo de la Investigación Operativa, resolviendo problemas en una línea de producción de dos máquinas. El modelo se caracterizaba por su reducción a una formulación matemática, solucionándose con métodos algorítmicos formales. Otros trabajos que intentaron resolver el problema de la planificación en forma exacta incluyen el método de Graphplan creado por Avrim Blum a mediados de los años 80 y el STRIP desarrollado en el año 1971 por Fikes y Nilsson. Ambos revolucionaron el campo con sus planteamientos y fijaron el inicio para posteriores investigaciones; sin embargo, se veían limitados por lo genérico de sus procedimientos; tanto así, que para su aplicación era necesario forzar situaciones y contextos del propio Scheduling para encajar en las condiciones que ellos mismos proponían. De ahí que la aplicabilidad de tales restricciones en variantes complejas era sencillamente imposible.

~ 17 ~

De otro lado, Henry L. Gantt se ha reconocido como el hombre que se identifica de forma única con la programación de tareas al diseñar gráficos innovadores para el control de la producción. De acuerdo con Cox (1992), un diagrama de Gantt es “el más conocido y el mejor tipo de gráfico de control especialmente diseñado para mostrar gráficamente la relación entre los resultados previstos y los resultados reales”. Gantt diseñó sus gráficos para que los operarios o supervisores lograran saber rápidamente si la producción se entregaba en la fecha prevista o si había algún retraso. El software utilizado en las empresas modernas, incluye aún estas funciones. En 1903 Gantt presentó dos tipos de “balances”: el registro de los hombres, que presenta un control de lo que debería haber hecho un trabajador y lo que efectivamente realizó y el balance diario del trabajo que muestra la cantidad de trabajo que debe realizarse y las tareas que restan. Trece años más tarde, Gantt discutió el Scheduling, especialmente en los ambientes Job Shop. Propuso dar al operario una “orden de trabajo”, es decir, una lista secuencial de las actividades que debe realizar cada día; además, discutió la necesidad de coordinarlas para evitar “interferencias”. Muchas empresas acogieron la sugerencia de Taylor de crear una oficina para la planeación de la producción y las personas encargadas de esta tarea, adoptaron y modificaron los aportes de Gantt. Se puede decir que Gantt fue un pionero en el desarrollo de formas gráficas que permitieran visualizar la programación de la producción y el estado de la misma, ya que hizo uso del tiempo (no solo de la cantidad) como una forma de medir las tareas. Por su parte, en 1939 Mitchell discutió el papel de la planificación de la producción por departamentos, incluyendo enrutamiento, despacho y Scheduling, proceso al que definió como “el momento de realización de todas las operaciones, con el fin de garantizar su terminación cuando sea necesario”. Mitchell enfatizó que, en algunas plantas, los trabajadores deberían tener más información sobre los factores cualitativos que afectan la producción ya que eran responsables de las tareas más detalladas. Muther (1944) concordó con Mitchell, estableciendo que en muchos ambientes, los supervisores deciden qué trabajo realizar y se limitan a asignarlos a los operarios. A partir de la Segunda Guerra Mundial se emplearon programas especializados para controlar la logística u organización de las acciones bélicas, a los que se denominó MRP (Material Requirements Planning), que a finales de los años 50 fueron parte importante en los sectores productivos, especialmente en Estados Unidos. Las compañías que los adoptaron se dieron cuenta que estos sistemas les permitían llevar un control de diversas actividades tales como el manejo de inventario, facturación, pago y administración de nómina.

~ 18 ~

De manera paralela, la evolución de las computadoras favoreció el crecimiento de estos sistemas, aumentando el número de empresas que optaban por ellos. A pesar de que las computadoras eran muy rudimentarias, contaban con capacidad de almacenamiento y recuperación de datos, facilitando el manejo y canalización eficiente de datos hacia todas las áreas de la firma, de manera que al integrarlos, pudieran ejecutar acciones rápidamente. En las décadas de los sesenta y setenta, los sistemas MRP evolucionaron para ayudar a las empresas a reducir los niveles de inventario de los materiales que utilizaban en su proceso productivo ya que al ajustar sus requerimientos a la demanda real, se compraba sólo lo necesario y en el momento oportuno, disminuyendo los costos totales. Los sistemas de manufactura han evolucionado de tal manera que actualmente la fabricación en este entorno supone un proceso cuya complejidad es variable dependiendo de los tipos de producto que se fabriquen y que consta de múltiples etapas intermedias, en las que tienen lugar procesos industriales que transforman los materiales empleados y se realizan ensambles de componentes para obtener unidades de nivel superior que a su vez pueden ser integrantes de otras, hasta la terminación del producto final, listo para ser entregado a los clientes externos. Además, se consideran eventos inesperados como daños o paradas de máquinas, en tanto que pueden afectar considerablemente la programación de dichos trabajos. Por tanto, desarrollar, bajo este contexto una programación detallada, ayuda a mantener la eficiencia y el control de las operaciones. Los sistemas básicos para planificar y controlar estos procesos modernos constan de las mismas etapas, si bien su implementación en una situación concreta depende de las particularidades de la línea. Todos ellos abordan el problema de la ordenación del flujo de materiales en la empresa para alcanzar eficientemente los objetivos de producción, relacionados con ajustar lo mejor posible los niveles de inventarios, la capacidad, mano de obra, costos de producción, plazos de fabricación y las cargas de trabajo en las distintas secciones a las necesidades de la producción. De esta forma y tal como se observa en el siguiente gráfico, la planeación y el proceso de Scheduling interactúan con otros sistemas de apoyo a las decisiones. Además del sistema de Planeación de Requerimiento de Materiales (MRP – Material Requirements Planning) actual, cuyo propósito es garantizar que después de realizada una programación de tareas, todas las materias primas y recursos se encuentren disponibles en un tiempo especificado, también se han incluido los sistemas de Planeación de Recursos Empresariales (ERP – Enterprise Resource Planning), que controlan y coordinan la información de todas las divisiones de la firma e incluyen algunas veces datos de proveedores y compradores. Diferentes sistemas de soporte a las decisiones pueden estar conectados a un sistema ERP, facilitando la planeación a mediano y largo plazo, así como el proceso de Scheduling a corto plazo.

~ 19 ~

Gráfico 1.3. Diagrama de flujo de información en un sistema de manufactura.

Fuente: Elaboración Propia. Adaptado de: Pinedo, M. 2005.

1.2.2 Definición formal de los problemas de Scheduling

Todos los problemas de Scheduling involucran un número finito de trabajos y máquinas, cuyo conjunto se denota por 𝑛 y 𝑚, respectivamente. Usualmente, el

índice 𝑖 denota una máquina en particular, mientras que 𝑗 se relaciona con un trabajo [10]. Una secuencia o schedule es su asignación en una o varias máquinas en uno o varios intervalos de tiempo, los cuales se representan en un diagrama de Gantt que puede estar orientado a las tareas (parte a del siguiente diagrama) o a los recursos (parte b). El problema de Scheduling es encontrar una secuencia que satisfaga un conjunto dado de restricciones [5].

~ 20 ~

Gráfico 1.4. Diagramas de Gantt orientados a los trabajos (a) y las máquinas (b)

Fuente: Elaboración Propia. Adaptado de: Brucker, P. 2007.

Un trabajo 𝑗 consiste de un número 𝑛𝑗 de operaciones 𝑂𝑗1, …𝑂𝑗𝑛𝑗

a las que se

asocia un tiempo de procesamiento 𝑝𝑖𝑗 . Si el trabajo 𝑗 se compone de una

única operación, se identifica con 𝑂𝑗1 y su tiempo de procesamiento es 𝑝𝑗. Así

mismo, se especifica un tiempo de liberación o arribo (due date) 𝑟𝑗, en que la

primera operación de 𝑗 se encuentra disponible para su procesamiento [5], es decir, la fecha más tempana en que dicho trabajo puede iniciar su recorrido por la línea de manufactura. Cada operación se encuentra asociada a un conjunto de máquinas 𝜇𝑖𝑗 ⊆

{𝑀1, … , 𝑀𝑚} y puede ser procesada por cualquiera de ellas o únicamente por

aquellas que cumplan ciertos requerimientos, lo que se refiere a un escenario de máquinas especializadas. De igual forma, a cada trabajo puede asociarse una fecha de entrega o due date 𝑑𝑗, que representa la fecha en la que debe hacerse el envío o completarse

el trabajo, es decir, el tiempo en que se ha prometido al cliente que llegará el

~ 21 ~

producto. Completar una tarea después de esta fecha está permitido, pero se incurre en una penalización por incumplimiento. Cuando un trabajo debe entregarse obligatoriamente en este tiempo, se habla entonces de una fecha

límite (deadline) y se denota como �̅�𝒋 [6, 1, 5]. También puede incluirse una

ponderación 𝑤𝑗, definida como un factor de prioridad que denota la importancia

relativa que tiene el trabajo respecto a los demás en el sistema y puede representar, por ejemplo, el costo actual de conservar el trabajo en la línea, asociado al costo de mantenimiento de inventario o al valor que se ha agregado al producto [6, 1]. Una secuencia se considera factible si no existen dos intervalos de tiempo que se sobrepongan en la misma máquina o en el mismo trabajo y si, adicionalmente, se cumplen una serie de restricciones propias del problema bajo estudio [5]. Una secuencia se considera óptima si se consigue con ella minimizar o maximizar un criterio dado. Ahora bien, durante los últimos cincuenta años [6] una cantidad considerable de investigaciones se ha focalizado en la programación determinística. Durante este tiempo, la notación de los problemas ha evolucionado para capturar la estructura de muchos (pero sin duda no todos) los modelos de este tipo que se consideran en la literatura. Un problema de Scheduling se describe por un triplete 𝛼|𝛽|𝛾 [6], clasificación que fue introducida por primera vez por Graham et ál. [7]. El primer campo, describe el ambiente de máquinas y contiene una sola entrada. El campo 𝛽 provee detalles sobre las características de procesamiento y las restricciones consideradas, por lo que puede contener ninguna, una o múltiples entradas.

Por último, el campo 𝛾 describe la función objetivo. A lo largo de los siguientes numerales se explorarán las diferentes características que se incluyen en estos campos. 1.2.3 Entornos de Máquinas

El ambiente de máquinas se caracteriza por un arreglo 𝛼 = 𝛼1𝛼2 de dos parámetros [5], que se integran de la siguiente manera. Si 𝛼1 = 1, el modelo es de una sola máquina e indica que el trabajo 𝑗 consiste de una única operación. Estos modelos son importantes en métodos de descomposición, los cuales son aplicados en escenarios complejos de máquinas donde la solución de un problema de Scheduling requiere desintegrar el ambiente en un modelo de máquinas individuales, en el que el hallazgo de una solución se logre con mayor facilidad [1]. Los modelos de una sola máquina han sido ampliamente analizados, bajo varias condiciones y con funciones objetivo diferentes. El resultado es un

~ 22 ~

conjunto de reglas, que además de ser fáciles de identificar y aplicar, ofrecen a menudo soluciones óptimas para este tipo de ambientes [1]. Por ejemplo, la regla de la menor fecha de entrega primero, Earliest Due Date first (EDD), la cual ordena los trabajos en orden ascendente de fechas de entrega, ha sido aplicada para minimizar el retraso máximo de todos los trabajos y la regla del menor tiempo de procesamiento primero, Shortest Processing Time first (SPT) ha sido utilizada para minimizar el número promedio de trabajos esperando para ser procesados. De otro lado, si 𝛼1 ∈ {𝑃, 𝑄, 𝑅} el sistema es de máquinas en paralelo. Este tipo

de modelos son el centro de la investigación a desarrollar y se consideran como una generalización del modelo de una sola máquina. Muchos sistemas de manufactura consisten en un número determinado de estaciones de trabajo ubicados en serie, dentro de los cuales se disponen cierta cantidad de máquinas en paralelo, las cuales suelen ser idénticas de manera que los trabajos puedan procesarse en cualquiera de las máquinas disponibles [1]. Esta característica aumenta el rendimiento y la capacidad de la planta, balancea la velocidad de las estaciones y elimina o reduce el impacto de los cuellos de botella a lo largo de toda la línea [8]. Este tipo de modelos son importantes, dado que si una estación es un cuello de botella, entonces la programación de dicha celda determinará el rendimiento de todo el sistema [1]. En busca de buenas soluciones a esta problemática, la estación puede ser modelada como un grupo de máquinas en paralelo y analizarse separadamente. En algunos casos, las máquinas ubicadas en paralelo pueden no ser exactamente idénticas. Esto se debe a que algunas pueden ser más antiguas que otras y trabajar a velocidades menores o pueden estar en mejores condiciones por lo que son capaces de realizar un trabajo de mayor calidad. Si se presenta esta situación, entonces algunos trabajos pueden ser procesados en cualquiera de las 𝑚 máquinas, mientras que otros podrán llevarse a cabo en

grupos específicos de las 𝑚 máquinas [1]. Las variantes que pueden presentarse son: Máquinas idénticas en paralelo (𝑃𝑚)

Se tienen 𝑚 máquinas idénticas en paralelo. El trabajo 𝑗 requiere una sola operación y puede ser procesado por cualquiera de las máquinas o en cualquiera de los recursos que haga parte de un conjunto específico 𝑀𝑗. Si este

último caso se presenta, la notación 𝑀𝑗 aparece en el campo 𝛽.

Máquinas en paralelo con diferentes velocidades (𝑄𝑚)

Se tienen 𝑚 máquinas en paralelo con velocidades heterogéneas. La velocidad de la máquina 𝑖 se denota como 𝑣𝑖. El tiempo 𝑝𝑖𝑗 que el trabajo 𝑗 pasa en la

~ 23 ~

máquina 𝑖 es igual a 𝑝𝑗

𝑣𝑖⁄ , asumiendo que el trabajo 𝑗 recibe todo su

procesamiento de la máquina 𝑖 [6]. Máquinas no relacionadas ubicadas en Paralelo (𝑅𝑚)

En este escenario, elegido para la investigación, se tienen 𝑚 máquinas

diferentes en paralelo. La máquina 𝑖 puede procesar el trabajo 𝑗 a una velocidad 𝑣𝑖𝑗. El tiempo 𝑝𝑖𝑗 que el trabajo 𝑗 pasa en la máquina 𝑖 es igual a 𝑝𝑗

𝑣𝑖𝑗⁄ , una vez más, asumiendo que el trabajo 𝑗 recibe todo su procesamiento

de la máquina 𝑖 [6].

Por su parte y de acuerdo con Brucker (2007) si 𝛼1 = 𝑃𝑀𝑃𝑀 o 𝛼1 = 𝑄𝑀𝑃𝑀, el escenario es de máquinas multipropósito con velocidades idénticas y uniformes, respectivamente. Ahora bien, en muchos ambientes de manufactura y ensamble los trabajos deben someterse a una serie de operaciones en diferentes máquinas;

dependiendo de la manera en que fluyen a lo largo de la línea, 𝛼1 puede tomar los símbolos 𝐺, 𝑋, 𝑂, 𝐽 ó 𝐹. El modelo general o General Shop representa un escenario donde cada

trabajo tiene asociado un conjunto de operaciones 𝑂𝑗1, …𝑂𝑗𝑛𝑗, las máquinas son

especializadas, es decir, todos los 𝜇𝑖𝑗 son conjuntos de un elemento y además,

existen relaciones de precedencia entre operaciones arbitrarias. En este caso

𝛼1 es igual a 𝐺. Ambientes especiales de este modelo general son el Job Shop, Flow Shop, Open Shop y Mixed Shop. El primero, indicado por 𝛼1 = 𝐽𝑚 , representa un escenario en donde cada trabajo tiene su propia ruta predeterminada a lo largo de toda la línea y se tiene una relación de precedencia especial de la forma:

𝑂𝑗1 → 𝑂𝑗2 → ⋯ → 𝑂𝑗𝑛𝑗 para todo 𝑗 = 1,… , 𝑛 [5]. Además, puede distinguirse

entre los escenarios donde cada trabajo visita cada máquina a lo sumo una vez y aquellos en los que es posible hacerlo múltiples veces, lo que se conoce en la literatura como recirculación. La generalización de este modelo y el escenario

de máquinas en paralelo se conoce como Flexible Job Shop, en este caso 𝛼1 es igual a 𝐹𝐽𝑐 y en lugar de encontrarse 𝑚 máquinas en serie, se ubican 𝑐 centros de trabajo, cada uno equipado con un número específico de recursos en paralelo.

De otro lado, en el modelo Flow Shop para el que 𝛼1 = 𝐹𝑚, los trabajos siguen la misma ruta de procesamiento, por lo que por ejemplo, todos pueden visitar la máquina 1, luego la 2 y así sucesivamente hasta finalizar su recorrido por la línea, tal como se muestra en la siguiente imagen. Las máquinas están organizadas en serie y cada vez que se completa una etapa del trabajo en una máquina, este se une a la cola de la siguiente. De acuerdo con Pinedo (2008), la secuencia de trabajos puede variar de una máquina a otra, puesto que los

~ 24 ~

trabajos pueden volver a programarse entre ellas. Sin embargo, si existe un sistema de transporte o manejo de materiales, que lleve el producto de una máquina a otra como ocurre en sistemas flexibles de manufactura, la secuencia se mantiene a lo largo de la línea.

Gráfico 1.5. Flow Shop Scheduling

Fuente: Tomado de: Ramírez, C. 2009.

La generalización de este ambiente y los escenarios de máquinas en paralelo, se ha elegido como tema de estudio en esta investigación y es conocido en la literatura como Flexible Flow Shop, cuyo comportamiento se muestra en la

siguiente figura. En este caso 𝛼1 = 𝐹𝐹𝑐 y en lugar de contar con 𝑚 máquinas en serie, se tienen 𝑐 centros de trabajo dispuestos de esta manera, cada uno equipado con una determinada cantidad de máquinas en paralelo. En cada etapa, el trabajo 𝑗 requiere procesamiento en solo una de las máquinas disponibles, el cual puede ser ejecutado por cualquiera de ellas. En algunos escenarios Flexible Flow Shop, un trabajo puede evitar una máquina o estación de trabajo si no requiere procesamiento en ella y puede adelantar a los demás trabajos que están siendo procesados o esperando a ser elaborados en dicha celda. Otros escenarios, sin embargo, pueden no permitir este tipo de comportamiento [1].

Gráfico 1.6. Flexible Flow Shop

Fuente: Elaboración propia. Adaptado de: Pinedo, Michael. 2005.

~ 25 ~

Por su parte, en el Open Shop 𝛼1 toma el indicador 𝑂𝑚 y representa un ambiente donde no existen restricciones en torno a la ruta que debe seguir cada trabajo en su recorrido por la línea de manufactura. Por tanto, el programador puede determinar libremente el camino de cada uno. La combinación de este escenario y el ambiente Job Shop se conoce en la

literatura como Mixed Shop y en este caso 𝛼1 es igual a 𝑋𝑚. Finalmente y de acuerdo con Brucker (2007), 𝛼2 denota la cantidad de

máquinas bajo estudio. Si 𝛼2 = 𝑘, entonces 𝑘 es un número arbitrario pero fijo de recursos. Por el contrario, si 𝛼2 = ∘, lo que representa una condición de vacío, el número es arbitrario. 1.2.4 Características de Procesamiento

Las características particulares de la línea son contenidas en el campo 𝛽, que se encuentra integrado a lo sumo por seis elementos [5]. El primero de ellos indica si se aceptan o no interrupciones en la ejecución de un trabajo ocasionadas por el arribo de tareas de mayor importancia, tras las que se reanuda su fabricación en cualquier máquina. Esto es lo que se conoce en la literatura como preemptions. En este caso, 𝛽1 es igual a 𝑝𝑚𝑡𝑛 y

de no admitirse, 𝛽1 no se incluye en el campo 𝛽.

Por su parte, 𝛽2 describe las relaciones de precedencia entre los trabajos, que pueden representarse como un grafo direccionado no cíclico 𝐺 = (𝑉, 𝐴), donde 𝑉 = {1, … , 𝑛} corresponde a los trabajos y (𝑗, 𝑘) ∈ 𝐴 si el trabajo 𝑗 debe

completarse antes que 𝑘 inicie, lo que se simboliza como 𝑗 → 𝑘. Si esto sucede 𝛽2 es igual a prec. Existen varias formas de restricciones de precedencia: si

cada trabajo tiene como máximo un predecesor y a lo sumo un sucesor, las restricciones se denominan chains; si cada trabajo tiene únicamente un sucesor, estas limitantes se conocen como intree, mientras que si cada trabajo tiene sólo un predecesor se llaman outtree. En caso que no existan

restricciones de precedencia, 𝛽2 no aparece en el campo 𝛽. Asociados a estas relaciones, Pinedo (2008) establece que pueden incluirse en el campo 𝛽, tiempos de alistamiento dependientes de la secuencia, 𝑠𝑗𝑘 que

representan la cantidad de tiempo requerido entre el procesamiento de los

trabajos 𝑗 y 𝑘; 𝑠0𝑘 denota el tiempo de alistamiento del trabajo 𝑘 cuando éste es el primero de la secuencia y 𝑠𝑗0 el tiempo de limpieza después del trabajo 𝑗,

cuando éste es el último. El autor afirma que si 𝑠𝑗𝑘 no aparece en el campo 𝛽,

todos los tiempos de alistamiento se suponen 0 o independientes de la secuencia, en cuyo caso se incluyen simplemente en los tiempos de procesamiento. Si 𝛽3 = 𝑟𝑗, se incluyen en el escenario fechas de arribo al sistema para cada

trabajo. Si 𝑟𝑗 = 0 en todos los casos, 𝛽3 no se incluye en el campo 𝛽.

~ 26 ~

De otro lado, 𝛽4 especifica las restricciones en los tiempos de procesamiento o en el número de operaciones de los trabajos. Si 𝛽4 = 𝑝𝑗 =

1 (𝑝𝑖𝑗 = 1), entonces cada trabajo (operación) tiene un requerimiento de una

unidad. Adicionalmente, si 𝛽5 = 𝑑𝑗, entonces se han especificado fechas de entrega

para cada producto terminado, tras las que se incurre en una penalización por incumplimiento. Tal como sucede con 𝛽3, si 𝑑𝑗 = 0 en todos los casos, 𝛽5

no se incluye en el campo 𝛽. Finalmente, en algunas aplicaciones de Scheduling los trabajos pueden agruparse en lotes que deben procesarse de forma conjunta en una máquina. El tiempo de finalización de las tareas dentro de un lote se define como el

momento en que se completa todo el grupo, cuyo tamaño varía entre 1 y 𝑛. Adicionalmente, se asume un tiempo de alistamiento para cada conjunto. Los problemas de loteo o batching problems consisten en agrupar correctamente las tareas y programar eficientemente la fabricación de dichos lotes y pueden clasificarse en dos categorías: p-batching problems o s-batching problems. Si estos escenarios se incluyen en el problema bajo análisis, dicha clasificación

corresponde a 𝛽6, en caso contrario se omite del campo 𝛽. De acuerdo con Pinedo (2008), otros criterios que pueden incluirse en el campo 𝛽 incluyen paradas de máquinas o breakdowns, conocidas como

restricciones de disponibilidad de las máquinas, que se escriben como 𝛽 =𝑏𝑟𝑘𝑑𝑤𝑛 y que se encuentran referidas a escenarios en los que los recursos no se encuentran continuamente disponibles, así como las restricciones en la elegibilidad de máquinas, en cuyo caso 𝛽 = 𝑀𝑗, haciendo referencia a

escenarios de máquinas en paralelo en los que no todos los recursos son capaces de procesar el trabajo 𝑗. El conjunto 𝑀𝑗 corresponde al grupo de

máquinas que pueden realizar estas operaciones. Si el campo 𝛽 no contiene

esta restricción, el trabajo 𝑗 puede manufacturarse en cualquiera de ellas. Del mismo modo, el campo 𝛽 puede incluir variaciones como el requerimiento

no-wait, que se escribe como 𝛽 = 𝑛𝑤𝑡 y que impide que los trabajos esperen entre dos máquinas sucesivas, lo que implica que el tiempo de inicio de un trabajo tiene que retrasarse para asegurar que pueda fluir sin demoras a lo largo de toda la línea, así como la opción de recirculación donde 𝛽 = 𝑟𝑐𝑟𝑐, en la que un trabajo puede visitar una máquina o estación de trabajo más de una vez. 1.2.5 Criterio de Optimización

El objetivo a minimizar es usualmente, según Pinedo (2008), una función del tiempo en que se finalizan todos los trabajos, lo que por supuesto, depende de la secuencia construida.

~ 27 ~

Dentro de las funciones objetivo más comunes que se incluyen en el campo 𝛾 se pueden encontrar el makespan (𝑪𝒎á𝒙), definido como Máx {𝐶1, … , 𝐶𝑛} y

equivalente al tiempo en que el último trabajo abandona el sistema, el tiempo

de flujo total (∑ 𝑪𝒋𝒏𝒋=𝟏 ), el tiempo de finalización total

ponderado (∑ 𝒘𝒋𝑪𝒋𝒏𝒋=𝟏 ), que a diferencia del anterior involucra un factor de

importancia relativa de cada trabajo respecto a los demás y provee una indicación de los costos de mantenimiento de inventario en los que se incurre

con la secuencia y el máximo retraso (𝑳𝒎á𝒙), que mide la peor violación en las fechas de entrega y para la que las demoras de cada trabajo se definen como la diferencia entre su finalización y la fecha de entrega pactada con el cliente, es decir: 𝐿𝑗: 𝐶𝑗 − 𝑑𝑗.

Otras funciones objetivo que se relacionan con esta fecha definen para los trabajos las siguientes métricas: 𝐸𝑗: Máx {0, 𝑑𝑗 − 𝐶𝑗} Adelanto

𝑇𝑗:Máx {0, 𝐶𝑗 − 𝑑𝑗} Tardanza

𝐷𝑗: |𝐶𝑗 − 𝑑𝑗| Desviación absoluta

𝑆𝑗: (𝐶𝑗 − 𝑑𝑗)2 Desviación cuadrada

𝑈𝑗: {0 Si 𝐶𝑗 ≤ 𝑑𝑗

1 en otro caso Penalización unitaria.

Con ellas, es posible construir otras funciones objetivo ampliamente usadas como ∑𝑇𝑗, ∑𝑤𝑗𝑇𝑗, ∑𝑈𝑗, ∑𝑤𝑗𝑈𝑗 , ∑𝐷𝑗, ∑𝑤𝑗𝐷𝑗, ∑𝑆𝑗, ∑𝑤𝑗𝑆𝑗 , ∑𝐸𝑗, ∑𝑤𝑗𝐸𝑗 [5], así

como sus combinaciones lineales. De acuerdo con Brucker (2007), una función objetivo que es no decreciente respecto a todas las variables 𝐶𝑗 se denomina regular, mientras que las

funciones que involucran 𝐸𝑗, 𝐷𝑗 o 𝑆𝑗 son no regulares.

Según el mismo autor, una secuencia es activa si no es posible programar las tareas (operaciones) con anterioridad sin violar alguna restricción, mientras que se denomina semi-activa si ninguna tarea (operación) puede ser procesada anticipadamente sin cambiar el orden de procesamiento o quebrantar alguna limitante. 1.2.6 Aplicación de este dominio de conocimiento en el desarrollo de la

investigación Las generalidades del problema de Scheduling abordadas en los numerales previos, constituyen la base de la investigación a desarrollar, debido a que para entender las particularidades estudiadas en este proyecto, se hace necesario contextualizar el problema en un ambiente más amplio comprendiendo las formas en que se ha elaborado la programación en el pasado para analizar los sistemas actuales y encontrar maneras de mejorarlos, así como identificar los campos de aplicación que justifican su estudio hoy en día. Esta revisión se

~ 28 ~

considera de suma importancia además, para unificar criterios y determinar la notación formal a emplear a lo largo de todo el proyecto. 1.3 ACEPTACIÓN DE ÓRDENES Y SCHEDULING

En los problemas tradicionales de Scheduling, todas las órdenes o trabajos que arriban al sistema deben ser procesados. Sin embargo, en condiciones reales y debido a la limitada capacidad disponible, el fabricante puede rechazar algunos de los pedidos que recibe [9], por ejemplo, en casos donde se requieren materias primas especializadas o trabajadores con habilidades particulares y que además, brindan poco margen de utilidad. En estos escenarios y con el fin de reducir costos y garantizar altos ingresos, los fabricantes evalúan la conveniencia general de los pedidos recibidos y posteriormente rechazan aquellos que no son favorables para el negocio. Esto se debe a que aceptar órdenes sin considerar su impacto en la capacidad productiva puede causar sobrecargas en algunos periodos, retrasando las órdenes más allá de la fecha de entrega pactada con el cliente, incurriéndose en una penalización por dicha tardanza y ocasionando pérdidas en los ingresos a largo plazo, debido a la insatisfacción de los clientes [10]. Es de notar, que estos descensos en la imagen corporativa son letales especialmente en un mercado globalizado y competitivo como en el que se llevan a cabo los negocios en la actualidad. Este problema, denominado en la literatura como Aceptación de Órdenes y Scheduling (OAS) o Scheduling admitiendo rechazos (MSR), ha atraído una atención considerable en las últimas décadas, tanto desde el punto de vista académico como de gerentes de producción que practican el Scheduling [11]. La mayoría de las investigaciones relacionadas consideran escenarios de una sola máquina difiriendo de la configuración bajo análisis [12]. Slotnick y Morton [13] y Gosh [14] son considerados pioneros [12] en estudiar este problema, en el que consideraron una función objetivo que maximizara las utilidades totales. Lewis y Slotnick [15] extendieron el escenario incorporando varios periodos de decisión y suponiendo que rechazar una orden de un cliente llevaría a la pérdida de todos sus pedidos futuros. Con el nombre de Scheduling admitiendo rechazos, se considera como precursores [9] a Bartal et ál. [16], quienes optaron por una función objetivo que minimizara el makespan y los costos de penalización asociados a las órdenes rechazadas. A partir de allí, en las últimas dos décadas varios problemas con diferentes características y funciones objetivo han sido estudiados. En términos de las herramientas empleadas para su solución, autores como Lewis y Slotnick [15], Engels et ál. [17], Charnsirisakskul, Griffin y Keskinocak [18, 19], Slotnick y Morton [20], Lee y Sung [21], Oğuz, Salman y Yalçın [22], Nobibon y Leus [23] y Wang, Xie y Cheng [12] han desarrollado heurísticas miopes y enfoques exactos tales como Branch and Bound, programación dinámica y modelos de programación entera y entera mixta.

~ 29 ~

Sin embargo y debido a su carácter NP-Hard, este tipo de algoritmos sólo pueden suministrar una solución a problemas de pequeña escala. Por ello, las investigaciones se han orientado hacia la búsqueda de heurísticas de aproximación eficientes para encontrar soluciones cercanas al óptimo en tiempos computacionalmente razonables. Muchas herramientas de este tipo han probado su robustez en alcanzar buenas soluciones y resolver las limitaciones de los métodos exactos [24, 25]. De acuerdo con Lin y Ying [26], las heurísticas de aproximación disponibles actualmente para resolver este tipo de problemas, pueden clasificarse en dos categorías: heurísticas constructivas (CHs) y heurísticas de mejoramiento (IHs). Dentro del primer grupo, se encuentran aquellas desarrolladas por autores como Kyparisis et ál. [27], Lewis y Slotnick [15], Engels et ál. [17], Yang y Geunes [28], Lee y Sung [21], Oğuz, Salman y Yalçın [22], Cesaret, Oğuz y Salman [10] y Xiao et ál. [29], que añaden órdenes una a una y examinan el efecto de cada adición sobre la función objetivo. Cuando una orden ha sido aceptada y programada, se fija, por lo que no puede rechazarse posteriormente. De acuerdo con los aportes de Lin y Ying [26], dentro de las heurísticas disponibles en esta categoría, la combinación de las reglas WSPT o tiempo de procesamiento ponderado más corto y DD o due date, propuesta por Xiao et ál. [29], es uno de los mejores enfoques, en la que se toma la decisión respecto a los pedidos a aceptar con base en el orden creciente del tiempo de procesamiento ponderado, mientras que la programación de los trabajos aceptados se realiza respecto al orden creciente de fechas de entrega. Sin embargo, una característica común de estas herramientas es la poca robustez de sus soluciones y aunque llegan a ellas de una manera rápida, no existe una heurística particular que tenga mejor desempeño que las demás para todos los problemas teniendo en cuenta una función objetivo y ambiente de manufactura específicos. Adicionalmente, la calidad de los resultados obtenidos no siempre es tan buena como se espera, sobre todo en instancias de gran tamaño [30]. De otro lado, las heurísticas de mejoramiento como las desarrolladas por Akkan [31], Lewis y Slotnick [15], Yang y Geunes [28], Slotnick y Morton [20], Cesaret, Oğuz y Salman [10] y Xiao et ál. [29], empiezan con una solución inicial que es luego iterativamente mejorada hasta encontrar una solución lo más cercana al óptimo posible. En décadas recientes, el desarrollo de metaheurísticas basadas en estas herramientas ha atraído gran atención tanto desde la academia como la industria. Algunas de las empleadas para resolver el problema de Aceptación de Órdenes y Scheduling incluyen optimización extrema [32], recocido simulado [22, 29, 33, 34], búsqueda tabú [10], colonia de hormigas [35, 12], algoritmo evolutivo de gotas de agua [9] y la elegida para esta investigación, algoritmos genéticos [33, 32, 36]. Los resultados experimentales de estas investigaciones han demostrado que estas herramientas proveen resultados satisfactorios para varios tipos de problemas en el escenario de Scheduling aceptando rechazos; sin embargo, la mayoría de los estudios se han enfocado en ambientes de una sola máquina [26].

~ 30 ~

El lector puede remitirse a autores como Keskinocak y Tayur [37] y Slotnick [30], quienes realizan una revisión y taxonomía detallada relacionada con los modelos y heurísticas disponibles para resolver varios tipos de problemas en este escenario. 1.4 ALGORITMOS GENÉTICOS

La teoría de la selección natural formulada por Charles Darwin en 1859 [38] propone que las plantas y animales que existen en la actualidad, son el resultado de millones de años de adaptación a las demandas de su entorno. Darwin observó que en un momento dado del tiempo, diferentes organismos que conviven en un ecosistema compiten con otros por recursos limitados como comida, agua, abrigo y hasta una pareja para su reproducción y que como resultado de estos enfrentamientos constantes, solo aquellos individuos que pudieran conseguir dichos recursos tendrían numerosos sucesores en el futuro, mientras que los que no lo hicieran, tendrían menor o ninguna descendencia. De acuerdo con Sivanandam y Deepa (2008), de los primeros se dice que están mejor adaptados que los segundos y las características distintivas que los hacen mejores se conocen como propiedades de selección. Así mismo, Darwin se percató que después de varias generaciones, toda la población evoluciona para contener organismos que, en promedio, se encuentran mejor acondicionados que sus antepasados [3], esto debido a que ostentan más de aquellas características que promueven la supervivencia. Las técnicas de computación evolutiva (EC) abstraen estos principios en algoritmos que pueden ser empleados en la búsqueda de soluciones óptimas a un problema a través de la evaluación de un número de posibles soluciones en un intervalo fijo de tiempo. Dentro de un espacio de búsqueda reducido, todas las soluciones pueden examinarse en un lapso razonable de tiempo y es posible encontrar una respuesta óptima. Sin embargo, esta búsqueda exhaustiva fácilmente se torna impráctica a medida que aumenta el tamaño de dicho espacio. Los algoritmos de búsqueda tradicionales toman una solución aleatoria (paseo aleatorio o random walk) o heurística (gradiente descendente), con la esperanza de encontrar una solución óptima. El aspecto que distingue estas herramientas de un algoritmo de búsqueda evolutivo es que este se fundamenta en una población y a través de la adaptación de generaciones sucesivas de un número extenso de individuos, realiza una búsqueda direccionada eficiente. La computación evolutiva comenzó tomando ideas de la teoría biológica de la evolución, involucrándolas con las ciencias computacionales y aún hoy continúa buscando inspiración a través de las nuevas investigaciones que se desarrollan en esa área del conocimiento. Como resultado, se han formulado cuatro grandes paradigmas que sirven de base a gran parte de la actividad desarrollada en la materia: los algoritmos genéticos (Holland, 1975), programación genética (Koza, 1992, 1994), estrategias evolutivas

~ 31 ~

(Recheuberg, 1973) y programación evolutiva (Forgel et ál. 1966). La diferencia fundamental que existe entre ellos recae en la naturaleza de los esquemas de representación, los operadores de reproducción y los métodos de selección. Por ser el principal objeto de estudio, en los siguientes numerales se presenta una breve referencia en torno a los algoritmos genéticos. 1.4.1 La teoría de Holland

En 1975, John Holland [39] presentó su libro “Adaptation in natural and artificial systems”, con el objetivo principal de estudiar formalmente el fenómeno de adaptación tal como ocurre en la naturaleza y desarrollar formas en las que los mecanismos de la selección natural de Darwin podían incorporarse en los sistemas computacionales. Bajo los preceptos de la genética y la evolución, formuló el primer algoritmo genético (GA). Su teoría, ha sido ampliamente desarrollada, convirtiéndose en la actualidad en una herramienta poderosa para resolver problemas de búsqueda y optimización. Los Algoritmos Genéticos involucran un par de características importantes. Primero, es un algoritmo estocástico, en el que los procesos de selección y reproducción siguen procedimientos al azar, por lo que la aleatoriedad juega un rol fundamental en su construcción. En segundo lugar, siempre consideran una población de soluciones, por lo que el algoritmo puede recombinar diferentes respuestas para alcanzar unas mejores y así, emplear los beneficios de la variedad. La robustez del algoritmo es una propiedad que debe mencionarse como un factor esencial para su éxito y se refiere a la habilidad para ejecutarse de forma consistente en una amplia gama de problemas; en este sentido, no existe un requerimiento particular sobre el escenario antes de emplear el algoritmo, por lo que pueden aplicarse para resolver cualquier situación. Estas características, hacen de los Algoritmos Genéticos una herramienta de optimización realmente poderosa [3]. Sin embargo, se considera crucial mencionar los límites de los Algoritmos Genéticos. El más importante es que, como con muchos métodos estocásticos, no es posible garantizar que se encontrará la solución óptima global, sino respuestas “aceptablemente buenas” al problema bajo estudio. Además, son extremadamente generales, por lo que algunas técnicas especializadas para resolver problemas particulares pueden tener un mejor desempeño tanto en velocidad como en calidad del resultado final [3]. En este caso, es a menudo interesante combinar ambos enfoques con el fin de obtener posiblemente algunas mejoras. Es primordial mantener siempre un punto de vista objetivo y no considerar que estos algoritmos son la panacea para resolver cualquier tipo de problemas de optimización, sino herramientas que proveen buenos resultados si se aplican correctamente a los problemas adecuados. Según Sivanandam y Deepa (2008) los Algoritmos Genéticos difieren de las técnicas de optimización convencionales en cuatro aspectos fundamentales. Primero, operan con versiones codificadas de los parámetros del problema analizado y no con los parámetros en sí mismos. Segundo, la mayoría de

~ 32 ~

técnicas tradicionales realizan la búsqueda a partir de una única solución, mientras que los Algoritmos Genéticos usan una población de soluciones, lo que juega un papel fundamental en su robustez, además de incrementar la posibilidad de alcanzar el óptimo global y evitar puntos locales. Así mismo, los Algoritmos Genéticos usan una función de aptitud para la evaluación de las soluciones en lugar de derivadas. Como resultado, pueden aplicarse a cualquier tipo de problema de optimización continua o discreta. Finalmente, los Algoritmos Genéticos emplean operadores de transición probabilísticos mientras que los métodos convencionales empleados en optimización continua aplican operadores de transición determinísticos. En pocas palabras, los Algoritmos Genéticos no usan reglas de carácter determinístico. 1.4.2 Terminología y Operadores de los Algoritmos Genéticos

Los Algoritmos Genéticos emplean una metáfora en la que el problema de optimización que se quiere resolver toma el lugar del ecosistema y sus soluciones factibles son consideradas individuos que habitan dicho entorno, los cuales generalmente, son dígitos binarios u otra colección de símbolos diseñados a partir de un conjunto finito, que conforman una representación de una solución particular al problema. Para que el algoritmo encuentre una buena respuesta, es necesario realizar ciertas operaciones sobre estos organismos. Los siguientes numerales abordan la terminología básica y los operadores genéticos empleados para alcanzar la mejor solución posible en los términos de los criterios de parada. 1.4.2.1 Elementos Clave

Los dos elementos distintivos de los Algoritmos Genéticos son los individuos o soluciones únicas al problema bajo análisis y las poblaciones, o grupos de dichos organismos que se encuentran involucrados en el proceso de búsqueda. De acuerdo con Sivanandam y Deepa (2008), los individuos agrupan dos formas de solución: El cromosoma, que es la información “genética” básica (genotipo) con que trabaja el algoritmo y el fenotipo que caracteriza el cromosoma en los términos del modelo. Un cromosoma se encuentra dividido en genes, que son la representación de un factor de control único. Cada factor en la solución corresponde a un gen en el cromosoma, tal como se muestra en la siguiente figura.

~ 33 ~

Gráfico 1.7. Representación del Genotipo y Fenotipo

Fuente: Elaboración Propia. Adaptado de: Sivanandam y Deepa, 2008.

De alguna manera, el cromosoma debe contener la información relacionada con la respuesta que representa. La función de morfogénesis asocia cada genotipo con su fenotipo y significa simplemente que cada cromosoma debe definir una única solución, pero no que cada solución deba estar codificada exactamente por un cromosoma. En efecto, la función de morfogénesis no es necesariamente biyectiva y es algunas veces imposible que lo sea, especialmente con una representación binaria; no obstante, debe por lo menos garantizar que todas las soluciones candidatas correspondan al menos con un cromosoma, para asegurarse que todo el espacio de búsqueda sea considerado. Cuando esta función no es inyectiva, es decir, cuando diferentes cromosomas codifican la misma solución, se dice que la representación es degenerada [3]. De acuerdo con Sivanandam y Deepa (2008), un pequeño grado de degeneración no es tan preocupante, incluso si el espacio de búsqueda se hace inevitablemente más grande; sin embargo, una degeneración demasiado importante puede ser un problema serio, en tanto que afecta negativamente el comportamiento del algoritmo, principalmente porque puede agregar algún tipo de confusión a la búsqueda. De otro lado, una población es una colección de individuos que son puestos a prueba e involucra alguna información relacionada con el espacio de búsqueda. Los dos aspectos importantes para los Algoritmos Genéticos en este aspecto son la generación de la población inicial y el tamaño. Para cada problema, el tamaño de la población dependerá de su complejidad. Idealmente, la primera población debería tener un conjunto de genes tan largo como sea posible de manera que se pueda explorar todo el espacio de búsqueda. Normalmente, se emplea una generación aleatoria de los individuos, pero en algunos casos se emplea un método heurístico para cimentarla, haciendo que en promedio, su adaptación sea más alta y se facilite el hallazgo de buenas soluciones. Sin embargo, debe asegurarse que el conjunto de genes siga siendo muy amplio ya que en caso contrario faltaría diversidad en la población, haciendo imposible encontrar la solución óptima.

~ 34 ~

El tamaño de la población representa también algunos problemas, ya que aunque a medida que sea más grande, más fácil se hace explorar el espacio de búsqueda, se ha establecido que el tiempo que tarda un Algoritmo Genético en converger es 𝑶(𝒏𝐋𝐨𝐠𝒏) evaluaciones, siendo 𝑛 el tamaño de la población y que la eficiencia del algoritmo para encontrar el óptimo global en lugar de óptimos locales está altamente determinada por este criterio [40]. En conclusión, aunque una población numerosa es bastante útil, requiere mucho más costo, memoria y tiempo computacional. En la práctica, un tamaño de población de alrededor de 100 individuos es bastante frecuente [3], pero puede modificarse teniendo en cuenta la memoria disponible en la máquina y la calidad de soluciones buscada. A continuación se muestra la manera como se combinan cuatro cromosomas para configurar una población.

Población

Cromosoma 1 1 1 1 0 0 0 1 0

Cromosoma 2 0 1 1 1 1 0 1 1

Cromosoma 3 1 0 1 0 1 0 1 0

Cromosoma 4 1 1 0 0 1 1 0 0 Gráfico 1.8. Población

Fuente: Elaboración Propia. Adaptado de: Sivanandam y Deepa, 2008. 1.4.2.2 Genes Los genes son las “instrucciones” básicas para construir los Algoritmos Genéticos. Un cromosoma es una secuencia de genes que pueden describir una posible solución al problema, sin ser realmente la solución [3]. Es una cadena de bits de longitudes arbitrarias, que, usualmente, son una representación binaria del valor de un único factor de control, que debe tener un límite superior y un límite inferior. Este rango puede dividirse en el número de intervalos que pueden expresarse por la cadena de bits del gen. Una cadena de bits de longitud “𝑛” puede representar 2𝑛 − 1 intervalos. El tamaño

del intervalo será [𝑟𝑎𝑛𝑔𝑜]/(2𝑛 − 1 ). La estructura de cada gen se define en un registro de parámetros fenotípicos, instrucciones para la interacción entre el genotipo y el fenotipo, de los que también se puede decir que codifican una solución dentro de un cromosoma y decodifican el cromosoma en una solución. La interacción entre ellos es necesaria para convertir una solución del modelo a una forma con la que el Algoritmo Genético pueda trabajar y para convertir nuevos individuos del algoritmo en una forma que pueda ser evaluada por el modelo. En un cromosoma los genes son representados tal como se muestra en la siguiente figura.

~ 35 ~

Gráfico 1.9. Representación de un gen


1.4.2.3 Funciones de Evaluación y Aptitud En este contexto, es necesario diferenciar entre la función de evaluación y la función de fitness o adaptación usada por un algoritmo genético [41]. La función de evaluación o función objetivo, provee una medida del desempeño respecto a un conjunto particular de parámetros, mientras que la función de adaptación transforma esta medida en una asignación de oportunidades de reproducción. Es así como la evaluación de un arreglo que representa un conjunto de parámetros es independiente de la evaluación de otra cadena. Sin embargo, la adaptación de esa cadena está siempre definida respecto a los demás miembros de la población actual. La función de evaluación calcula el valor que toma la función objetivo con su fenotipo y debe ser diseñada para cada problema de manera específica. En el caso de problemas de optimización multicriterio, puede ser más difícil de determinar y es necesario tener cuidado de combinar los criterios de un modo consistente [3]. Por su parte, la adaptación o fitness es una muestra de la aptitud que tienen los individuos para sobrevivir [41]. Una vez se realiza la generación de una nueva población, el valor de adaptación (𝐹𝑘) de cada cromosoma es calculado y cuánto más alto sea, mejor será el desempeño del mismo. Por tanto, los individuos con mejores valores de adaptación tendrán más posibilidades de sobrevivir. 1.4.2.4 Creación de nuevos individuos. Los operadores genéticos. La reproducción es el corazón de los Algoritmos Genéticos. En este proceso, la búsqueda crea nuevos y con suerte mejores individuos. De acuerdo con Sivanandam y Deepa (2008), el ciclo consiste de tres etapas: seleccionar los padres, combinarlos para crear nuevos individuos y reemplazar la población de antecesores con la nueva generación. La selección se refiere al proceso de elegir dos padres de la población para cruzarlos. Después de diseñar un tipo de codificación, el siguiente paso es decidir cómo se seleccionarán los padres que crearán la descendencia para la siguiente generación y cuántos concebirán. El propósito de la selección es elegir buenos padres, de manera que sus sucesores estén mejor adaptados. Para ello, se escogen aleatoriamente dos cromosomas de la población, de acuerdo con la función de evaluación; entre más alto sea su valor, mayores probabilidades tiene un individuo de salir elegido. La presión de selección se

~ 36 ~

define como el grado en que los mejores individuos son favorecidos y guía al algoritmo a mejorar la adaptación de la población a lo largo de generaciones sucesivas [3]. La tasa de convergencia de la herramienta está altamente determinada por la magnitud de este criterio; si es demasiado bajo, la tasa de convergencia será lenta y el algoritmo tomará innecesariamente mayor tiempo para encontrar una solución óptima; si, por el contrario, es muy alta, existe una posibilidad creciente que el algoritmo converja prematuramente hacia óptimos locales. Adicionalmente, los esquemas de selección deben preservar la diversidad de la población, en la medida en que estos ayudan a evitar la convergencia prematura. Típicamente, es posible distinguir dos tipos de enfoque: la selección basada en proporciones, que elige los individuos de acuerdo con los valores de ajuste alcanzados y su relación con las cifras arrojadas por los demás individuos y la selección basada en ordinales, que los selecciona de acuerdo con su rango al interior de la población. Este proceso debe balancearse de forma adecuada, en tanto que medidas de selección demasiado fuertes concentrarán la población de individuos sub-óptimos altamente adaptados que reducen la diversidad necesaria para el progreso y el cambio de la población, mientras que una selección demasiado débil resultará en un proceso de evolución excesivamente lento. De otro lado, el cruce o recombinación es el proceso de tomar un par de soluciones padres para producir a partir de ellos un nuevo individuo. El proceso de selección enriquece la población con mejores individuos, clones de buenos arreglos, pero no diseña nuevos. Para ello, se aplica el operador de cruce, con la esperanza de mejorar la descendencia. Este proceso se lleva a cabo en tres etapas. Inicialmente, el operador selecciona un par de individuos para combinar, posteriormente, elige al azar un punto de corte dentro de sus cadenas de bits y finalmente, intercambia hasta este punto los valores de las dos cadenas, tal como se muestra en la siguiente imagen.

Gráfico 1.10. Operador de Cruce


~ 37 ~

En este aspecto, puede hacerse una distinción respecto al número de cortes que se realizan en el arreglo. Si se efectúa un único corte, como el que se muestra en la imagen, el operador se denomina single-point crossover, mientras que si involucra dos puntos, se convierte en two-point crossover. En caso que se realicen múltiples cortes, el operador se designa entonces como multi-point crossover. Es de notar, tal como lo mencionan Sivanandam y Deepa [3], que fragmentar más la cadena reduce el desempeño del algoritmo, debido a que los bloques de construcción son más propensos a quebrarse. Sin embargo, su ventaja radica en que el espacio del problema puede examinarse más exhaustivamente. El lector puede remitirse a los autores mencionados para estudiar otras formas de realizar cruces en los Algoritmos Genéticos. El parámetro básico para implementar este operador es la probabilidad de

cruce, 𝑃𝑐, que describe la frecuencia con que se ejecuta dentro del algoritmo. Si toma un valor del 100%, toda la descendencia será sometida a cruce, mientras que si se establece en 0%, los nuevos individuos serán copias exactas de los cromosomas de la población antecesora, lo cual no significa que la población sea la misma. El operador de cruce se efectúa con la esperanza que nuevos cromosomas contengan buenas partes de sus padres y por tanto, sean mejores. Sin embargo, es bueno dejar que individuos de la generación antecesora sobrevivan para la siguiente población. Después del cruce, los arreglos son sometidos a mutación, con el objetivo de mantener la diversidad dentro de la población y prevenir la convergencia prematura. Se aplica a cada hijo de manera individual y consiste en la alteración aleatoria (normalmente con probabilidad pequeña) de cada gen, componente del cromosoma [42]. Es una póliza de seguros contra la pérdida irreversible de material genético y se ha considerado tradicionalmente como un simple operador de búsqueda [3]. Si el cruce se emplea para explotar la solución actual y encontrar mejores, la mutación ayuda a explorar todo el espacio de búsqueda. La siguiente imagen muestra cómo puede funcionar un operador de este tipo.

Gráfico 1.11. Operador de Mutación


~ 38 ~

Dependiendo del tipo de mutación que se realice y de la codificación elegida, se puede distinguir entre operadores de mutación de bit como el que se muestra en la figura o multi-bit, en los que se selecciona al azar uno o varios bits y se invierte su valor. Así mismo, existen mutaciones de gen o multi-gen donde en lugar de cambiarse un bit, se modifica el valor de un gen completo. También, puede emplearse un operador de mutación de intercambio o pairwise interchange que toma dos bits o genes y cambia su ubicación en la cadena de valores. De forma homogénea a como sucede con el cruce, el parámetro principal del operador es la probabilidad de mutación, 𝑃𝑚, que describe la frecuencia con que se ejecuta dentro del algoritmo. Si no existe mutación, la descendencia es generada inmediatamente después del cruce (o directamente copiada) sin ningún tipo de cambio. La mutación generalmente previene que la herramienta caiga en extremos locales, pero no debe ocurrir muy a menudo, porque esto ocasionaría que el algoritmo ejecutara una búsqueda aleatoria. El reemplazo es la última etapa de cualquier ciclo de reproducción. Dos padres son extraídos de una población de tamaño fijo y producen un nuevo individuo, pero los cuatro no pueden retornar a la población, así que dos deben ser reemplazados. Es decir, que una vez se genera la descendencia, un método debe determinar cuáles de los miembros actuales de la población, de ser el caso, deben reemplazarse por las nuevas soluciones. Para ello, puede optarse por un reemplazo aleatorio, en donde los hijos sustituyen dos individuos de la población (incluidos los padres) elegidos al azar; otro mecanismo es suplir un padre débil con un hijo fuerte, en cuyo caso el operador se denomina weak parent replacement. De esta manera, de los cuatro individuos solo los dos mejores adaptados retornan a la población. También puede elegirse simplemente un operador de reemplazo de ambos padres. En resumen, la interacción de estos elementos conforma el ciclo de un Algoritmo Genético, tal como se muestra a continuación.

~ 39 ~

Gráfico 1.12. Ciclo de los Algoritmos Genéticos

Fuente: Elaboración Propia. Adaptado de: Sivanandam y Deepa, 2008. 1.4.3 Terminación de la búsqueda. Criterios de convergencia. Usualmente y de acuerdo con Sivanandam y Deepa (2008), se definen cinco posibles condiciones de parada para el algoritmo. El primero, ocurre cuando al interior del procedimiento han evolucionado un número especificado de generaciones; también es común encontrar situaciones donde la herramienta se interrumpe una vez ha alcanzado un tiempo determinado de corrida, cuya elección debe ser suficiente para permitir al algoritmo encontrar una buena solución pero no tan extenso que consuma inútilmente mayor tiempo computacional. Normalmente, se involucra el criterio anterior para garantizar que esto ocurra, de manera que si se alcanza el número máximo de generaciones antes que este tiempo se cumpla, el procedimiento se detendrá. Así mismo, es común encontrar situaciones donde se suspende el algoritmo si no existe un cambio considerable en la función de adaptación, es decir, cuando no se encuentran mejores valores en la población por un número especificado de generaciones. Del mismo modo, puede interrumpirse la ejecución del algoritmo si no existen mejoras en los valores de la función objetivo para una secuencia de generaciones consecutivas de tamaño especificado, lo que se conoce en la literatura como stall generations. Este mismo concepto se emplea para detenerlo si no existen mejoras en la función objetivo durante un intervalo de segundos equivalente al límite de tiempo de parada o stall time limit.

~ 40 ~

En definitiva, los criterios de terminación o convergencia finalizan el proceso de búsqueda. A continuación se presentan los métodos extraídos por Sivanandam y Deepa (2008) que son empleados en las técnicas de terminación. 1.4.3.1 Mejor individuo Un criterio de convergencia fundamentado en el mejor individuo detiene la búsqueda una vez el mínimo valor de adaptación de la población cae por debajo del valor de convergencia. Esta situación lleva a la búsqueda a una conclusión rápida garantizando al menos una buena solución. 1.4.3.2 Peor individuo Este criterio termina la búsqueda cuando los individuos menos adaptados de la población alcanzan valores por debajo del criterio de convergencia. Esto garantiza que toda la población tenga un estándar mínimo, así el mejor individuo pueda no ser significativamente mejor que el peor. 1.4.3.3 Suma de la adaptación En este enfoque, se considera que la búsqueda converge satisfactoriamente cuando la suma de los valores de adaptación de toda la población es menor o igual a su valor de convergencia histórico. Esto garantiza que prácticamente todos los individuos estarán dentro de un rango particular de adaptación, aunque los autores recomiendan combinar este criterio con un reemplazo de los genes más débiles ya que de lo contrario, unos pocos individuos inadaptados incrementarán el valor total. Es de notar que el tamaño de la población debe considerarse al establecer el valor de convergencia. 1.4.3.4 Adaptación media Finalmente, con este método se garantiza que al menos la mitad de los individuos tendrán valores de adaptación mayores o iguales al valor de convergencia, lo que proveerá un buen rango de soluciones del cual elegir. 1.4.4 Construcción de un Algoritmo Genético: Diagrama de flujo. Una vez se han analizado todos los procesos componentes de un Algoritmo Genético, su adaptación en el constructo general se desarrolla tal como se muestra a continuación.

~ 41 ~

Si No

Gráfico 1.13. Diagrama de flujo de un Algoritmo Genético

Fuente: Elaboración Propia. Adaptado de: Sivanandam y Deepa, 2008 y Balin, 2011.

Inicio

Crear población inicial

Selección natural

Crear nueva generación aplicando cruce

¿Solución buena u óptima?

Reproducir e ignorar algunas poblaciones

Aplicar mutación

Calcular medidas de aptitud

Evaluar generación

Detener algoritmo

~ 42 ~

Gráfico 1.14. Representación gráfica del diagrama de flujo de un Algoritmo Genético


~ 43 ~

1.4.5 Aplicación de los Algoritmos Genéticos

Los algoritmos genéticos han sido empleados en una gran variedad de problemas tan diversos como: administración de la cadena de suministro [43], ruteo de vehículos [44], administración de desperdicios [45], diseño de redes e instalaciones [46, 47, 48, 49], diseño de líneas de producto [50, 51], programación de personal [52], planeación de portafolio [53] y análisis de quiebra [54], entre otros. Particularmente, en el área de Scheduling algunas aplicaciones incluyen problemas relacionados con la minimización de la tardanza [55, 56, 57, 58, 59] y el número ponderado de trabajos tardíos [60], problemas que involucran tiempos de alistamiento dependientes de la secuencia [61, 62, 63, 64, 65, 66], flow-shop Scheduling [67, 68, 63, 64], programación de máquinas en paralelo [69, 70, 71, 65, 72, 66] y varias versiones del problema job-shop [73, 74, 75, 76] y open-shop Scheduling [77]. Para más detalles sobre este tema, el lector puede remitirse a autores como Gen y Cheng [2], Ponnambalam, Aravindan y Rao [74], Jou [71], Ruiz y Maroto [78] y Essafi, Mati y Dauzère-Pérès [59]. 1.5 ESTADO DEL ARTE: APLICACIÓN DE ALGORITMOS GENÉTICOS

PARA DAR SOLUCIÓN AL PROBLEMA DE SCHEDULING ADMITIENDO RECHAZOS

De acuerdo con la revisión realizada por el autor y hasta su conocimiento, apoyado en autores como Oğuz, Salman y Yalçın [22], Wang, Xie y Cheng [12], Lin y Ying [26] y Mokhtari [9], se encuentran en la literatura tres aplicaciones de algoritmos genéticos a la resolución del problema de Aceptación de Órdenes y Scheduling, de las cuales una se refiere al escenario multi-etapa; este relativo vacío de conocimiento, ha motivado el desarrollo de la presente investigación. Roundy et ál. [33] trabajan el problema de aceptación de órdenes en un ambiente con múltiples etapas, donde las decisiones a tomar incluyen además de rechazar o no un pedido, qué fecha de entrega pactar y qué tamaño deben tener los lotes de producción. Las nuevas órdenes son incluidas en el programa factible actual y las restricciones respecto a los due dates de los trabajos no pueden violarse. El objetivo es minimizar los costos de alistamiento y mantenimiento, a la vez que se busca cumplir el mayor nivel de demanda posible. Los autores formulan un modelo MILP (mixed integer linear programming) para instancias pequeñas y varias heurísticas que incluyen algoritmos genéticos, para problemas de mayor tamaño. Como resultado, los experimentos computacionales muestran que tanto el algoritmo genético como recocido simulado funcionan bien para el problema bajo análisis. Por su parte, Chen, Lu y Yang [32] proponen un algoritmo evolutivo híbrido que combina algoritmos genéticos con optimización extrema (EO) para dar solución al problema de Scheduling admitiendo rechazos, en el que además se involucran restricciones relacionadas con costos de transición dependientes de

~ 44 ~

la secuencia, penalizaciones por no ejecutar las tareas y por adelantos y retrasos respecto a la fecha de entrega. Inicialmente, se formula un modelo de optimización combinatoria; sin embargo, debido al carácter NP-Hard del escenario bajo análisis, se diseña la herramienta mencionada para instancias de mayor tamaño, combinando la capacidad de búsqueda de los algoritmos genéticos y la eficacia en la búsqueda local de la optimización extrema. Los resultados experimentales muestran resultados superiores en torno a la calidad de la solución y la eficiencia computacional del algoritmo. Finalmente, Rom y Slotnick [36] toman en cuenta un escenario make-to-order donde se eligen las órdenes a aceptar dentro de un conjunto de pedidos, de los que se conoce su tiempo de procesamiento, fecha de entrega y utilidad. Adicionalmente, se involucra dentro del proceso de toma de decisiones la importancia del cliente, por lo que pueden aceptarse pedidos que aunque no sean tan lucrativos como otros, tienen un valor estratégico para negocios futuros. Una orden despachada después de la fecha de entrega pactada incurre en una penalización proporcional al tiempo de demora; sin embargo, no existen utilidades o penalizaciones por despacharla con anterioridad. El objetivo es maximizar la utilidad, es decir, la diferencia entre la suma de los ingresos unitarios y la tardanza total ponderada. Para resolverlo, se propone una heurística miope para dar respuesta a una relajación del problema original, la cual ensambla nuevamente los trabajos aceptados, que son programados heurísticamente para minimizar la tardanza total ponderada. Esta herramienta es complementada con un algoritmo genético para construir un espacio de búsqueda diverso, mientras se mantienen los registros de las mejores soluciones encontradas. Para verificar la eficiencia de las herramientas propuestas, se evalúa su desempeño en términos del valor de la función objetivo y tiempo de corrida, demostrándose que los mejores resultados son alcanzados por una búsqueda exhaustiva local a expensas de un costo computacional alto. 1.6 CONCLUSIONES PARCIALES El recorrido efectuado para la construcción del marco teórico verificando las teorías, enfoques y el estado del arte relacionado con la aplicación de Algoritmos Genéticos en el escenario de Aceptación de Órdenes y Scheduling en ambientes de manufactura Flexible Flow Shop, permitió en primera instancia, contextualizar el objeto de estudio dentro de un campo general como es el problema de Scheduling, evidenciar la evolución de los sistemas productivos y de las herramientas empleadas para su solución y demostrar su importancia como soporte a la toma de decisiones en las firmas reales y su papel en el aumento de la eficiencia de las compañías a través de la utilización adecuada de los recursos y la capacidad disponible. Adicionalmente, fue posible definir los términos y símbolos que se utilizarán en el desarrollo de esta investigación, clarificando los conceptos de interés y adoptando una notación universal para el problema de estudio.

~ 45 ~

En segunda instancia, se definieron las particularidades del escenario de Scheduling admitiendo rechazos, lo que permitió extractar nuevas relaciones, parámetros y variables a considerar dentro del problema, eligiéndose un ambiente de máquinas no relacionadas en paralelo y una función objetivo que maximice la utilidad. De esta manera, la investigación se concentrará en un escenario estático determinístico que puede notarse

como: 𝑶𝑨𝑺𝑹𝒎𝑭𝑭𝒄|𝒄𝒉𝒂𝒊𝒏𝒔, 𝒔𝒋𝒍𝒕 , 𝑹𝑫𝒋, 𝒑𝒔𝒋

𝒕, 𝒗𝒊𝒋𝒕 , 𝑫𝑫𝒋,𝑫𝑳𝒋| 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅, tal como se

observará en el Capítulo 2. De otro lado y teniendo en cuenta que el procedimiento producto de esta investigación se fundamenta en Algoritmos Genéticos, la revisión teórica alrededor de su implementación permite establecer algunas ventajas sobre otras herramientas de búsqueda, definir la terminología a emplear a lo largo de la investigación, identificar diversas formas de codificar los parámetros y soluciones para involucrar a la herramienta cromosomas que representen adecuadamente el escenario, analizar los operadores genéticos disponibles y los parámetros que deben calibrarse para lograr los objetivos planteados, observar la teoría existente alrededor de las funciones de evaluación y adaptación, así como en torno a los diferentes criterios de convergencia y métodos de terminación de la búsqueda y diagramar finalmente la manera como estos elementos confluyen dentro de un algoritmo estándar que guiará el proceso de construcción de la herramienta propuesta en esta investigación. Finalmente, la revisión del estado del arte en el contexto de interés evidenció la importancia de realizar esta investigación, en tanto que se encontraron tres aportes relacionados en la literatura de los cuales uno considera un escenario multi-etapa, lo que representa un relativo vacío de conocimiento que se considera necesario satisfacer. 1.7 BIBLIOGRAFÍA

[1] M. Pinedo, Planning and Scheduling in Manufacturing and Services., Springer Series in Operations Research, 2005.

[2] M. Gen y R. Cheng, Genetic Algorithms and Engineering Optimization, Wiley - IEEE, 2000.

[3] S. Sivanandam y S. Deepa, Introduction to Genetic Algorithms, Springer, 2008.

[4] Herrmann, J.W. (Editor), Handbook of Production Scheduling, Springer, 2006.

[5] P. Brucker, Scheduling Algorithms, Osnabrück: Springer, 2007.

[6] M. Pinedo, Scheduling. Theory, Algorithms and Systems, Springer, 2008.

[7] R. Graham, E. Lawler, J. Lenstra y A. R. Kan, «Optimization and approximation in deterministic sequencing and scheduling: A survey,» Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979.

[8] B. Naderi, S. Fatemi Ghomi, M. Aminnayeri y M. Zandieh, Scheduling open

~ 46 ~

shops with parallel machines to minimize total completion time, vol. 235, 2011, pp. 1275-87.

[9] H. Mokhtari, «A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection,» Applied Soft Computing, vol. 26, pp. 166-179, 2015.

[10] B. Cesaret, C. Oğuz y F. S. Salman, «A tabu search algorithm for order acceptance and scheduling,» Computers and Operations Research, vol. 39, pp. 1197-1205, 2012.

[11] J. Ou, X. Zhong y G. Wang, «An improved heuristic for parallel machine scheduling with rejection,» European Journal of Operational Research, vol. 241, pp. 653-661, 2015.

[12] X. Wang, X. Xie y T. Cheng, «A modified artificial bee colony algorithm for order acceptance in two-machine flow shops,» Int. J. Production Economics, vol. 141, pp. 14-23, 2013.

[13] S. Slotnick y T. Morton, «Selecting jobs for a heavily loaded shop with lateness penalties,» Computers and Operations Research, vol. 23, pp. 131-140, 1996.

[14] J. Ghosh, «Job selection in a heavily loaded shop,» Computers and Operations Research, vol. 24, pp. 141-145, 1997.

[15] H. Lewis y S. Slotnick, «Multi-period job selection: planning work loads to maximize profit,» Computers and Operations Research, vol. 29, pp. 1081-98, 2002.

[16] Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall y L. Stougie, «Multiprocessor Scheduling with Rejection,» SIAM J. Discret. Math., vol. 13, pp. 64-78, 2000.

[17] D. Engels, D. Karger, S. Kolliopoulos, S. Sengupta, R. Uma y J. Wein, «Techniques for scheduling with rejection,» J. Algorithms, vol. 39, pp. 175-191, 2003.

[18] K. Charnsirisakskul, P. Griffin y P. Keskinocak, «Order selection and scheduling with leadtime flexibility,» IIE Trans., vol. 36, pp. 697-707, 2004.

[19] K. Charnsirisakskul, P. Griffin y P. Keskinocak, «Pricing and scheduling decisions with leadtime flexibility,» Eur. J. Oper. Res., vol. 171, pp. 153-169, 2006.

[20] S. Slotnick y T. Morton, «Order acceptance with weighted tardiness,» Computers and Operations Research, vol. 34, pp. 3029-42, 2007.

[21] I. Lee y C. Sung, «Single machine scheduling with outsourcing allowed,» Int. J. Prod. Econ., vol. 111, pp. 623-634, 2008.

[22] C. Oğuz, F. S. Salman y Z. B. Yalçın, «Order acceptance and scheduling decisions in make-to-order systems,» Int. J. Production Economics, vol. 125, pp. 200-211, 2010.

[23] F. Nobinon y R. Leus, «Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment,» Computers and Operations Research, vol. 38, pp. 367-378, 2011.

[24] V. Oduguwa, A. Tiwari y R. Roy, «Evolutionary computing in manufacturing

~ 47 ~

industry: an overview of recent applications,» App. Soft. Comput., vol. 5, pp. 281-299, 2005.

[25] A. Zavoianu, G. Bramerdorfer, E. Lughofer, S. Silber, W. Amrhein y E. Klement, «Hybridization of multi-objective evolutionary algorithms and artificial neuralnetworks for optimizing the performance of electrical drives,» Eng. App. Artif. Intell., vol. 26, pp. 1781-94, 2013.

[26] S.-W. Lin y K.-C. Ying, «Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness,» Applied Soft Computing, vol. 30, pp. 462-474, 2015.

[27] G. Kyparisis, S. Gupta y C. Ip, «Project selection with discounted returns and multiple constraints,» Eur. J. Oper. Res., vol. 94, pp. 87-96, 1996.

[28] B. Yang y J. Geunes, «Heuristic Approaches for Solving Single Resource Scheduling Problems with Job-Selection Flexibility. Technical Report,» Department ofIndustrial and Systems Engineering, University of Florida, 2003.

[29] Y. Xiao, R. Zhang, Q. Zhao y I. Kaku, «Permutation flow shop schedulingwith order acceptance and weighted tardiness,» App. Math. Comput., vol. 218, pp. 7911-26, 2012.

[30] S. A. Slotnick, «Order acceptance and scheduling: A taxonomy and review,» European Journal of Operational Research, vol. 212, pp. 1-11, 2011.

[31] C. Akkan, «Finite-capacity scheduling-based planning for revenue-based capacity management,» Eur. J. Oper. Res., vol. 100, pp. 170-179, 1997.

[32] Y.-W. Chen, Y.-Z. Lu y G.-K. Yang, «Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling,» Int J Adv Manuf Technol, vol. 36, pp. 959-968, 2008.

[33] R. Roundy, D. Chen, P. Chen, M. Çakanyildirim, M. Freimer y V. Melkonian, «Capacity-Driven Acceptance of Customer Orders for a Multi-stage batch manufacturing system: models and algorithms,» IIE Trans., vol. 37, pp. 1093-1105, 2005.

[34] A. Moghaddam, F. Yalaoui y L. Amodeo, «Efficient meta-heuristics based on various dominance criteria for a single-machine bi-criteria scheduling problem with rejection,» Journal of Manufacturing Systems, vol. 34, pp. 12-22, 2015.

[35] S. Lin y K. Ying, «Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm,» J. Oper. Res. Soc., vol. 64, pp. 293-311, 2013.

[36] W. O. Rom y S. A. Slotnick, «Order Acceptance Using Genetic Algorithms,» Computers & Operations Research, vol. 36, pp. 1758-67, 2009.

[37] P. Keskinocak y S. Tayur, «Due date management policies,» de D. Simchi-Levi, S.D. Wu, Z.J. Shen (Eds.), Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era, Boston, Kluwer, 2004, pp. 485-556.

[38] C. Darwin, On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life, London: John

~ 48 ~

Murray, 1859.

[39] J. Holland, Adaptation in Natural and Artificial Systems, Ann Arbor, Michigan: The University of Michigan Press, 1975.

[40] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Inc., 1989.

[41] H. Zhou, Y. Feng y L. Han, «The hybrid heuristic genetic algorithm for job shop scheduling,» Computers and Industrial Engineering, vol. 40, nº 3, pp. 191-200, 2001.

[42] S. Balin, «Non-identical parallel machine scheduling using genetic algorithms,» Expert Systems with Applications, vol. 38, pp. 6814-21, 2011.

[43] H. Ko y G. Evans, «A genetic-algorithm based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs,» Computers and Operations Research, vol. 34, pp. 346-366, 2007.

[44] G. Alvarenga, G. Mateus y G. de Tomi, «A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,» Computers and Operations Research, vol. 34, pp. 1561-84, 2007.

[45] J. Bautista y J. Pereira, «Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona.,» Omega, vol. 34, pp. 617-629, 2006.

[46] B. Norman y A. Smith, «Continuous approach to considering uncertainty in facility design.,» Computers and Operations Research, vol. 33, nº 6, pp. 1760-75, 2006.

[47] T. Tyni y J. Ylinen, «Evolutionary bi-objective optimisation in the elevator car routing problem,» European Journal of Operational Research, vol. 169, nº 3, pp. 960-977, 2006.

[48] M. Vroblefski y E. Brown, «A grouping genetic algorithm for registration area planning,» Omega, vol. 34, nº 3, pp. 220-230, 2006.

[49] G. Zhang y K. Lai, «Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem.,» European Journal of Operational Research, vol. 169, nº 2, pp. 413-425, 2006.

[50] G. Alexouda y K. Paparrizos, «A genetic algorithm approach to the product line design problem using the seller's return criterion: an extensive comparative computational study,» European Journal of Operational Research, vol. 134, pp. 165-178, 2001.

[51] G. Alexouda, «An evolutionary algorithm approach to the share of choices problem in product line design,» Computers and Operations Research, vol. 31, pp. 2215-2229, 2004.

[52] M. Moz y M. Pato, «genetic algorithm approach to the nurse rerostering problem,» Computers and Operations Research, vol. 34, pp. 667-691, 2007.

[53] J. Jiao, Y. Zhang y Y. Wang, «A heuristic genetic algorithm for product portfolio planning.,» Computers and Operations Research, vol. 34, pp. 1777-1799, 2007.

[54] T. Lensberg, A. Eilifsen y T. McKee, «Bankruptcy theory development and

~ 49 ~

classification via genetic programming,» European Journal of Operational Research, vol. 169, nº 2, pp. 677-697, 2006.

[55] S. Avci, M. Akturk y R. Storer, «A problem space algorithm for single machine weighted tardiness problems,» IIE Transactions, vol. 35, pp. 479-486, 2003.

[56] D. Mattfeld y C. Bierwirth, «An efficient genetic algorithm for job shop scheduling with tardiness objectives,» European Journal of Operational Research, vol. 155, pp. 616-630, 2004.

[57] C. Hino, D. Ronconi y A. Mendes, «Minimizing earliness and tardiness penalties in a single-machine problem with a common due date,» European Journal of Operational Research, vol. 160, pp. 190-201, 2005.

[58] R. M'Hallah, «Minimizing total earliness and tardiness on a single machine using a hybrid heuristic,» Computers and Operations Research, vol. 34, pp. 3126-3142, 2007.

[59] I. Essafi, Y. Mati y S. Dauzère-Pérès, «A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,» Computers and Operations Research, vol. 35, pp. 2599-616, 2008.

[60] M. Sevaux y S. Dauzère-Pérès, «Genetic algorithms to minimize the weighted number of late jobs on a single machine.,» European Journal of Operational Research, vol. 151, pp. 296-306, 2003.

[61] M. Kurz y R. Askin, «Scheduling flexible flow lines with sequence-dependent setup times,» European Journal of Operational Research, vol. 159, pp. 66-82, 2004.

[62] S. Lee y A. Asllani, «Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming,» Omega, vol. 45, nº 32, pp. 145-153, 2004.

[63] P. Franca, J. Gupta, A. Mendes, P. Moscato y K. Veltink, «Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups,» Computers and Industrial Engineering, vol. 48, pp. 491-506, 2005.

[64] R. Ruiz, C. Maroto y J. Alcarez, «Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics,» European Journal of Operational Research, vol. 165, pp. 34-54, 2005.

[65] J. Jungwattanakit, M. Reodecha, P. Chaovalitwongse y F. Werner, «A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria,» Computers & Operations Research, vol. 36(2), pp. 358-78, 2009.

[66] J. Torres, V. Perea y C. López, «A Genetic Algorithm For Simultaneous Scheduling Problem In Flexible Flow Shop Environments With Unrelated Parallel Machines, Setup Time And Multiple Criteria,» Proceedings of the International Conference on Advanced Manufacturing Engineering and Technologies, vol. 2, pp. 203-212, 2013.

[67] O. Etiler, B. Toklu, M. Atak y J. Wilson, «A genetic algorithm for flow shop scheduling problems,» Journal of the Operational Research Society, vol. 55, pp. 830-835, 2004.

~ 50 ~

[68] A. Bolat, I. Al-Harkan y B. Al Harbi, «Flow-shop scheduling for three serial stations with the last two duplicate,» Computers and Operations Research, vol. 32, pp. 647-667, 2005.

[69] N. Chiu, S. Fang y Y. Lee, «Sequencing parallel machining operations by genetic algorithms,» Computers and Industrial Engineering, vol. 36, pp. 259-80, 1999.

[70] S. Koh, P. Koo, J. Ha y W. Lee, «Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families,» International Journal of Production Research, vol. 42, nº 19, pp. 4091-107, 2004.

[71] C. Jou, «A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines,» Computers and Industrial Engineering, vol. 48, pp. 39-54, 2005.

[72] H. Khademi Zare y M. Fakhrzad, «Solving flexible flow shop scheduling problem with a hybrid genetic algorithm and data mining: a fuzzy approach,» Expert Systems with Applications, vol. 38, pp. 7609-15, 2011.

[73] F. Ghedjati, «Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: heuristic mixing method machines and precedence,» Computers and Industrial Engineering, vol. 37, pp. 39-42, 1999.

[74] S. Ponnambalam, P. Aravindan y P. Rao, «Comparative evaluation of genetic algorithms for job-shop scheduling,» Production Planning and Control, vol. 12, nº 6, pp. 560-74, 2001.

[75] B. Park, H. Choi y H. Kim, «A hybrid genetic algorithm for the job shop scheduling problems,» Computers and Industrial Engineering, vol. 45, pp. 597-613, 2003.

[76] G. Cavory, R. Dupas y G. Goncalves, «A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints,» European Journal of Operations Research, vol. 161, pp. 73-85, 2005.

[77] C. Prins, «Competitive genetic algorithms for the open-shop scheduling problem.,» Mathematical Methods of Operations Research, vol. 52, pp. 389-411, 2000.

[78] R. Ruiz y C. Maroto, «A comprehensive review and evaluation of permutation flowshop heuristics,» European Journal of Operational Research, vol. 165, pp. 479-494, 2005.

~ 51 ~

CAPÍTULO 2

PROCEDIMIENTO PROPUESTO PARA EL ESCENARIO DE ACEPTACIÓN

DE ÓRDENES Y SCHEDULING EN AMBIENTES FLEXIBLE FLOW SHOP

Una vez contextualizado y definido el problema a estudiar, en este capítulo se presentarán las herramientas de ingeniería propuestas para su resolución. En primera instancia, se desarrollará el modelo matemático que caracteriza formalmente el escenario de interés, involucrando los parámetros, variables y relaciones correspondientes, el cual será posteriormente evaluado para definir el tamaño de problema que puede resolver dentro de un tiempo computacional razonable. Seguidamente y tomando en cuenta la complejidad del escenario bajo análisis, el modelo formulado se tomará como base para elaborar una herramienta heurística que permita obtener resultados cercanos al óptimo, en tiempos computacionales más cortos y que servirá para generar una solución inicial que acelere la convergencia del algoritmo genético y oriente su búsqueda. Finalmente, con estas herramientas se diseñará el procedimiento propuesto resultado de la investigación, que aprovecha las ventajas de los algoritmos genéticos y el criterio de asignación que sigue la heurística para encontrar mejores soluciones. La metodología a seguir se presenta en la siguiente figura.

~ 52 ~

Fuente: Elaboración Propia

Revisión de literatura: escenario Flexible Flow Shop, máquinas no relacionadas y maximizando la utilidad: ganancias por las órdenes aceptadas, penalización por las órdenes rechazadas y costo del tiempo ocioso de los recursos

MODELO DE PROGRAMACIÓN

ENTERA MIXTA

Formular y ejecutar en GAMS para determinar el tamaño máximo de problema que puede resolver

Límite de tiempo de corrida de 200.000 segundos de CPU. Se prueba un criterio a la vez hasta que se encuentre un límite

Apéndice A

APROXIMACIÓN

HEURÍSTICA

Crear población inicial. Involucrar solución de

la heurística. Definir operadores

genéticos. Programar en Visual

Basic para Excel. Calibrar parámetros.

Encontrar una solución más cercana al óptimo en tiempos razonables. Aprovechar los beneficios de la recombinación de soluciones. Mantiene el criterio de elección de las máquinas de la heurística

PROCEDIMIENTO PROPUESTO

RESULTADO DE LA

INVESTIGACIÓN

Comparar frente a los resultados del MIP (tiempo computacional y función objetivo).

Verificar desempeño en instancias de mayor tamaño.

Capítulo 3

Modificación herramienta Dynamic Release First-

Sequence Best (d-RFSB).

Debido al escenario combinatorio y con el objetivo de encontrar una solución inicial que oriente la búsqueda del algoritmo y acelere su convergencia.

Gráfico 2.1. Metodología diseñada para el Capítulo 2

~ 53 ~

2.1 MODELO MATEMÁTICO FORMULADO

A través del análisis de los diferentes modelos de programación entera mixta formulados en la literatura para representar formalmente escenarios similares al objeto de estudio, se ha diseñado la estructura que se presenta a continuación, la cual servirá de base para la construcción del procedimiento propuesto basado en Algoritmos Genéticos y que ha sido ajustada de acuerdo con los alcances de este proyecto de investigación. En el escenario de interés, se plantea la maximización de las utilidades totales del ejercicio, que involucran tres criterios a saber: la ganancia recibida por las órdenes aceptadas, los costos asociados al tiempo ocioso de los recursos – métrica que según la revisión de literatura no ha sido considerada en investigaciones previas – y la penalización por las órdenes rechazadas, relacionada con la pérdida de imagen frente al cliente o la tercerización de las actividades asociadas a su fabricación. Para la construcción del primer criterio, se realiza la suma de una función lineal a tramos definida para cada orden como la ganancia recibida por ella, 𝑹𝒋, tal

como lo sugieren Oğuz, Salman y Yalçın [1] y que se muestra en la siguiente figura.

Gráfico 2.2. Función de utilidad para la orden 𝒋

Fuente: Elaboración Propia. Adaptado de: Oğuz, Salman y Yalçın, 2010.

Como se observa y tal como lo plantean los autores, en la región I no se reciben ganancias por la orden puesto que es un tiempo anterior a su fecha de arribo al sistema o release date, mientras que si el tiempo de finalización de la orden se encuentra en la región II, se reciben por ella 𝑢𝑗 unidades de ganancia

constante.

~ 54 ~

En este contexto, la fecha de entrega o due date puede ser considerada como el momento más tardío en que el cliente preferiría recibir su orden. A medida que se incumple esta fecha, su satisfacción disminuye, por lo que acepta pagar una cifra inferior al precio inicial y el fabricante incurre entonces en un costo de penalización asociado a esta tardanza, 𝑤𝑗. Por tanto, si la orden se completa en

la zona III, la utilidad recibida por una orden decrece linealmente hasta que se convierte en 0 en la fecha límite de entrega o deadline. Por tanto, cualquier orden que finalizaría después de la fecha límite debe ser rechazada a su ingreso. Bajo las condiciones establecidas para el modelo, todos los clientes tienen la misma importancia, el número de órdenes que se acepta está limitado únicamente por la capacidad disponible y se asume que en el entorno de producción no existen paradas inesperadas de máquinas y que las interrupciones en la ejecución de las órdenes no están permitidas. Adicionalmente, una orden sólo puede recibir procesamiento de un recurso a la vez y este sólo puede manufacturar una orden al mismo tiempo. Cualquier orden se envía directamente al cliente, por lo que no se incurre en costos de mantenimiento de inventario. Finalmente, toda la información de entrada se asume conocida al momento de la planeación. En los siguientes incisos se presenta la notación empleada a lo largo del proyecto, así como el modelo de programación entera mixta que representa formalmente las relaciones incluidas. 2.1.1 Notación La notación elegida para el escenario de estudio involucra los siguientes índices, parámetros y variables. Índices

𝑡 Índice de la estación, 𝑡 = 1,2,3,… , 𝑘 𝑗, 𝑙 Índice de las órdenes, 𝑗, 𝑙 = 1,2,3,… , 𝑛

𝑚𝑡 Cantidad de máquinas en paralelo en la estación 𝑡 𝑖 Índice de la máquina, 𝑖 = 1,2,3,… ,𝑚𝑡 Parámetros 𝑅𝐷𝑗 Fecha de liberación de la orden 𝑗

𝐷𝐷𝑗 Fecha de entrega de la orden 𝑗

𝐷𝐿𝑗 Fecha límite de entrega de la orden 𝑗, tal que 𝐷𝐷𝑗 ≤ 𝐷𝐿𝑗, tras la

que no se reciben utilidades 𝑢𝑗 Máxima ganancia recibida si se acepta la orden 𝑗

𝑒𝑗 Penalización por rechazar la orden 𝑗

𝑤𝑗 Costo unitario de penalización por la tardanza en la entrega de 𝑗

𝑝𝑠𝑗𝑡 Tiempo promedio de procesamiento de la orden 𝑗 en la estación 𝑡

~ 55 ~

𝑣𝑖𝑗𝑡 Velocidad relativa de procesamiento de la orden 𝑗 en la máquina 𝑖

de la estación 𝑡 (adimensional)

𝑠𝑗𝑙𝑡 Tiempo de alistamiento dependiente de la secuencia, referido a la

demora en que se incurre antes que la orden 𝑙 pueda procesarse,

si 𝑗 precede a 𝑙 en la máquina 𝑖 de la estación 𝑡 𝐶𝑂𝑖

𝑡 Costo unitario del tiempo ocioso de la máquina 𝑖 de la estación 𝑡 Variables Positivas

𝑃𝑖𝑗𝑡 Tiempo de procesamiento de la orden 𝑗 en la máquina 𝑖 de la

estación 𝑡 𝑆𝑇𝑗

𝑡 Inicio de la orden 𝑗 en la estación 𝑡

𝐶𝑗𝑡 Tiempo de finalización de la orden 𝑗 en la estación 𝑡

𝑇𝐴𝑗 Tardanza de la orden 𝑗

𝐼𝐷𝑖𝑗𝑙𝑡 Tiempo ocioso entre la elaboración de las órdenes 𝑗 y 𝑙 en la

máquina 𝑖 de la estación 𝑡 𝑅𝑗 Utilidades recibidas si se acepta la orden 𝑗, tal que 𝑅𝑗 =

max {0, 𝑒𝑗 − 𝑤𝑗𝑇𝐴𝑗}

Variables Binarias

𝑋𝑖𝑗𝑙𝑡 1 si la orden 𝑗 es programada justamente antes de 𝑙 en la

máquina 𝑖 de la estación 𝑡. 0 en otro caso. 𝑌𝑗 1 si se acepta la orden 𝑗. 0 si se rechaza.

2.1.2 Modelo de Programación Entera Mixta

Teniendo en cuenta que la literatura relacionada se focaliza en escenarios de una sola máquina y una estación, estos aportes se han modificado para ajustarse a un ambiente de manufactura Flexible Flow Shop con máquinas no relacionadas en paralelo e involucrar dentro de la función objetivo el costo del tiempo ocioso de estos recursos, que de acuerdo con la revisión de la literatura presentada en el Capítulo 1 y la taxonomía del problema analizada, no se ha considerado y que ha permitido describir el problema, según la notación de Graham, et ál. [2] como:

𝑶𝑨𝑺𝑹𝒎𝑭𝑭𝒄|𝒄𝒉𝒂𝒊𝒏𝒔, 𝒔𝒋𝒍𝒕 , 𝑹𝑫𝒋, 𝒑𝒔𝒋

𝒕, 𝒗𝒊𝒋𝒕 , 𝑫𝑫𝒋, 𝑫𝑳𝒋| 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅.

De esta manera, el modelo de programación entera mixta formulado incluye las siguientes relaciones.

~ 56 ~

Función Objetivo:

Se considera la maximización de las utilidades del ejercicio, compuesta por las ganancias percibidas por las órdenes aceptadas, menos la penalización por las órdenes rechazadas y el costo de tiempo ocioso de los recursos de cada estación.

Máx ∑𝑅𝑗

𝑛

𝑗=1

− ∑ 𝑒𝑗(1 − 𝑌𝑗)

𝑛

𝑗=1

− ∑∑ ∑ ∑𝐶𝑂𝑖𝑡𝐼𝐷𝑖𝑗𝑙

𝑡

𝑘

𝑡=1

𝑛+1

𝑙=1𝑙≠𝑗

𝑛

𝑗=0

𝑚𝑡

𝑖=1

(1)

Sujeto a:

1. Restricciones de secuencia: obligan a que, si una orden es aceptada,

sea sucedida y precedida por una sola orden y que, en caso contrario, no tenga lugar en la secuencia.

∑ ∑ 𝑋𝑖𝑗𝑙𝑡 = 𝑌𝑗

𝑛+1

𝑙=1𝑙≠𝑗

𝑚𝑡

𝑖=1

∀𝑗 = 1,… , 𝑛 ; 𝑡 = 1,… , 𝑘

(2)

∑∑𝑋𝑖𝑙𝑗𝑡

𝑛

𝑙=0𝑙≠𝑗

= 𝑌𝑗 ∀𝑗 = 1, … , 𝑛 ; 𝑡 = 1, … , 𝑘

𝑚𝑡

𝑖=1

(3)

2. Restricciones para las órdenes artificiales 𝒋 = 𝟎 y 𝒋 = 𝒏 + 𝟏: garantizan que la orden ficticia 0 tenga máximo un sucesor y que la

orden 𝑛 + 1, que cierra el sistema, tenga un único predecesor en cada máquina de cada estación.

∑𝑋𝑖𝑗=0𝑙𝑡 = 1 ∀𝑖 = 1, . . , 𝑚𝑡

𝑛

𝑙=1

; 𝑡 = 1, … , 𝑘

(4)

∑𝑋𝑖𝑙𝑗=𝑛+1𝑡 = 1 ∀𝑖 = 1, . . ,𝑚𝑡

𝑛

𝑙=1

; 𝑡 = 1,… , 𝑘

(5)

3. Construcción de una secuencia coherente. Asegura que si una orden

es nodo destino, a su vez, debe ser nodo origen para la siguiente orden programada en la secuencia en cada máquina de cada estación, hasta

que dicho destino sea la orden ficticia 𝑛 + 1, que cierra el sistema.

~ 57 ~

∑𝑋𝑖𝑗𝑙𝑡 = ∑ 𝑋𝑖𝑙𝑗

𝑡

𝑛+1

𝑗=1𝑗≠𝑙

∀𝑙 = 1,… , 𝑛 ; 𝑖 = 1, . . , 𝑚𝑡

𝑛

𝑗=0𝑗≠𝑙

; 𝑡 = 1,… , 𝑘

(6)

4. Conjunto de restricciones que permiten obtener la variable positiva

𝑷𝒊𝒋𝒕 , es decir, el tiempo de procesamiento de cada orden en cualquier

máquina de cada estación. Este tiempo se define como el tiempo promedio de procesamiento de la orden 𝑗 en la estación 𝑡 dividido entre la velocidad relativa (adimensional) de cada máquina al realizar dicha tarea [3].

𝑃𝑖𝑗𝑡 = ∑

𝑝𝑠𝑗𝑡

𝑣𝑖𝑗𝑡 𝑋𝑖𝑗𝑙

𝑡

𝑛+1

𝑙=1𝑙≠𝑗

∀𝑙 = 1,… , 𝑛 ; 𝑖 = 1, . . ,𝑚𝑡 ; 𝑡 = 1,… , 𝑘

(7)

5. Conjunto de restricciones disyuntivas: establece que, si las órdenes 𝑗 y 𝑙 son programadas en la misma máquina de una estación y 𝑗 se ubica

inmediatamente antes que 𝑙, entonces 𝑗 debe completarse antes de que

pueda iniciarse 𝑙. El inicio de la orden 𝑙 debe realizarse cuando por lo menos, se haya completado el tiempo de procesamiento de la orden 𝑗 y

el tiempo de alistamiento por el cambio de tareas. 𝑀 denota una constante de gran valor, mayor que la suma de todos los tiempos de procesamiento y alistamiento, que permite relajar la restricción.

𝐶𝑙𝑡 − 𝐶𝑗

𝑡 ≥ 𝑠𝑗𝑙𝑡 + ∑𝑃𝑖𝑗

𝑡

𝑚𝑡

𝑖=1

+ [(∑𝑋𝑖𝑗𝑙𝑡

𝑚𝑡

𝑖=1

) − 1]𝑀 ∀𝑗, 𝑙 = 1, … , 𝑛 ; 𝑡 = 1, … , 𝑘

(8)

6. Restricciones de precedencia en las estaciones. Obligan a que las

órdenes no inicien su procesamiento en la estación 𝑡 + 1 hasta que hayan culminado su transformación en la estación 𝑡. Para el caso de la

primera estación, 𝐶𝑗0 se declara como la fecha de arribo al sistema o

release date de la orden 𝑗.

𝐶𝑙𝑡 − 𝑅𝐷𝑙𝑌𝑙 ≥ ∑∑𝑋𝑖𝑗𝑙

𝑡 𝑠𝑗𝑙𝑡

𝑚𝑡

𝑖

𝑛

𝑗=1𝑗≠𝑙

+ ∑𝑃𝑖𝑙𝑡

𝑚𝑡

𝑖=1

∀𝑙 = 1,… , 𝑛 ; 𝑡 = 1

(9)

𝐶𝑙𝑡 − 𝐶𝑙

𝑡−1 ≥ ∑∑ 𝑋𝑖𝑗𝑙𝑡 𝑠𝑗𝑙

𝑡

𝑚𝑡

𝑖

𝑛

𝑗=1𝑗≠𝑙

+ ∑ 𝑃𝑖𝑙𝑡

𝑚𝑡

𝑖=1

∀𝑙 = 1, … , 𝑛 ; 𝑡 = 2, … , 𝑘

(10)

~ 58 ~

7. Restricciones que permiten calcular la variable positiva 𝑺𝑻𝒋𝒕 o inicio

de la orden 𝑗 en la estación 𝑡, como la diferencia entre su tiempo de finalización y la suma de su tiempo de procesamiento y el tiempo de

alistamiento en que se incurre por el paso de la orden anterior a 𝑗.

8. Restricciones que vinculan el tiempo ocioso de los recursos

productivos, definido como la diferencia entre el inicio de la orden 𝑙 y el

tiempo de finalización de la orden 𝑗, cuando 𝑗 precede a 𝑙. Se involucra

una vez más la constante 𝑀 que permite relajar la restricción.

𝑆𝑇𝑙𝑡 − 𝐶𝑗

𝑡 ≤ 𝐼𝐷𝑖𝑗𝑙𝑡 + (1 − 𝑋𝑖𝑗𝑙

𝑡 )𝑀 ∀𝑗, 𝑙 = 1,… , 𝑛; 𝑖 = 1, . . , 𝑚𝑡; 𝑡 = 1,… , 𝑘; 𝑗 ≠ 𝑙 (12)

9. Restricciones que rechazan las órdenes cuyo tiempo de finalización

será posterior a la fecha límite de entrega o deadline

𝐶𝑗𝑡 ≤ 𝐷𝐿𝑗𝑌𝑗 ∀𝑗 = 1,… , 𝑛 ; 𝑡 = 𝑘 (13)

10. Restricciones que establecen el límite inferior y superior de la

tardanza de la orden 𝒋.

𝑇𝐴𝑗 ≥ 𝐶𝑗𝑡 − 𝐷𝐷𝑗 ∀𝑗 = 1,… , 𝑛 ; 𝑡 = 𝑘 (14)

𝑇𝐴𝑗 ≤ (𝐷𝐿𝑗 − 𝐷𝐷𝑗) 𝑌𝑗 ∀𝑗 = 1,… , 𝑛 (15)

11. Restricciones que establecen la función de ganancia recibida por

una orden, 𝑹𝒋

𝑅𝑗 ≤ 𝑢𝑗𝑌𝑗 − 𝑤𝑗𝑇𝐴𝑗 ∀𝑗 = 1,… , 𝑛 (16)

12. Restricciones adicionales

𝑌𝑗=0 = 1 (17)

𝑌𝑗=𝑛+1 = 1 (18)

𝑌𝑗 ∈ {0,1} , 𝑋𝑖𝑗𝑙𝑡 ∈ {0,1} ∀𝑗, 𝑙 = 1,… , 𝑛 ; 𝑗 ≠ 𝑙 (19)

𝑆𝑇𝑙𝑡 + ∑𝑃𝑖𝑙

𝑡

𝑚𝑡

𝑖=1

+ ∑ ∑𝑋𝑖𝑗𝑙𝑡 𝑠𝑗𝑙

𝑡

𝑚𝑡

𝑖

𝑛

𝑗=1𝑗≠𝑙

≥ 𝐶𝑙𝑡 ∀𝑙 = 1,… , 𝑛 ; 𝑡 = 1,… , 𝑘

(11)

~ 59 ~

2.1.3 Generación de datos y límite superior del Modelo de Programación Entera Mixta propuesto

El modelo planteado se ejecutó en el software comercial de programación matemática General Algebraic Modelling System (GAMS) con ayuda de un procesador Intel Core i7 2.20GHz con 6GB de RAM. Debido a que de acuerdo con el conocimiento del autor, no se encuentran en la literatura instancias de comparación al problema bajo estudio, los parámetros del problema se definieron como números aleatorios distribuidos uniformemente en los siguientes intervalos: los tiempos de procesamiento estándar en [10,100] y los tiempos de alistamiento dependientes de la secuencia en el intervalo [2,10]. Así mismo, la ganancia máxima recibida por

cada orden 𝑗 se distribuye entre 200 y 1000 unidades, la penalización por rechazar una orden sigue esta misma distribución entre el intervalo [50,80] y el costo unitario del tiempo ocioso de cada máquina en cada estación se encuentra en el intervalo [1, 5]. Para la generación del Release Date de cada orden, las velocidades relativas de las máquinas y las fechas de entrega o due date, se emplearon los aportes de Jungwattanakit et ál. [4], quienes trabajan bajo un escenario Flexible Flow Shop tradicional. En este sentido, la fecha de liberación de cada orden se distribuye uniformemente entre 0 y la media de su tiempo estándar en todas las estaciones y las velocidades de las máquinas siguen esta misma distribución entre 0,7 y 1,3. Por su parte, las fechas de entrega de cada orden fueron obtenidas con base en la aproximación de los autores de la siguiente manera:

𝐷𝐷𝑗 = 𝑅𝐷𝑗 + ∑𝑝𝑠𝑗𝑡

𝑘

𝑡=1

+1

𝑛∑∑ 𝑠𝑗𝑙

𝑡

𝑘

𝑡=1

𝑛

𝑙=1

+ 𝑈(0,1)

[ (𝑛 − 1)∑ ∑

𝑝𝑠𝑗𝑖

𝑣𝑖𝑗𝑡

𝑚𝑡

𝑖=1𝑘𝑡=1

(𝑛)Máx{𝑚𝑡}

]

(20)

A partir de allí, la fecha límite de cada orden se definió como 𝐷𝐿𝑗 = 𝐷𝐷𝑗 +

𝑈(10,50). Finalmente y dado que no se reciben utilidades por la orden 𝑗 después de cumplirse su fecha límite o deadline, el costo asociado a su tardanza se define

como 𝑤𝑗 =𝑢𝑗

(𝐷𝐿𝑗 − 𝐷𝐷𝑗)⁄ tal como lo sugieren Oğuz, Salman y Yalçın [1].

Una vez definidos los parámetros de entrada, en todas las pruebas computacionales necesarias para definir el límite superior alcanzado por el modelo se estableció un tiempo límite de 200.000 segundos de CPU, tomando en cuenta que Oğuz, Salman y Yalçın [1] proponen un tiempo límite de 3.600 segundos en un escenario de una sola máquina. Así mismo, se evaluaron

~ 60 ~

varias instancias del problema de Aceptación de Órdenes y Scheduling combinando diferentes configuraciones de números de órdenes y estaciones. Teniendo en cuenta que la literatura revisada difiere notoriamente del escenario bajo estudio, por lo que no es posible adoptar una metodología de experimentación previa, se diseñó un procedimiento experimental particular que puede observarse en detalle en el Apéndice A. De acuerdo con los experimentos realizados, los tiempos promedio de corrida más cortos se logran en instancias con el número máximo de máquinas en paralelo en todas las estaciones de trabajo. Adicionalmente, es de anotar que en dichos casos se alcanza el mayor valor de la función objetivo. Este resultado es predecible, debido a que una mayor cantidad de recursos disminuye el tiempo en cola de las órdenes y su consecuente finalización en el sistema, por lo que es poco probable que estas se liberen posteriormente a su fecha de entrega o due date, por lo que las decisiones respecto a si se rechaza o no una orden son más fáciles para el modelo. En contraste, el programa tarda en promedio mayor tiempo en aquellas configuraciones que consideran dos o más estaciones con una sola máquina, particularmente si se trata de la última celda de trabajo, en donde se toman las decisiones en torno a si se acepta o no una orden y si se incurre en una penalización por la tardanza en su entrega. A través de los resultados computacionales se concluye que el modelo propuesto permite obtener soluciones óptimas en problemas de hasta 8 órdenes y 5 estaciones. 2.2 APROXIMACIÓN HEURÍSTICA

Como se mencionó en el Capítulo 1, el problema de Aceptación de Órdenes y Scheduling es de carácter NP-Hard y por tal razón, el modelo de programación entera mixta propuesto es capaz de resolver únicamente pequeñas instancias del problema en tiempos razonables. Para situaciones de escala real, es necesario entonces aplicar algoritmos que resuelvan el problema en tiempos considerablemente menores. Por esta razón y con el fin de obtener una solución inicial para el escenario bajo estudio que oriente la búsqueda del algoritmo genético y agilice su convergencia en el óptimo, se ha diseñado una heurística constructiva que se considera una modificación de la herramienta Dynamic Release First-Sequence Best (d-RFSB) originalmente propuesta para una sola máquina por Oğuz, Salman y Yalçın [1].

~ 61 ~

En la herramienta original, se calcula inicialmente para todas las órdenes la relación entre la máxima ganancia que se puede recibir por ella si se acepta y el tiempo que tarda su fabricación, es decir:

𝑢𝑗

𝑝 + 𝑆𝑒𝑡𝑢𝑝

Siendo 𝑝 el tiempo de procesamiento. Una vez se encuentra la orden con la cifra máxima, esta se programa en la máquina, se retira de la lista y se recalcula la relación para las demás órdenes, ahora involucrando el tiempo de alistamiento en que se incurre por el intercambio de tareas y una vez más, se programa la tarea con la cifra máxima. Este procedimiento se repite hasta que todas las órdenes se hayan programado y se rechazan aquellas cuya finalización se da después del deadline. Por su parte, la idea principal del enfoque propuesto, es evaluar la conveniencia de cada orden que arriba al sistema, tomando las decisiones respecto a las órdenes a aceptar de manera dinámica. De esta manera, las órdenes se organizan inicialmente respecto a su fecha de arribo al sistema, para que una vez se libere la primera orden, esta se programe en todas las estaciones de manufactura, eligiendo dentro de ellas la máquina en la que dicha orden alcanza la mayor relación entre la máxima ganancia recibida

por ella, 𝒖𝒋 y el tiempo que tarda en completar su fabricación, en la que se

programa parcialmente. Una vez la orden se ha programado en todas las estaciones, en la última etapa se toma la decisión de aceptarla o no. Si la orden se completa antes de cumplirse su fecha límite de entrega (deadline), se acepta y se asigna definitivamente; en caso contrario, se rechaza y el tiempo de simulación de las máquinas elegidas se devuelve para eliminarla de la secuencia. Posteriormente, se considera la siguiente orden que ha arribado al sistema y el procedimiento se repite hasta que se evalúe la conveniencia de todas ellas. En este contexto, es necesario involucrar en la relación el tiempo actual de la

máquina o 𝑇𝐶𝑢𝑟𝑟𝑒𝑛𝑡, que se ha considerado teniendo en cuenta que si, por ejemplo, la orden encuentra la máxima relación calculada a través de la relación original en una máquina que se encuentra ocupada, tendría que esperar para iniciar su procesamiento cuando pueden encontrarse máquinas disponibles para ello. Bajo esta modificación se garantiza que la orden espere a ser procesada únicamente si todas las máquinas se encuentran ocupadas. Por tanto, la relación se establece como:

𝑢𝑗

𝑝 + 𝑆𝑒𝑡𝑢𝑝 + 𝑇𝐶𝑢𝑟𝑟𝑒𝑛𝑡

De esta manera, el algoritmo que sigue la herramienta diseñada puede describirse como se presenta a continuación.

~ 62 ~

1. Leer la información de entrada 2. Jerarquizar las órdenes respecto a su fecha de arribo al sistema 𝑅𝐷𝑗

3. Establecer: 𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑖, 𝑡] = 0, 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] = 0, 𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑖, 𝑡] = 0

4. Mientras 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] = 0:

Contar el número de órdenes no programadas. Si el número de órdenes no programadas es 0,

Terminar el algoritmo. Encontrar la máxima fecha límite de entrega del conjunto de órdenes no programadas Si 𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑖, 𝑡] ≥ 𝑀𝑎𝑥𝐷𝐿,

Terminar el algoritmo.

5. Mientras no se cumpla el criterio de terminación del algoritmo descrito en 4 calcular para cada orden:

5.1. Para cada máquina 𝑖 en la estación 𝑡: Si 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] ≥ 𝑡 − 1:

𝑅𝑎𝑡𝑖𝑜[𝑗] = 𝑢𝑗 (𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑖, 𝑡] + 𝑃𝑟𝑜𝑐[𝑗, 𝑖, 𝑡] + 𝑆𝑒𝑡𝑢𝑝[𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑖, 𝑡], 𝑗, 𝑡])⁄

Mientras 𝑅𝑎𝑡𝑖𝑜[𝑗] ≥ 𝑚𝑎𝑥 _𝑟𝑎𝑡𝑖𝑜 asignar: 𝑚𝑎𝑥 _𝑟𝑎𝑡𝑖𝑜 = 𝑅𝑎𝑡𝑖𝑜[𝑗] 𝑖 = 𝑚𝑎𝑞 En caso contrario: Terminar paso 5 y retornar a 4.

5.2. Definir: 𝑆𝑡𝑎𝑟𝑡[𝑗, 𝑡] = Max(𝑅𝐷𝑗, 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑗, 𝑡 − 1], 𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑚𝑎𝑞, 𝑡])

Si 𝑆𝑡𝑎𝑟𝑡[𝑗, 𝑡] + 𝑃𝑟𝑜𝑐[𝑗,𝑚𝑎𝑞, 𝑡] + 𝑆𝑒𝑡𝑢𝑝[𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑚𝑎𝑞, 𝑡], 𝑗, 𝑡] ≤ 𝐷𝐿𝑗

asignar: 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] = 𝑇𝑒𝑚_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] + 1

𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑚𝑎𝑞, 𝑡] = 𝑆𝑡𝑎𝑟𝑡[𝑗, 𝑡] + 𝑃𝑟𝑜𝑐[𝑗,𝑚𝑎𝑞, 𝑡] + 𝑆𝑒𝑡𝑢𝑝[𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑚𝑎𝑞, 𝑡], 𝑗, 𝑡] 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑗, 𝑡] = 𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑚𝑎𝑞, 𝑡] 𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒[𝑗, 𝑚𝑎𝑞, 𝑡] = 1 Continuar en 5.1 con 𝑡 = 𝑡 + 1

En otro caso:

𝑅𝑎𝑡𝑖𝑜[𝑗] = 0 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] = 0

Terminar paso 5 y retornar a 4.

6. Calcular para todas las órdenes: Si 𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] = No. Estaciones evaluar en cada máquina de

cada estación:

Mientras 𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒[𝑗, 𝑖, 𝑡] = 1:

~ 63 ~

𝐼𝑑𝑙𝑒[𝑖, 𝑡] = 𝐼𝑑𝑙𝑒[𝑖, 𝑡] + (𝑆𝑡𝑎𝑟𝑡[𝑗, 𝑡] − 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑖, 𝑡], 𝑖, 𝑡]) 𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑖, 𝑡] = 𝑗

Si 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑗, 𝑇] ≤ 𝐷𝐷𝑗, siendo 𝑇 = No. Estacionesentonces:

𝑇𝑎𝑟𝑑𝑎𝑛𝑧𝑎[𝑗] = 0 En otro caso: 𝑇𝑎𝑟𝑑𝑎𝑛𝑧𝑎[𝑗] = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑗, 𝑇] − 𝐷𝐷𝑗

Mostrar inicio y duración de las órdenes asignadas. Calcular utilidad total de las órdenes aceptadas, costo total por

tardanza y costo total del tiempo ocioso de los recursos.

En caso contrario (𝑇𝑒𝑚𝑝_𝐴𝑐𝑐𝑒𝑝𝑡𝑎𝑛𝑐𝑒[𝑗] < No. Estaciones):

Mientras 𝑆𝑒𝑞𝑢𝑒𝑛𝑐𝑒[𝑗, 𝑖, 𝑡] = 1 𝑡_𝑐𝑢𝑟𝑟𝑒𝑛𝑡[𝑚𝑎𝑞, 𝑡] = 𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑖𝑜𝑛[𝑝𝑟𝑒𝑣_𝑜𝑟𝑑𝑒𝑟[𝑖, 𝑡], 𝑖, 𝑡] Calcular penalización total por órdenes rechazadas Terminar algoritmo. 2.3 PROCEDIMIENTO PROPUESTO RESULTADO DE LA INVESTIGACIÓN

Con el objetivo de mejorar los resultados obtenidos a través de la aproximación heurística y hallar una solución más cercana al óptimo, se decidió involucrar un algoritmo genético y aprovechar los beneficios de la recombinación de una población de soluciones, manteniendo el mismo criterio de elección de las máquinas. De esta manera, en lugar de una única secuencia de entrada de las órdenes tomada a partir de su fecha de arribo al sistema, se construyen secuencias aleatorias que arrojen potencialmente mejores resultados. En términos generales, para el problema de interés los cromosomas son una muestra de posibles soluciones, es decir, un subconjunto de secuencias de órdenes tomadas del espacio de candidatos, cuyos genes se representan a través de números aleatorios (Sección 2.3.1). La función de ajuste es el objetivo planteado, es decir, la maximización de las utilidades totales del ejercicio, que involucran la suma de las ganancias obtenidas por las órdenes aceptadas menos la penalización total por las órdenes rechazadas y el costo del tiempo ocioso de los recursos. Para crear nuevas generaciones se decidió emplear el cruce de los mejores padres (Sección 2.3.3) y para mantener la diversidad de la población se emplea la eliminación de soluciones duplicadas y un operador de mutación (Sección 2.3.4). El procedimiento finaliza cuando se alcanza un número máximo de generaciones o cuando no se ha encontrado una mejor solución tras un número especificado de ellas. El siguiente diagrama describe brevemente el procedimiento general del algoritmo genético propuesto.

~ 64 ~

Gráfico 2.3. Diagrama de Flujo Algoritmo Genético propuesto


~ 65 ~

2.3.1 Construcción de la Población Inicial

En torno a la representación del escenario, considerar una permutación de trabajos u órdenes es una aproximación sencilla y ampliamente usada en gran cantidad de investigaciones previas relacionadas con el uso de algoritmos genéticos en el problema flow-shop [5, 4]. Por tanto, en la aproximación propuesta se aplica un código basado en permutación (o código de trabajos) usando números enteros como el enfoque de codificación de los cromosomas, los cuales fueron generados como se muestra a continuación. Como primer individuo se involucró la secuencia obtenida a través de la aproximación heurística. Para los demás individuos de la población y tomando un problema de 𝑁 órdenes se generaron en primera instancia 𝑁 números aleatorios uniformemente distribuidos en [0,1] que fueron reordenados ascendentemente, mientras que los números enteros de 1 a 𝑁 que indican la orden correspondiente se reajustan de forma consecuente, tal como lo sugieren Rom y Slotnick [6]. El lector puede remitirse a Bean [7] quien presenta una discusión en torno a este tipo de representación. Por ejemplo, para un escenario de 5 órdenes se tiene:

La secuencia obtenida es entonces:

Este procedimiento es repetido hasta que se construye la población de soluciones deseada. Para cada individuo se desarrolla el proceso de asignación que sigue la heurística y una vez se alcanza el final de la secuencia se almacena el conjunto de órdenes aceptadas y el valor de la función objetivo. Cuando se han evaluado todos los individuos, se guarda la mejor solución. De esta manera, el algoritmo genético complementa la aproximación heurística presentada construyendo un espacio de soluciones diverso, mientras mantiene las mejores soluciones encontradas.

~ 66 ~

2.3.2 Generaciones sucesivas

Para crear nuevas generaciones se llevan a cabo los siguientes pasos: 1. Evaluar el valor de la función objetivo de todos los individuos y ordenarlos

en forma descendente respecto a esta cifra. 2. Mantener las soluciones cuya posición se encuentre dentro de la

probabilidad de cruce. Por ejemplo, si la población cuenta con 100 individuos y la probabilidad de cruce es 0.3, se seleccionan los 30 mejores padres para realizar el cruce.

3. Llevar a cabo el cruce de los individuos seleccionados que reemplazarán los peores individuos, tal como se presenta en el siguiente inciso. Para el ejemplo presentado, la primera y segunda solución son usadas para generar dos hijos que sustituirán aquellos ubicados en las posiciones 71 y 72, proceso que se repite de manera que se reemplacen las peores 30 soluciones.

2.3.3 Cruce El algoritmo genético propuesto emplea un cruce en dos puntos o two-point crossover para generar una nueva descendencia. A pesar que tal como lo mencionan Sivanandam y Deepa [8] fragmentar más la cadena reduce el desempeño del algoritmo debido a que los bloques de construcción son más propensos a quebrarse, su ventaja radica en que el espacio del problema puede examinarse más exhaustivamente. Para realizarlo, inicialmente se generan aleatoriamente dos números enteros 𝑛1

y 𝑛2 entre 1 y 𝑁, donde 𝑛1 y 𝑛2 son posiciones diferentes en la secuencia. Si 𝑛1 > 𝑛2 entonces las partes externas de la secuencia (esto es, las órdenes que

se encuentran antes de 𝑛2 y después de 𝑛1) son intercambiadas para generar

un nuevo individuo. Por el contrario, si 𝑛2 > 𝑛1 la descendencia se genera intercambiando las órdenes posicionadas entre 𝑛1 y 𝑛2. Por ejemplo, considerando los padres:

Caso 1: si 𝑛1 = 7 ∧ 𝑛2 = 3, entonces:

~ 67 ~

Caso 2: si 𝑛1 = 2 ∧ 𝑛2 = 8, entonces:

Como se observa, la secuencia resultante no es en general factible, dado que algunas órdenes pueden estar duplicadas mientras otras pueden no aparecer. La nueva secuencia debe entonces corregirse para reemplazar las tareas duplicadas por las inexistentes. De esta forma y tomando el ejemplo anterior, la descendencia modificada sería: Caso 1: si 𝑛1 = 7 ∧ 𝑛2 = 3

Caso 2: si 𝑛1 = 2 ∧ 𝑛2 = 8

De acuerdo con Rom y Slotnick [6], es posible también realizar el cruce en la secuencia original de números aleatorios y posteriormente reordenarla para generar una nueva secuencia, lo cual resultaría siempre en un individuo factible. Sin embargo, según los experimentos de los autores el desempeño de este cruce es inferior en términos de tiempo computacional y valor de la función objetivo. 2.3.4 Diversidad de la población

El algoritmo genético propuesto mantiene la diversidad de la población a través de la eliminación de soluciones duplicadas y un operador de mutación, combinación que fue elegida con base en los experimentos computacionales de Rom y Slotnick [6], quienes observaron mejores resultados al comparar estas técnicas con otras alternativas. Para el primer caso y teniendo en cuenta que comparar cada gen de las secuencias hasta encontrar soluciones duplicadas aumenta el tiempo computacional, se decidió comparar el valor de la función objetivo de las soluciones. Si dos individuos alcanzan el mismo valor, se lleva a cabo una

~ 68 ~

mutación en uno de ellos para eliminar el individuo duplicado, lo que en la literatura se conoce como una eliminación de clones. Así mismo, cada vez que se crea una nueva generación, se asocia una probabilidad de mutación a cada individuo, la cual se lleva a cabo eligiendo dos posiciones aleatorias en la secuencia e intercambiando las órdenes que hay en ellas, lo que se conoce en la literatura como Pairwise Interchange, tal como se muestra en el siguiente ejemplo.

2.3.5 Criterio de Terminación

En estudios preliminares, el algoritmo se programó para terminar después de 2000 generaciones, con un límite de 300 sin variación, observándose que a partir de máximo 40 se obtenían las mejores soluciones, lo que se considera una característica positiva del procedimiento. En consecuencia, se decidió realizar una prueba adicional a 20 problemas aleatorios correspondientes a 4 instancias del escenario elegido, para registrar el número máximo de generaciones requeridas, tal como se observa en la Tabla 2.1.

Máximo Promedio Mínimo

7 x 5 7 4,45 3

8 x 7 7 4,95 3

20 x 10 13 10,35 8

30 x 10 15 11,05 8

Tabla 2.1. Generaciones requeridas para encontrar las mejores soluciones

Con base en estos resultados y con el fin de abarcar cualquier caso y no incrementar ineficientemente el tiempo de corrida del algoritmo, se emplea un número máximo de 70 generaciones. 2.3.6 Parámetros del Algoritmo Genético

Con el fin de diseñar un algoritmo genético para contrastar con los resultados de la heurística y el modelo matemático, se llevó a cabo un experimento

factorial 2𝑘 con puntos centrales teniendo en cuenta los factores: tamaño de población y probabilidades de mutación y cruce. La estrategia de experimentación se guía por el objetivo de determinar aquellos factores que pueden ser importantes o que pueden influenciar la variable de respuesta, en este caso, el valor de la función objetivo escogida, así como

~ 69 ~

establecer su cuantía para garantizar un valor lo más cercano posible al óptimo sin penalizar excesivamente el tiempo de corrida requerido. De acuerdo con Montgomery, D.C. [9], el enfoque correcto para tratar con múltiples factores es conducir un experimento factorial, una estrategia experimental en la que los factores varían juntos en lugar de hacerlo uno a la vez, permitiendo al experimentador investigar los efectos individuales de cada factor y determinar si existe interacción entre ellos. En los siguientes numerales, se presentan brevemente los fundamentos teóricos que apoyan el diseño experimental, así como las conclusiones fundamentales del análisis estadístico elaborado. 2.3.6.1 Definiciones básicas de los Diseños Factoriales Gran cantidad de experimentos, entre los que se cuenta el estudio de pertinencia a esta investigación, involucran el análisis de los efectos de uno o más factores. Tal como lo menciona Montgomery, D.C. [9], en un diseño factorial para cada prueba o réplica del experimento se investigan todas las posibles combinaciones de los niveles de los factores. El efecto de un factor se define como el cambio en la respuesta producida por una alteración en sus niveles. Esto se denomina efectos principales debido a que se refiere a los factores de interés primordiales para el experimento. Por ejemplo, en un experimento bi-factorial con dos niveles en cada uno, denominados “alto” y “bajo” que se denotan como “-” y “+” respectivamente, el efecto principal del factor 𝐴 puede considerarse como la diferencia entre las respuestas promedio en el nivel inferior y en el nivel superior. En algunos estudios, es posible observar que la diferencia en la respuesta entre los diferentes niveles de un factor no es la misma en todos los niveles de los demás factores. Cuando esto ocurre, se dice que existe una interacción entre ellos. Generalmente, cuando una interacción toma un valor alto, los efectos principales correspondientes tienen escaso significado práctico. Una interacción significativa a menudo enmascara la importancia de los efectos principales. En general, un experimento bi-factorial se representa como aparece en la siguiente tabla. El orden en que se toman las observaciones es elegido al azar, de manera que el diseño sea completamente aleatorio.

~ 70 ~

F

acto

r 𝐴

Factor 𝐵

1 2 … 𝑏

1

𝑌111 , 𝑌112 , … ,𝑌11𝑛

𝑌121 , 𝑌122 , … , 𝑌12𝑛

𝑌1𝑏1 , 𝑌1𝑏2 , … , 𝑌1𝑏𝑛

2

𝑌211 , 𝑌212 , … , 𝑌21𝑛

𝑌221 , 𝑌222 , … ,𝑌22𝑛

𝑌2𝑏1 , 𝑌2𝑏2 , … ,𝑌2𝑏𝑛

…

𝑎

𝑌𝑎11 , 𝑌𝑎12 , … ,𝑌𝑎1𝑛

𝑌𝑎21 , 𝑌𝑎22 , … , 𝑌𝑎2𝑛

𝑌𝑎𝑏1 , 𝑌𝑎𝑏2 , … , 𝑌𝑎𝑏𝑛

Tabla 2.2. Arreglo general de un diseño bi-factorial

Fuente: Elaboración Propia. Adaptado de: Montgomery, 2013.

Estas observaciones pueden describirse por un modelo. A pesar que existen numerosas formas de escribirlo, se ha escogido el modelo de efectos que para el caso de este experimento se representa como:

𝑦𝑖𝑗𝑘 = 𝜇 + 𝜏𝑖 + 𝛽𝑗 + (𝜏𝛽)𝑖𝑗 + 𝜖𝑖𝑗𝑘 {𝑖 = 1,2,… , 𝑎𝑗 = 1,2,… , 𝑏𝑘 = 1,2… , 𝑛

Siendo 𝜇 el efecto principal general, 𝜏𝑖 el efecto del 𝑖-ésimo nivel del factor fila 𝐴, 𝛽𝑗 el efecto del 𝑗-ésimo nivel del factor columna 𝐵, (𝜏𝛽)𝑖𝑗 el efecto de la

interacción entre 𝜏𝑖 y 𝛽𝑗 y 𝜖𝑖𝑗𝑘 el componente aleatorio del error.

En este contexto, los factores 𝐴 y 𝐵 son de igual interés. Específicamente es de pertinencia contrastar las hipótesis relacionadas con la equidad de los efectos, es decir:

𝐻0: 𝜏1 = 𝜏2 = ⋯ = 𝜏𝑎 = 0 𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 𝜏𝑖 ≠ 0

Y:

𝐻0: 𝛽1 = 𝛽2 = ⋯ = 𝛽𝑏 = 0 𝐻𝑎 : 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 𝛽𝑗 ≠ 0

Así mismo, es necesario determinar si los factores interactúan; por tanto, se formulan las siguientes hipótesis:

𝐻0: (𝜏𝛽)𝑖𝑗 = 0

𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 (𝜏𝛽)𝑖𝑗 ≠ 0

~ 71 ~

Ahora bien, entre las ventajas principales de los diseños factoriales se cuenta que hacen el uso más eficiente de los datos experimentales, en tanto emplean todas las observaciones para calcular los efectos de los factores y su interacción. De acuerdo con Montgomery, D.C. [9], ninguna otra estrategia de experimentación usa de forma tan eficiente los datos. De otro lado, permiten a los efectos de un factor ser estimados en varios niveles de otros factores, arrojando conclusiones válidas sobre un rango de condiciones experimentales y finalmente, son necesarios cuando las interacciones pueden estar presentes para evitar conclusiones erróneas.

2.3.6.2 El diseño 𝟐𝟑 En este caso, elegido para la experimentación de los diferentes parámetros del algoritmo genético que sustenta el procedimiento propuesto, resultado de esta investigación, se supone que existen tres factores: 𝐴, 𝐵 y 𝐶, cada uno en dos

niveles. Este escenario se conoce en la literatura como un diseño factorial 𝟐𝟑 y se representa a través del modelo de efectos como:

𝑦𝑖𝑗𝑘𝑙 = 𝜇 + 𝜏𝑖 + 𝛽𝑗 + 𝛾𝑘 + (𝜏𝛽)𝑖𝑗 + (𝜏𝛾)𝑖𝑘 + (𝛽𝛾)𝑗𝑘 + (𝜏𝛽𝛾)𝑖𝑗𝑘

+ 𝜖𝑖𝑗𝑘𝑙 {

𝑖 = 1,2,… , 𝑎𝑗 = 1,2,… , 𝑏𝑘 = 1,2… , 𝑐𝑙 = 1,2,… , 𝑛

Las ocho combinaciones posibles pueden representarte geométricamente como un cubo, tal como se muestra en el Gráfico 2.4.

Gráfico 2.4. Vista geométrica del diseño


El Gráfico 2.5, muestra las tres posibilidades [9] de representar las ocho

corridas del diseño 23. Inicialmente, se presenta la notación “+” / “-”, denominada comúnmente codificación geométrica, ortogonal o de efectos. La

~ 72 ~

segunda forma hace referencia al uso de letras minúsculas para etiquetar la combinación de factores. La notación final consiste en usar +1 y -1 en lugar de + y -. Corrida Factor Etiquetas Factor

A B C A B C 1 - - - (1) -1 -1 -1

2 + - - a +1 -1 -1

3 - + - b -1 +1 -1

4 + + - ab +1 +1 -1

5 - - + c -1 -1 +1

6 + - + ac +1 -1 +1

7 - + + bc -1 +1 +1

8 + + + abc +1 +1 +1

Gráfico 2.5. Matriz del diseño


El lector puede consultar en detalle el análisis estadístico pertinente en el capítulo 6 de Montgomery, D.C. [9]. Una vez esbozados los fundamentos estadísticos que subyacen el diseño de experimentos elegido, se presenta a continuación el experimento factorial elaborado para la elección de los parámetros del algoritmo genético. 2.3.6.3 Experimento factorial empleado El experimento propuesto consistió de 900 pruebas experimentales ordenadas de manera aleatoria, realizadas en un problema de 7 órdenes y 5 estaciones escogido al azar, que se llevaron a cabo de la siguiente manera. Teniendo en cuenta que de acuerdo con Montgomery, D.C. [9] el experimento debe tener como mínimo 2 réplicas para que sea posible estimar el error interno o “puro” y considerando la aleatoriedad natural del algoritmo relacionada con la obtención de la población inicial y los operadores genéticos, se realizaron en las 8 corridas 100 observaciones, registrándose el valor de la función objetivo alcanzado y el tiempo necesario para derivar una solución. De acuerdo con la literatura relacionada y algunas pruebas preliminares realizadas por el autor, los niveles de cada factor analizados se establecieron tal como se muestra en la Tabla 2.3.

~ 73 ~

Factor

Niveles

Bajo Punto Central Alto

Tamaño Población 100 200 300

Probabilidad Cruce 0.1 0.5 0.9

Probabilidad Mutación 0.1 0.3 0.5

Tabla 2.3. Factores y niveles analizados

El punto central, fue añadido siguiendo la recomendación de Montgomery, D.C. [9], quien advierte que para los experimentos conducidos en situaciones donde no existe información previa relacionada con la variabilidad del proceso, es de gran utilidad adicionar puntos centrales con el fin de estimarla. De acuerdo con el autor, si la magnitud de la variabilidad parece razonable, tiene sentido continuar con el experimento; en caso contrario, es necesario analizar las razones de dicha variabilidad antes de continuar con el resto del estudio. Por tanto, se agregan 100 réplicas adicionales, correspondientes al punto 𝑥𝑖 =0 (𝑖 = 1,2,… , 𝑘) El análisis estadístico desarrollado se puede observar en su totalidad en el Apéndice B. De acuerdo con los resultados experimentales, es posible concluir que la mejor función objetivo se alcanza con un tamaño de población de 200 individuos, una tasa de cruce de 0.5 y una probabilidad de mutación de 0.3. 2.4 CONCLUSIONES PARCIALES

En este capítulo, se presentaron las herramientas de ingeniería propuestas para dar solución al escenario de Aceptación de Órdenes y Scheduling seleccionado, las cuales involucran en primera instancia, el modelo de programación entera mixta (MIP) que considera la maximización de las utilidades del ejercicio, compuesta por las ganancias percibidas por las órdenes aceptadas, menos la penalización por las órdenes rechazadas y el costo de tiempo ocioso de los recursos de cada estación y que de acuerdo con los resultados experimentales, brinda una solución a escenarios de máximo 8 órdenes y 5 estaciones en un tiempo computacional límite de 200.000 segundos de CPU. Debido a la complejidad del escenario y con el fin de obtener una solución inicial para el ambiente bajo estudio que oriente la búsqueda del algoritmo genético y agilice su convergencia en el óptimo, se propuso una heurística constructiva que se considera una modificación de la herramienta Dynamic Release First-Sequence Best (d-RFSB), que evalúa la conveniencia de las órdenes que arriban al sistema y las programa en todas las celdas de manufactura eligiendo dentro de ellas la máquina en la que dicha orden

~ 74 ~

alcanza la mayor relación entre la máxima ganancia recibida por ella, 𝑢𝑗 y el

tiempo que tarda en completar su fabricación. Con el objetivo de mejorar los resultados obtenidos a través de esta heurística y hallar una solución más cercana al óptimo, sin penalizar excesivamente el tiempo computacional requerido para derivarlas, se diseña finalmente el procedimiento propuesto resultado de la investigación, que involucra un algoritmo genético para aprovechar los beneficios de la recombinación de una población de soluciones y mantiene el mismo criterio de elección de las máquinas de la heurística. Este algoritmo, aplica como enfoque de codificación de los cromosomas un código basado en permutación o código de trabajos usando números enteros, siendo el primer individuo la secuencia obtenida a través de la aproximación heurística. Para crear una nueva generación, se emplea un cruce en dos puntos o two-point crossover y para mantener la diversidad de la población se emplea una eliminación de clones y un operador de mutación en el cual se eligen dos posiciones aleatorias en la secuencia y se intercambian las órdenes que hay en ellas, lo que se conoce en la literatura como Pairwise Interchange. Como criterio de parada y tomando en cuenta que la herramienta no requiere gran número de generaciones para brindar una buena solución, el algoritmo se detiene al completar 70 generaciones. Con el fin de diseñar una herramienta para contrastar con los resultados de los

demás enfoques, se formula un experimento 23 con puntos centrales cuyos resultados permitieron elegir un tamaño de población de 200 individuos y tasas de cruce y mutación de 0.5 y 0.3, respectivamente. 2.5 BIBLIOGRAFÍA

[1] C. Oğuz, F. S. Salman y Z. B. Yalçın, «Order acceptance and scheduling decisions in make-to-order systems,» Int. J. Production Economics, vol. 125, pp. 200-211, 2010.

[2] R. Graham, E. Lawler, J. Lenstra y A. Rinnooy Kan, «Optimization and approximation in deterministic sequencing and scheduling: A survey,» Annals of Discrete Mathematics, vol. 5, pp. 287-326, 1979.

[3] M. Pinedo, Scheduling. Theory, Algorithms and Systems, Springer, 2008.

[4] J. Jungwattanakit, M. Reodecha, P. Chaovalitwongse y F. Werner, «A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria,» Computers & Operations Research, vol. 36(2), pp. 358-78, 2009.

[5] F. Werner, On the solution of special sequencing problems. Dissertation., Germany: TU Magdeburg, 1984.

[6] W. O. Rom y S. A. Slotnick, «Order Acceptance Using Genetic Algorithms,» Computers & Operations Research, vol. 36, pp. 1758-67, 2009.

~ 75 ~

[7] J. Bean, «Genetic algorithms and random keys for sequencing and optimization.,» ORSA Journal on Computing, vol. 6, pp. 154-160, 1994.

[8] S. Sivanandam y S. Deepa, Introduction to Genetic Algorithms, Springer, 2008.

[9] D. Montgomery, Design and Analysis of Experiments, 8th ed., John Wiley & Sons, Inc., 2013.

~ 76 ~

CAPÍTULO 3

VERIFICACIÓN DEL PROCEDIMIENTO PROPUESTO PARA EL

ESCENARIO DE ACEPTACIÓN DE ÓRDENES Y SCHEDULING EN

AMBIENTES FLEXIBLE FLOW SHOP

De acuerdo con los objetivos planteados para la investigación, en este capítulo se presentará la verificación teórica del procedimiento propuesto para dar solución al escenario de Aceptación de Órdenes y Scheduling seleccionado, a través del análisis de los resultados de su implementación en una serie de problemas aleatorios considerando inicialmente dos instancias, una de ellas en la que el software de programación matemática GAMS, superó el tiempo límite de corrida. Como último paso del análisis, se emplean dos instancias de mayor tamaño, de manera que sea posible observar si el procedimiento propuesto, ejecutado en el software Visual Basic para Excel, también sobrepasa dicho límite. La metodología escogida para el desarrollo de este inciso, se presenta en la siguiente figura.

Gráfico 3.1. Metodología diseñada para el Capítulo 3


Comparación resultados Modelo de programación entera mixta (MIP) y procedimiento

propuesto en términos del valor de la función objetivo y el tiempo de corrida.

Diseño de experimentos de muestras pareadas: eliminar sistemáticamente el efecto sobre la comparación estadística de los parámetros aleatorios de cada problema.

Elección tamaño de la muestra e instancias del problema

Ejecución de cada problema en GAMS y Visual Basic

Importe de datos generados en Visual Basic en GAMS

Comparación estadística. Conclusiones del análisis.

Verificación desempeño

procedimiento

propuesto

Instancias de mayor tamaño para verificar si el tiempo de convergencia del procedimiento supera los 200.000 segundos de CPU definidos como límite.

Elección tamaño de la muestra e instancias del problema

Ejecución de cada problema en Visual Basic

Conclusiones del análisis

~ 77 ~

3.1 COMPARACIÓN DEL MODELO DE PROGRAMACIÓN ENTERA MIXTA Y EL PROCEDIMIENTO PROPUESTO

Con el objetivo de comparar las herramientas de ingeniería diseñadas, se recurre a un diseño de experimentos de muestras pareadas, para el que se seleccionaron completamente al azar 60 problemas ejecutados en las dos herramientas objeto de contraste y para los que se registró el valor de la función objetivo, así como el tiempo de corrida requerido por el modelo de programación entera mixta (MIP) y por el procedimiento propuesto, para derivar dicha solución. La elección de este tipo de experimento, se debe a que los parámetros de entrada de cada problema representan un factor adicional de aleatoriedad que es controlable, por lo que de acuerdo con Montgomery, D.C. [1], debe implementarse una técnica de bloques para eliminar sistemáticamente su efecto en la comparación estadística de los tratamientos. De esta manera, cada problema representa un bloque. El experimento se llevó a cabo considerando instancias de 7 órdenes × 5

estaciones y 8 órdenes × 7 estaciones, esta última, en la que como se puede observar en el Apéndice A, el modelo de programación entera mixta ejecutado en GAMS superó el tiempo límite de corrida establecido 200.000 segundos de CPU. Esta instancia, fue involucrada de manera que pudiera compararse el desempeño del procedimiento propuesto en una instancia problemática para el enfoque exacto. De acuerdo con Montgomery, D.C. [1], es posible escribir el modelo estadístico que representa los datos de este experimento como:

𝑦𝑖𝑗 = 𝜇𝑖 + 𝛽𝑗 + 𝜖𝑖𝑗 {𝑖 = 1,2, . . , 𝑛𝑗 = 1,2, . . , 𝑚

Donde 𝑦𝑖𝑗 es la observación del tratamiento 𝑖 –que en este caso se refiere a las

dos herramientas bajo contraste– en el problema 𝑗, 𝜇𝑖 es la media real del 𝑖-ésimo tratamiento, 𝛽𝑗 es el efecto sobre las variables de respuesta debido al 𝑗-

ésimo problema y 𝜖𝑖𝑗 es el error aleatorio del experimento con media 0 y

varianza 𝜎𝑖2.

En el caso de interés, se computan las diferencias pareadas:

𝑑𝑗 = 𝑦1𝑗 − 𝑦2𝑗 𝑗 = 1,2, . . ,60

Siendo el valor esperado de dicha diferencia:

𝜇𝑑 = 𝐸(𝑑𝑗)

𝜇𝑑 = 𝐸(𝑦1𝑗 − 𝑦2𝑗)

𝜇𝑑 = 𝐸(𝑦1𝑗) − 𝐸(𝑦2𝑗)

~ 78 ~

𝜇𝑑 = (𝜇1 + 𝛽𝑗) − (𝜇2 + 𝛽𝑗)

𝜇𝑑 = 𝜇1 − 𝜇2 De esta manera, se realizan deducciones respecto a las diferencias de las

medias de los dos tratamientos 𝜇1 − 𝜇2, emitiendo conclusiones sobre la media

de las diferencias, 𝜇𝑑. Es de notar que el efecto adicional de los problemas o bloques 𝛽𝑗 se omite del análisis cuando las observaciones se emparejan en

esta forma.

De esta manera, probar 𝐻0: 𝜇1 = 𝜇2 es equivalente a la prueba de hipótesis:

𝐻0: 𝜇𝑑 = 0 𝐻𝑎: 𝜇𝑑 ≠ 0

Así pues, los resultados obtenidos para los tamaños de problema considerados, se muestran en los siguientes numerales. En todos ellos, también se incluyeron las observaciones asociadas a la heurística, de forma que pudieran realizarse conclusiones adicionales sobre su desempeño. El análisis estadístico, sin embargo, no comprende este tratamiento, debido a que la herramienta se encuentra altamente involucrada en el procedimiento propuesto. 3.1.1 Instancia de 7 órdenes × 5 estaciones Los resultados correspondientes a los valores de la función objetivo alcanzados con las tres herramientas diseñadas, así como el tiempo que tarda cada una en derivar una solución se muestran en la Tabla 3.1 y en los Gráficos 3.2 y 3.3.

Problema GAMS PROCEDIMIENTO

Z* - z T* - t HEURÍSTICA

Z t Z t Z t

1 3927,066 1419,524 3673,995 184,231 253,071 1235,293 601,829 0,923

2 4220,792 1093,335 4204,052 197,594 16,740 895,741 409,547 0,749

3 4318,107 1275,918 4135,983 181,535 182,124 1094,383 786,719 0,659

4 4236,400 1758,930 4155,625 184,594 80,775 1574,336 1187,989 0,967

5 3898,056 793,460 3645,782 197,882 252,275 595,578 373,322 0,694

6 4090,149 209,698 3877,677 187,539 212,472 22,159 906,431 0,966

7 4310,693 299,486 4134,465 177,242 176,228 122,244 425,444 0,822

8 3975,570 648,016 3681,779 182,094 293,791 465,922 1495,096 0,992

9 4114,956 914,262 3824,817 177,266 290,138 736,996 1196,298 0,858

10 4297,851 1724,586 4138,877 196,555 158,974 1528,031 1337,769 0,753

11 4482,269 1817,287 4326,443 177,477 155,826 1639,810 1239,005 0,951

12 4400,213 530,150 4361,832 178,606 38,381 351,544 779,938 0,830

13 4327,143 1416,354 4327,143 193,402 0,000 1222,952 1034,598 0,740

14 4211,035 1683,271 3947,732 200,953 263,303 1482,318 729,087 0,981

15 3798,344 1199,699 3781,799 192,227 16,544 1007,472 1389,285 0,999

~ 79 ~

16 3943,382 1014,669 3812,527 185,227 130,855 829,442 1218,268 0,991

17 3958,870 977,370 3893,283 181,590 65,587 795,780 1061,269 0,982

18 4211,796 1463,206 4067,101 175,375 144,695 1287,831 722,461 0,992

19 4337,643 1862,836 4261,371 190,465 76,272 1672,371 1350,835 0,989

20 4191,362 1705,728 3994,813 185,375 196,549 1520,353 1491,874 0,961

21 4489,530 931,077 4296,113 189,566 193,418 741,511 1622,026 0,875

22 4102,485 1601,235 3862,779 191,809 239,706 1409,426 338,687 0,699

23 3963,531 1475,286 3757,106 186,727 206,425 1288,559 235,641 0,641

24 3679,795 566,723 3563,118 191,512 116,678 375,212 543,548 0,941

25 4156,090 343,712 4156,090 179,902 0 163,809 109,330 0,680

26 4026,788 471,147 3926,974 197,922 99,814 273,225 1695,476 0,945

27 4208,553 406,743 4009,990 194,344 198,563 212,399 722,794 0,805

28 4461,065 1314,291 4422,980 200,844 38,085 1113,447 1635,652 0,961

29 4710,818 878,922 4705,520 198,914 5,298 680,008 910,755 1,016

30 4187,148 1995,646 4013,632 200,875 173,516 1794,771 1578,919 0,844

31 3323,322 1076,773 3174,568 189,195 148,754 887,578 894,268 0,703

32 3617,547 214,776 3470,668 189,570 146,879 25,206 1185,901 0,914

33 3505,170 868,953 3395,389 185,266 109,781 683,687 760,406 0,789

34 3304,371 669,838 3063,568 189,938 240,803 479,901 773,586 0,727

35 4364,510 820,736 4249,673 193,008 114,836 627,728 2141,307 0,961

36 3621,310 1306,860 3470,221 194,758 151,089 1112,103 1142,657 0,992

37 4560,783 1838,246 4269,360 196,156 291,423 1642,089 1392,115 0,969

38 4286,914 263,655 4246,533 189,555 40,381 74,100 1720,142 0,961

39 4532,164 1873,267 4266,825 192,680 265,339 1680,587 1198,614 0,969

40 4256,322 1859,993 4151,493 179,500 104,829 1680,493 1962,662 0,992

41 3771,440 741,779 3635,953 181,836 135,487 559,944 663,659 0,977

42 4144,257 1176,998 3946,852 177,625 197,405 999,373 749,798 0,965

43 3936,674 1882,856 3707,160 191,445 229,514 1691,411 1739,586 0,957

44 4082,657 1881,545 4075,709 192,633 6,947 1688,912 2240,498 0,949

45 4127,971 752,561 4063,886 199,039 64,086 553,522 1462,100 0,969

46 4549,917 442,209 4479,919 198,273 69,998 243,936 1608,087 0,961

47 4251,895 929,257 4241,259 179,617 10,637 749,640 1737,779 0,957

48 4382,163 949,593 4248,669 185,141 133,494 764,452 198,790 0,977

49 4135,913 1733,389 3952,130 191,414 183,783 1541,975 579,465 0,973

50 4187,043 797,774 3916,402 176,504 270,641 621,270 1059,576 0,977

51 4297,197 1188,580 4209,473 198,586 87,724 989,994 888,477 0,984

52 4003,959 1035,758 3978,587 198,258 25,372 837,500 543,400 0,949

53 4247,124 1972,496 4187,674 200,508 59,450 1771,988 659,642 0,973

54 4266,820 1930,283 4198,573 193,227 68,247 1737,056 1020,449 0,965

55 4118,088 1843,829 4038,399 193,813 79,689 1650,017 1284,983 0,969

56 4145,001 1945,494 4082,286 175,805 62,715 1769,689 234,436 0,949

57 3992,993 258,923 3917,793 180,668 75,201 78,255 1271,027 0,984

58 4279,048 229,057 4239,519 191,156 39,529 37,900 1167,822 0,969

~ 80 ~

59 3736,821 1028,240 3660,630 179,641 76,191 848,599 1731,123 0,969

60 4106,849 1332,946 4066,638 191,656 40,211 1141,290 1907,489 0,969

Tabla 3.1. Datos obtenidos Instancia 7 órdenes y 5 estaciones


Gráfico 3.3. Resultados Tiempo de Corrida Instancia de 7 órdenes y 5 estaciones

~ 81 ~

Tomando inicialmente los valores de la función objetivo obtenidos con las herramientas diseñadas, se calcularon de forma preliminar los estadísticos descriptivos para las dos muestras, con los que se construye la Tabla 3.2 y el Gráfico 3.4, que involucra además los resultados de la heurística.

Estadísticos de muestras relacionadas

Media N Desviación típ. Error típ. de la

media

Par 1 MIP_FO 4122,895709 60 288,7148125 37,2729220

Proc_FO 3992,786732 60 312,1966068 40,3044086

Tabla 3.2. Estadísticos valores Función Objetivo Instancia de 7 órdenes y 5 estaciones

Gráfico 3.4. Media de valores Función Objetivo Instancia de 7 órdenes y 5 estaciones

De esta forma, la media de las diferencias del valor de la función objetivo obtenidas por el modelo de programación entera mixta y el procedimiento propuesto alcanza 130,109 unidades monetarias, lo que se considera un muy buen resultado. Así mismo, se encuentran 2 casos en los que el procedimiento propuesto arroja una solución óptima. De otra parte, las diferencias de la heurística respecto al método exacto y el procedimiento propuesto son en promedio de 3038,73 y 2908,625 unidades monetarias, respectivamente, notándose en todos los casos resultados inferiores frente al procedimiento, por lo que es posible deducir que involucrar

~ 82 ~

un algoritmo genético favorece el hallazgo de soluciones más cercanas al óptimo. Con el objetivo de determinar si la diferencia entre las herramientas bajo estudio es estadísticamente significativa, se realiza una prueba de comparación de medias, cuya elección debe sustentarse inicialmente en la normalidad de las observaciones, por lo cual se elige una prueba de Kolmogorov-Smirnov, debido a su buen ajuste en muestras mayores a 50 datos, para la que se formula la siguiente prueba de hipótesis.

𝐻0: los datos se distribuyen normalmente

𝐻𝑎: no se puede asumir normalidad de los datos

Los resultados se muestran en la Tabla 3.3.

Pruebas de normalidad

Kolmogorov-Smirnova Shapiro-Wilk

Estadístico gl Sig. Estadístico gl Sig.

MIP_FO ,128 60 ,016 ,951 60 ,017

Proc_FO ,092 60 ,200* ,961 60 ,053

*. Este es un límite inferior de la significación verdadera.

a. Corrección de la significación de Lilliefors

Tabla 3.3. Prueba de normalidad valores Función Objetivo Instancia de 7 órdenes y 5 estaciones

Como se observa, a pesar que el p-valor del enfoque exacto es inferior a un nivel de significancia del 5%, se decide disminuir el nivel de la prueba a 1% y de esta manera aceptar la hipótesis nula y concluir que los datos se distribuyen normalmente. Una vez comprobado el supuesto de normalidad, se realiza con ayuda del software estadístico SPSS una prueba t para muestras pareadas para la que se formula la prueba de hipótesis:

𝐻0: 𝜇𝑑 = 0

𝐻𝑎: 𝜇𝑑 ≠ 0 Y cuyos resultados se muestran a continuación.

~ 83 ~

Prueba de muestras relacionadas

Diferencias relacionadas t gl Sig.

(bilateral) Media Desviación

típ.

Error típ. de

la media

95% Intervalo de confianza

para la diferencia

Inferior Superior

Par 1 MIP_FO -

Proc_FO

130,1089768 86,4889554 11,1656761 107,7665104 152,4514431 11,653 59 ,000

Tabla 3.4. Prueba t muestras pareadas. Valores Función Objetivo Instancia de 7 órdenes

y 5 estaciones

Teniendo en cuenta que se alcanza un p-valor de 0, existen argumentos estadísticos para rechazar la hipótesis nula a cualquier nivel de significación. Por tanto, es posible concluir que hay diferencias entre las muestras. Con base en esta conclusión, se realizó una fragmentación de la muestra en 10 problemas para los que las diferencias entre una herramienta y otra alcanzan una diferencia máxima de 16 unidades monetarias, obteniéndose un p-valor de 0,023 que obliga a rechazar la hipótesis nula aun cuando la diferencia obtenida es bastante favorable. De acuerdo con Montgomery, D.C. [1] en todo diseño experimental es necesario en este punto reconocer la diferencia entre la significancia práctica y la estadística, dado que según el autor, no porque las condiciones del estudio arrojen medias estadísticamente diferentes, esto asegura que dicha diferencia sea lo suficientemente grande para tener un valor práctico. En consecuencia, se decidió analizar en detalle los resultados arrojados en ambas muestras, observándose una media de las diferencias de 130,109 unidades y un valor máximo de casi 294 unidades en valores de función objetivo que alcanzan como mínimo 3304,3708 unidades monetarias. Adicionalmente, se agregaron tres medidas de desempeño, asociadas a las desviaciones mínima, máxima y promedio, la cual se calculó para todo el análisis como:

𝐷𝑒𝑠𝑣. 𝑃𝑟𝑜𝑚𝑒𝑑𝑖𝑜 =1

𝑛∑Upper Bound𝑖 − Resultado Procedimiento𝑖

𝑛

𝑖=1

Siendo el límite superior el resultado arrojado por el modelo de programación entera mixta. Para esta instancia, se calcula una desviación mínima de 0%, dado que en 2 casos el procedimiento propuesto arrojó una solución óptima, una desviación promedio de 3,19% y una máxima de 7,39%.

~ 84 ~

Teniendo en cuenta que estos resultados no se consideran sustanciales en situaciones reales de manufactura, se decide concluir que en la práctica no existe diferencia entre las muestras. Esta practicidad se sustenta además en el tiempo de corrida requerido por las herramientas para derivar una solución, cuyos estadísticos descriptivos se presentan en la Tabla 3.5 y el Gráfico 3.5, que muestra la diferencia entre medias, involucrando además los resultados de la herramienta heurística.



media

Par 1 MIP_TC 1143,987143 60 557,3109195 71,9485303

Proc_TC 188,935147 60 7,6714052 ,9903742

Tabla 3.5. Estadísticos Tiempo de Corrida Instancia de 7 órdenes y 5 estaciones


En este caso, la media de las diferencias del tiempo de corrida obtenida por el modelo de programación entera mixta y el procedimiento propuesto alcanza 955,052 segundos de CPU, siendo el valor máximo de 1794,77 segundos a favor del procedimiento propuesto, lo que se considera una cifra importante. De otro lado, la heurística toma en promedio 0,91 segundos de CPU para derivar una solución, lo que se compensa con los resultados inferiores en términos del valor de la función objetivo que arroja.

~ 85 ~

Con el objetivo de verificar si esta diferencia es estadísticamente significativa, se verifica en primera instancia la normalidad de las observaciones a través de una prueba de Kolmogorov-Smirnov, para la que se formula la siguiente prueba de hipótesis y cuyos resultados se presentan en la Tabla 3.6.

𝐻0: los datos se distribuyen normalmente 𝐻𝑎: no se puede asumir normalidad de los datos




MIP_TC ,117 60 ,041 ,939 60 ,005

Proc_TC ,099 60 ,200* ,945 60 ,009



Tabla 3.6. Prueba de normalidad Tiempo de Corrida Instancia de 7 órdenes y 5

estaciones

Una vez más, a pesar que el p-valor del enfoque exacto es inferior a un nivel de significancia del 5%, se decide disminuir el nivel de la prueba a 1% y de esta manera aceptar la hipótesis nula y concluir que los datos se distribuyen normalmente. Al comprobarse este supuesto, se realiza una prueba t para muestras pareadas para la que se formula la siguiente prueba de hipótesis

𝐻0: 𝜇𝑑 = 0

𝐻𝑎: 𝜇𝑑 ≠ 0 Y cuyos resultados se muestran a continuación.




típ.

Error típ. de

la media


para la diferencia

Inferior Superior

Par 1 MIP_TC -

Proc_TC

955,0519965 556,1747733 71,8018545 811,3768175 1098,7271755 13,301 59 ,000

Tabla 3.7. Prueba t muestras pareadas. Tiempo de corrida Instancia de 7 órdenes y 5

estaciones

~ 86 ~

Sustentando las conclusiones previas, el p-valor de 0 permite rechazar la hipótesis nula y concluir que existe diferencia entre el tiempo de corrida de las muestras. Agregando una vez más métricas de desempeño asociadas con las desviaciones mínima, máxima y promedio, se observa una divergencia mínima del enfoque exacto frente al procedimiento de 10,57%, valor que en promedio alcanzó 75,46% y como máximo 90,96%. En este caso, siendo una diferencia considerable y teniendo en cuenta que el tiempo de corrida del algoritmo corresponde en situaciones reales al tiempo de respuesta al cliente sobre si se acepta o no una orden, se decide mantener esta conclusión. 3.1.2 Instancia de 8 órdenes × 7 estaciones Los resultados correspondientes en esta instancia a los valores de la función objetivo alcanzados con las tres herramientas diseñadas, así como el tiempo que tarda cada una en derivar una solución se muestran en la Tabla 3.8 y los Gráficos 3.6 y 3.7.

Problema GAMS PROCEDIMIENTO

Z* - z T* - t HEURÍSTICA

Z t Z t Z t

1 5088,516 378,277 4995,298 295,566 93,218 82,711 973,420 1,242

2 5129,634 979,086 5015,429 355,691 114,205 623,394 503,768 1,262

3 5055,455 688,413 4968,895 299,125 86,560 389,288 382,245 1,242

4 5303,976 1495,380 5213,222 316,811 90,754 1178,569 929,379 1,230

5 4797,278 1742,118 4462,230 305,379 335,047 1436,739 1340,858 1,270

6 4693,407 581,319 4376,773 401,156 316,633 180,163 534,526 1,238

7 3883,569 965,655 3855,418 395,027 28,151 570,627 1039,376 1,211

8 5487,325 200513,846 4989,805 294,203 497,520 200219,643 208,013 0,949

9 5128,325 200315,169 4688,773 266,680 439,552 200048,489 575,773 0,906

10 4430,490 1618,405 4131,322 385,328 299,168 1233,077 1087,941 1,422

11 4583,488 1109,787 4560,595 313,750 22,893 796,037 1483,023 1,223

12 4408,199 1530,458 4096,729 388,879 311,470 1141,579 448,967 1,230

13 4595,342 1679,084 4252,221 339,320 343,121 1339,764 1605,023 1,219

14 4739,787 646,636 4531,774 355,055 208,012 291,581 790,404 1,219

15 4761,067 529,729 4427,582 384,387 333,484 145,343 900,951 2,176

16 5195,218 1658,005 4802,017 406,598 393,202 1251,407 809,799 1,230

17 4167,728 401,140 4043,794 522,676 123,934 -121,535 973,454 1,258

18 4490,931 900,518 4304,208 326,391 186,723 574,128 900,538 1,234

19 5345,793 1157,162 4991,059 499,285 354,734 657,877 1709,507 1,230

20 5029,428 1886,746 4873,894 445,453 155,534 1441,293 678,735 1,270

21 3759,432 444,142 3556,883 257,234 202,548 186,907 768,131 1,664

~ 87 ~

22 4949,339 950,898 4798,772 379,305 150,566 571,594 962,654 1,219

23 5083,361 200116,478 4623,807 465,836 459,554 199650,642 1088,772 1,234

24 4966,814 520,564 4833,165 482,516 133,649 38,048 1619,930 1,242

25 5363,856 660,842 5174,087 314,758 189,769 346,085 398,632 1,266

26 4409,869 1860,803 4222,330 293,949 187,539 1566,853 618,100 1,254

27 4754,018 1681,722 4421,650 278,430 332,368 1403,292 1231,886 1,242

28 4391,767 1079,335 4180,002 349,301 211,765 730,035 229,864 1,270

29 4418,296 2604,805 4274,853 356,594 143,443 2248,211 1450,447 1,238

30 5687,792 2062,340 5386,018 393,547 301,774 1668,793 1619,206 1,996

31 5680,752 755,601 5626,967 388,930 53,785 366,672 112,428 2,004

32 4484,950 602,847 4284,066 306,555 200,884 296,292 1069,945 1,391

33 4254,870 321,895 4254,870 291,008 0,000 30,888 391,347 1,965

34 4760,834 200420,882 4419,383 414,016 341,451 200006,866 227,859 1,984

35 4311,318 335,256 4166,417 290,613 144,901 44,642 1590,205 1,234

36 4703,798 1477,987 4636,853 350,270 66,945 1127,718 256,967 1,258

37 4837,176 229,847 4465,628 308,266 371,549 -78,418 1767,099 1,961

38 4841,318 318,340 4638,743 322,043 202,575 -3,703 793,176 1,277

39 5138,431 2081,237 4852,801 432,332 285,630 1648,905 549,944 1,242

40 5487,325 200574,539 4987,049 255,262 500,276 200319,277 762,983 1,012

41 4924,884 200436,710 5003,096 485,613 -78,212 199951,097 1462,840 1,258

42 4936,609 501,183 4815,314 372,320 121,294 128,862 630,647 1,262

43 4843,540 596,826 4667,067 322,016 176,473 274,811 1256,896 1,256

44 3960,668 586,364 3769,442 310,789 191,226 275,575 764,400 1,262

45 5557,290 793,213 5423,399 389,777 133,892 403,435 1103,060 1,266

46 4254,252 1100,142 4043,886 372,992 210,366 727,150 1004,050 1,258

47 5212,700 926,209 5003,295 293,801 209,405 632,408 252,875 1,273

48 4961,934 1826,370 4818,900 329,484 143,033 1496,886 708,546 1,301

49 4222,365 1480,388 3944,898 320,637 277,468 1159,752 1150,108 1,254

50 4991,042 186683,702 4804,017 396,172 187,025 186287,530 804,832 1,273

51 4757,661 741,019 4714,975 321,156 42,686 419,863 1594,850 1,219

52 5113,413 1524,774 5091,612 284,133 21,802 1240,641 830,988 1,242

53 4058,803 1744,285 3996,286 275,820 62,517 1468,465 1141,176 1,252

54 5204,996 200840,270 4719,489 409,930 485,507 200430,341 328,461 1,257

55 4578,410 602,855 4307,420 289,047 270,989 313,808 1554,720 1,242

56 4406,411 1245,370 4051,411 294,008 354,999 951,362 1273,727 1,227

57 4708,623 430,704 4489,208 317,320 219,415 113,384 528,572 1,289

58 4486,893 894,208 4175,348 297,539 311,545 596,669 1070,815 1,266

59 4953,097 1083,296 4650,167 395,211 302,930 688,086 851,699 1,234

60 5045,019 1495,565 4843,500 366,961 201,519 1128,604 1504,435 1,242


~ 88 ~


Gráfico 3.7. Resultados Tiempo de Corrida Instancia de 8 órdenes y 7 estaciones

Tomando inicialmente los valores de la función objetivo obtenidos con las herramientas diseñadas, se calcularon de forma preliminar los estadísticos

~ 89 ~

descriptivos para las dos muestras, con los que se construye la Tabla 3.9 y el Gráfico 3.8, que involucra además los resultados de la heurística.



media

Par 1 MIP_FO 4796,314683 60 441,7118621 57,0247562

Proc_FO 4578,635254 60 432,8419547 55,8796561

Tabla 3.9. Estadísticos valores Función Objetivo Instancia de 8 órdenes y 7 estaciones

Gráfico 3.8. Media de valores Función Objetivo Instancia de 8 órdenes y 7 estaciones

Como se observa, la media de las diferencias del valor de la función objetivo obtenida por el modelo de programación entera mixta y el procedimiento propuesto alcanza 217,68 unidades monetarias, lo que se considera un buen

resultado. Así mismo, se encuentra 1 caso para el que el procedimiento propuesto arroja una solución óptima y otro para el que la diferencia se encuentra a favor del mismo. De otra parte, las diferencias de la heurística respecto al método exacto y el procedimiento son en promedio de 3876,26 y 3658,586 unidades respectivamente, por lo que en este caso también se observan mejoras sustanciales al involucrar un algoritmo genético.

~ 90 ~

Con el objetivo de determinar si la diferencia entre las herramientas bajo análisis es estadísticamente significativa, se efectúa en primera instancia una prueba de Kolmogorov-Smirnov para la que se formula la siguiente prueba de hipótesis:


Los resultados se presentan en la Tabla 3.10.




GAMS_FO ,065 60 ,200* ,989 60 ,870

Proc_FO ,078 60 ,200* ,991 60 ,932



Tabla 3.10. Prueba de normalidad valores Función Objetivo Instancia de 8 órdenes y 7

estaciones

Como se observa, con un nivel de significancia de 1% o 5%, es posible en ambos casos aceptar la hipótesis nula y concluir que las muestras se distribuyen normalmente. Una vez comprobado este supuesto, se realiza con ayuda del software estadístico SPSS una prueba t para muestras pareadas para la que se formula la siguiente prueba de hipótesis y cuyos resultados se muestran en la Tabla 3.11.

𝐻0: 𝜇𝑑 = 0

𝐻𝑎: 𝜇𝑑 ≠ 0




típ.

Error típ. de

la media


para la diferencia

Inferior Superior

Par 1 MIP_FO -

Proc_FO

217,6794289 132,4896450 17,1043396 183,4537244 251,9051335 12,727 59 ,000

Tabla 3.11. Prueba t muestras pareadas. Valores Función Objetivo Instancia de 8 órdenes

y 7 estaciones

~ 91 ~

En este caso, también se calcula un p-valor de 0 que permite rechazar a cualquier nivel de significancia la hipótesis nula y concluir que existe diferencia entre las medias. Atendiendo una vez más a la practicidad de este resultado y considerando que en situaciones reales de manufactura una diferencia media de 217,68 unidades monetarias puede no ser representativa cuando las utilidades alcanzan como mínimo 3759,43 unidades monetarias y realizando un análisis detallado de los datos obtenidos, donde es posible observar que para los 5 casos donde la diferencia en términos del valor de la función objetivo es mayor de 400 unidades, la penalización en tiempo de corrida es bastante amplia, por cuanto el tiempo de convergencia de GAMS es superior al límite de 200.000 segundos de CPU, en contraste con un máximo de aproximadamente 466 segundos que toma en estos casos el procedimiento propuesto compensando esta diferencia, se decide aceptar que en la práctica no existe diferencia entre las muestras, conclusión que se sustenta además en la prueba realizada a los 52 casos que se presentan en el Gráfico 3.9, en los que el tiempo de corrida de GAMS fue inferior a los 200.000 segundos de CPU establecidos, cuya normalidad es invariante y la media de las diferencias alcanza 196,694 unidades, lo cual se considera un buen resultado.

Gráfico 3.9. Valores Ajustados Función Objetivo Instancia 8 órdenes y 7 estaciones

Con el fin de soportar estos hallazgos, para este caso se agregan tres métricas de desempeño asociadas a la desviación mínima, máxima y promedio de las observaciones originales, encontrándose para la primera medida una divergencia del procedimiento respecto al enfoque exacto de 0%, dado que en uno de los problemas considerados el algoritmo encontró la solución óptima, así como un valor de 4,419% en promedio y máximo de 9,33%, por lo que es posible ratificar esta conclusión.

~ 92 ~

Dicha practicidad, se sustenta así mismo en el tiempo de corrida requerido por las herramientas para derivar una solución, cuyos estadísticos descriptivos se presentan en la Tabla 3.12 y el Gráfico 3.10, que muestra adicionalmente la diferencia entre medias, involucrando además los resultados de la herramienta heurística.



media

Par 1 MIP_TC 27423,51246 60 67784,90092 8750,993079

Proc_TC 351,204136 60 63,1778346 8,1562234

Tabla 3.12. Estadísticos Tiempo de Corrida Instancia de 8 órdenes y 7 estaciones


Como se observa, la media de las diferencias del tiempo de corrida obtenidas por el modelo de programación entera mixta y el procedimiento propuesto alcanza 27072,308 segundos de CPU, lo que se considera una cifra

significativamente alta, aumentada por los 5 casos remarcados anteriormente y 2 más señalados en la Tabla 3.8. De otro lado, la heurística toma en promedio 1,32 segundos de CPU para encontrar una solución, lo que se compensa con los resultados inferiores en términos del valor de la función objetivo que arroja. Con el objetivo de determinar si esta diferencia es estadísticamente significativa, se verifica inicialmente la normalidad de las observaciones a

~ 93 ~

través de una prueba de Kolmogorov-Smirnov para la que se establece la siguiente prueba de hipótesis y cuyos resultados se muestran en la Tabla 3.13.





MIP_TC ,510 60 ,000 ,411 60 ,000

Proc_TC ,144 60 ,003 ,937 60 ,004



Tabla 3.13. Prueba de normalidad Tiempos de Corrida Instancia de 8 órdenes y 7

estaciones

Al obtenerse un p-valor de 0 en ambas muestras, debe rechazarse a cualquier nivel de significancia la hipótesis nula y concluir que los datos no se distribuyen normalmente. Es de anotar, que tal como se muestra en la Tabla 3.14, la eliminación de los 8 puntos extremos correspondientes a los casos donde el enfoque exacto se acercó o alcanzó los 200.000 segundos de CPU aumentó la significancia de las observaciones asociadas al modelo de programación entera mixta, pero no modificó los resultados del procedimiento.




MIP_TC ,111 52 ,149 ,942 52 ,014

Proc_TC ,151 52 ,005 ,916 52 ,001



Tabla 3.14. Prueba de normalidad Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7 estaciones

Al no poder asumir la normalidad de ambas muestras, se realizó con ayuda del software estadístico SPSS, la prueba no paramétrica para muestras relacionadas de Wilcoxon, que se presenta como alternativa a la prueba t de muestras pareadas cuando el supuesto de normalidad no es asumible [2]. Los resultados se muestran en la Tabla 3.15.

~ 94 ~

Rangos

N Rango

promedio

Suma de

rangos

Proc_TC - MIP_TC

Rangos negativos 57a 31,86 1816,00

Rangos positivos 3b 4,67 14,00

Empates 0c

Total 60

a. Proc_Tiempo < MIP_Tiempo

b. Proc_Tiempo > MIP_Tiempo

c. Proc_Tiempo = MIP_Tiempo

Estadísticos de contrastea

Proc_TC - MIP_TC

Z -6,633b

Sig. asintót. (bilateral) ,000

a. Prueba de los rangos con signo de

Wilcoxon

b. Basado en los rangos positivos.

Tabla 3.15. Prueba de Wilcoxon Tiempos de Corrida Instancia de 8 órdenes y 7

estaciones

En este punto, se decidió realizar la prueba eliminando los puntos extremos señalados anteriormente. Como se puede observar, los resultados son similares.

Rangos

N Rango

promedio

Suma de

rangos

Proc_TC- MIP_TC

Rangos negativos 49a 27,84 1364,00

Rangos positivos 3b 4,67 14,00

Empates 0c

Total 52

a. Proc_Tiempo < MIP_Tiempo

b. Proc_Tiempo > MIP_Tiempo

c. Proc_Tiempo = MIP_Tiempo

~ 95 ~

Estadísticos de contrastea

Proc_TC - MIP_TC

Z -6,147b

Sig. asintót. (bilateral) ,000

a. Prueba de los rangos con signo de

Wilcoxon

b. Basado en los rangos positivos.

Tabla 3.16. Prueba de Wilcoxon Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7

estaciones

Es de aclarar que al eliminar estos puntos y tal como se muestra en los estadísticos descriptivos presentados en la Tabla 3.17 y los Gráficos 3.11 y 3.12, la media de las diferencias entre una herramienta y otra alcanza 719,704 segundos de CPU, que se considera un valor alto sin ser excesivo, siendo el valor máximo de 2248,2113 segundos a favor del procedimiento propuesto.



media

Par 1 MIP_TC 1067,483686 52 572,5539790 79,3989511

Proc_TC 347,779562 52 58,5217008 8,1154997

Tabla 3.17. Estadísticos Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7

estaciones

Gráfico 3.11. Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7 estaciones

~ 96 ~

Gráfico 3.12. Media de Tiempos de Corrida Ajustados Instancia de 8 órdenes y 7 estaciones

Sustentando las conclusiones previas, el p-valor de 0 arrojado por la prueba de Wilcoxon para los datos originales y ajustados, permite rechazar la hipótesis nula y concluir que existe diferencia entre el tiempo de corrida de las muestras. Así mismo, el cálculo en los datos originales de una desviación mínima de 0%, correspondiente a 3 casos en los que el enfoque exacto tardó un tiempo ligeramente inferior al algoritmo, un valor promedio de 62,151% y un máximo de 99,87% permitieron evidenciar la practicidad de la herramienta propuesta. Considerando la presencia de instancias para las que el enfoque exacto no brinda una solución óptima en el tiempo límite establecido y teniendo en cuenta una vez más, que el tiempo de corrida del algoritmo corresponde en situaciones reales al tiempo de respuesta al cliente sobre si se acepta o no una orden, se decide mantener la conclusión estadística. 3.2 VERIFICACIÓN DEL DESEMPEÑO DEL PROCEDIMIENTO

PROPUESTO Como último paso del estudio, se decide verificar el tiempo de corrida del procedimiento propuesto en 20 problemas completamente aleatorios considerando dos instancias de mayor tamaño definidas como 20 y 30 órdenes × 10 estaciones, esta última correspondiente a la máxima parametrización definida para el escenario. Esto con el objetivo de estimar si en estas instancias el algoritmo tarda un tiempo superior a los 200.000 segundos de CPU definidos como límite.

~ 97 ~

Los resultados obtenidos en el primer tamaño considerado se muestran en la Tabla 3.18.

Problema PROCEDIMIENTO HEURÍSTICA

Z t Z t

1 6609,95061 3133,00239 4346,50405 3,18359375

2 6702,4833 4189,74972 665,204256 3,18359375

3 7790,82497 3694,6408 577,744263 3,171875

4 8380,13695 4000,54009 4449,90307 3,171875

5 9662,65226 4327,32284 2959,47996 3,28125

6 8614,27607 4498,15291 3730,53358 3,19140625

7 8556,86011 4900,03295 3315,70169 3,17578125

8 5658,65933 4690,56373 1501,6267 3,17578125

9 8465,87445 3494,42112 376,007128 3,16796875

10 8913,99942 3669,10243 3383,50255 3,22265625

11 8690,08485 3985,46234 3923,7831 3,2109375

12 7816,65549 3156,82565 662,594929 3,265625

13 7189,04822 4667,62454 264,477408 3,40234375

14 6595,6491 4109,29793 903,551099 3,19921875

15 8878,82882 4954,53543 1222,47167 3,19921875

16 11448,1033 3009,37706 1377,1195 3,2578125

17 7611,08533 4473,99059 3260,48887 3,203125

18 8117,67782 3842,91821 1297,87317 3,23828125

19 7736,01597 4589,61711 6788,96126 3,2109375

20 9161,2463 3129,77658 4135,11164 3,19921875


El Gráfico 3.13 muestra la relación entre la media del valor de la función objetivo y el tiempo de corrida requerido por ambas herramientas. Es posible notar, que la diferencia promedio en términos de tiempo computacional alcanza 2453,917 segundos de CPU a favor de la heurística, que se compensa con una divergencia media en términos del valor de la función objetivo de 4104,158

unidades monetarias, lo que contribuye a concluir que en todos los casos analizados siempre es mejor involucrar un algoritmo genético en la resolución del problema.

~ 98 ~

Gráfico 3.13. Desempeño Procedimiento Vs. Heurística Instancia 20 órdenes y 10 estaciones

Como se puede apreciar, el tiempo que tarda el algoritmo alcanza en promedio 2457,132 segundos de CPU, inferior al límite establecido, cota que tampoco es superada si se realiza un análisis individual de cada uno de los 20 problemas considerados, lo que justifica el análisis de una instancia mayor. Para el segundo caso, correspondiente a 30 órdenes y 10 estaciones, los resultados alcanzados se resumen en la Tabla 3.19.

Problema PROCEDIMIENTO HEURÍSTICA

Z t Z t

1 11915,4699 4069,51918 4390,9501 3,3046875

2 10927,9432 4221,83426 2966,66068 3,28125

3 11706,1069 4409,31308 3902,54283 3,3359375

4 9903,47683 4059,22592 3307,97856 3,5078125

5 9388,77589 4581,54212 6320,25151 3,30859375

6 8705,2385 4358,78452 1280,14171 3,390625

7 10838,6617 3898,79095 4934,56124 3,26171875

8 12291,6207 4760,14813 5106,5142 3,2890625

9 10522,6935 3993,07134 1107,43888 3,30078125

10 11326,7841 4148,46639 4611,21415 3,265625

11 10864,301 3822,19269 3187,54281 3,2890625

12 8992,6267 4322,7886 4151,17058 3,3046875

~ 99 ~

13 9579,97152 3850,85024 4007,97352 3,2734375

14 11743,0582 4874,4269 8026,29163 3,28125

15 14017,8409 4871,14169 7104,05396 3,296875

16 10352,52 4900,30091 4971,34711 3,30859375

17 12027,274 4884,52922 6975,94456 3,29296875

18 11916,1297 4208,77204 4898,27599 3,24609375

19 8605,98855 4871,62492 4051,27699 3,2578125

20 10780,3105 4783,60379 5705,51613 3,2578125


El Gráfico 3.14 muestra la relación entre la media del valor de la función objetivo y el tiempo de corrida requerido por ambas herramientas. Es posible notar, que la diferencia promedio en términos de tiempo computacional es de 4547,08 segundos a favor de la heurística, que se compensa con una divergencia media en términos del valor de la función objetivo de 6425,793 unidades monetarias, mejorando notoriamente las utilidades obtenidas y contribuyendo a concluir que en todos los tamaños de problema considerados y todos los problemas aleatoriamente generados siempre es mejor involucrar un algoritmo genético en la resolución del problema.

Gráfico 3.14. Desempeño Procedimiento Vs. Heurística Instancia 30 órdenes y 10 estaciones

Así mismo, es posible observar que el tiempo que tarda el algoritmo alcanza en promedio 4550,382 segundos de CPU, que a pesar de ser una cifra

considerable, sigue siendo inferior al límite establecido, cota que tampoco es

~ 100 ~

superada si se realiza un análisis individual de cada uno de los 20 problemas considerados, concluyéndose entonces que es posible resolver problemas de hasta 30 órdenes y 10 estaciones en tiempos computacionalmente razonables. 3.3 CONCLUSIONES PARCIALES

En este capítulo, se presenta el análisis estadístico que permite verificar si el procedimiento propuesto brinda soluciones de calidad en tiempos computacionales razonables, a través de un diseño de experimentos de muestras pareadas que permite comparar su desempeño frente al modelo de programación entera mixta formulado. En primer lugar, se generaron 60 problemas aleatorios en instancias de 7 órdenes y 5 estaciones y 8 órdenes y 7 estaciones, esta última considerada problemática para el enfoque exacto. Los resultados computacionales que pueden observarse en detalle en los numerales 3.1.1 y 3.1.2, permitieron identificar una media de las diferencias respecto al valor de la función objetivo de 130,109 y 217,68 unidades monetarias en cada tamaño de problema y en torno al tiempo de convergencia requerido, una media de las diferencias de 955,052 y 27072,308 segundos de CPU, respectivamente. Adicionalmente, se agregaron tres medidas de desempeño asociadas a las desviaciones mínima, promedio y máxima de los resultados arrojados por el procedimiento propuesto respecto a las soluciones del modelo de programación entera mixta, observándose para la primera instancia porcentajes de 0%, 3,19% y 7,39% en relación con el valor de la función objetivo y de 10,57%, 75,46% y 90,96% en torno al tiempo de convergencia de las herramientas. Para la segunda instancia, estos cálculos alcanzaron un porcentaje de desviación en las utilidades de 0%, 4,42% y 9,33% y de 0%, 62,15% y 99,87% en los segundos de CPU requeridos por ambos enfoques. La diferencia notable en los segundos de CPU requeridos por ambos enfoques para derivar una solución, permitió involucrar consideraciones prácticas en torno a su implementación, por lo que teniendo en cuenta que en situaciones reales de manufactura un valor ligeramente inferior de utilidades no representa mayores problemas, pero un tiempo de respuesta al cliente sustancialmente mayor puede ocasionar el retiro de la orden y hasta la pérdida del mismo, fue posible demostrar la aplicabilidad del procedimiento propuesto. Por último, el procedimiento fue puesto a prueba en 20 problemas elegidos al azar en dos instancias de mayor tamaño, correspondientes a 20 y 30 órdenes y 10 estaciones, corroborándose que el tiempo de convergencia alcanza en promedio 2457,132 segundos de CPU en el primer caso y 4550,382 segundos en el segundo, cifras sustancialmente menores al límite establecido para el modelo de 200.000 segundos de CPU, por lo que representa una muy buena alternativa en problemas de mayor tamaño.

~ 101 ~

En todos los casos estudiados, fue posible observar que los resultados de la heurística son mucho mejores en términos de tiempo computacional, pero radicalmente inferiores en torno al valor de la función objetivo, por lo que es justificable el uso de algoritmos genéticos con el objetivo de encontrar soluciones cercanas al óptimo. 3.4 BIBLIOGRAFÍA

[1] D. Montgomery, Design and Analysis of Experiments, 8th ed., John Wiley & Sons, Inc., 2013.

[2] R. Walpole, R. Myers, S. Myers y K. Ye, Probability & Statistics for Engineers & Scientists, 9th ed., Prentice Hall, 2012.

~ 102 ~

CAPÍTULO 4

CONCLUSIONES Y RECOMENDACIONES

En este capítulo, se presentarán los resultados finales del recorrido teórico y experimental realizado por el autor en torno al problema de Aceptación de Órdenes y Scheduling en escenarios Flexible Flow Shop con máquinas no relacionadas y al diseño de las herramientas de ingeniería propuestas para su resolución. Se espera que los hallazgos y aportes de este proyecto, sean sustento de futuras investigaciones en este campo. 4.1 CONCLUSIONES Con base en los alcances de este proyecto de investigación y los objetivos formulados para su desarrollo, fue posible en primera instancia contextualizar el objeto de estudio dentro de un campo general como es el problema de Scheduling, evidenciar la evolución de los sistemas productivos y de las herramientas empleadas para su solución y demostrar su importancia como soporte a la toma de decisiones en firmas reales y su papel en el aumento de la eficiencia de las compañías a través de la utilización adecuada de los recursos. Del mismo modo, se identificó el problema de Aceptación de Órdenes y Scheduling (OAS) o Scheduling admitiendo rechazos, como un escenario que ha atraído interés desde el punto de vista académico y empresarial, en tanto permite emplear lo mejor posible la limitada capacidad de producción disponible, distinguiendo aquellas órdenes que impactan positivamente las utilidades y las que no lo hacen y pueden no aceptarse, sin desconocer las implicaciones que tiene en el mercado el rechazarlas. Con el fin de ajustar este escenario a un entorno de manufactura real, se decidió trabajar un problema Flexible Flow Shop estático determinístico con máquinas no relacionadas ubicadas en paralelo y considerando la maximización de las utilidades totales del ejercicio, que involucran tres criterios a saber: la ganancia recibida por las órdenes aceptadas, los costos asociados al tiempo ocioso de los recursos y la penalización por las órdenes rechazadas, relacionada con la pérdida de imagen frente al cliente o la tercerización de las actividades asociadas a su fabricación. Tomando en consideración los parámetros y condiciones de flujo elegidos, el problema bajo estudio puede notarse como:

𝑶𝑨𝑺𝑹𝒎𝑭𝑭𝒄|𝒄𝒉𝒂𝒊𝒏𝒔, 𝒔𝒋𝒍𝒕 , 𝑹𝑫𝒋, 𝒑𝒔𝒋

𝒕, 𝒗𝒊𝒋𝒕 , 𝑫𝑫𝒋, 𝑫𝑳𝒋| 𝑼𝒕𝒊𝒍𝒊𝒅𝒂𝒅.

En este contexto, las investigaciones previas revisadas por el autor así como la taxonomía del problema presentada por otros autores, justificaron la elección de las características mencionadas, debido a que de acuerdo con su conocimiento y hasta el momento en que este documento se escribió, las

~ 103 ~

investigaciones previas empleando algoritmos genéticos, se concentraron en escenarios de una sola máquina y métricas en la función objetivo que no contemplan el costo del tiempo ocioso de los recursos productivos, significando un aporte en el ámbito académico y científico que abre puertas a numerosas investigaciones en este campo. Una vez contextualizado y definido el problema a estudiar, el diseño de las herramientas de ingeniería requeridas para su solución se concentra en primer lugar en el desarrollo del modelo de programación entera mixta (MIP) que caracteriza formalmente el escenario de interés, involucrando los parámetros, variables y relaciones correspondientes y que brinda, según los experimentos computacionales realizados, soluciones en instancias de hasta 8 órdenes y 5 estaciones en un tiempo de 200.000 segundos de CPU, establecidos como límite. Debido al carácter combinatorio del problema bajo estudio y con el fin de obtener una solución inicial que oriente la búsqueda del algoritmo genético y agilice su convergencia en el óptimo, se diseña una heurística constructiva que se considera una modificación de la herramienta Dynamic Release First-Sequence Best (d-RFSB), que evalúa la conveniencia de las órdenes que arriban al sistema y las programa en todas las celdas de manufactura eligiendo dentro de ellas la máquina en la que dicha orden alcanza la mayor relación entre la máxima ganancia recibida por ella, 𝑢𝑗 y el tiempo que tarda en

completar su fabricación. Con el objetivo de mejorar los resultados obtenidos a través de esta heurística y hallar una solución más cercana al óptimo, sin penalizar excesivamente el tiempo computacional requerido para derivarlas, se diseña finalmente el procedimiento propuesto resultado de la investigación, que involucra un algoritmo genético para aprovechar los beneficios de la recombinación de una población de soluciones y mantiene el mismo criterio de elección de las máquinas de la heurística. Este algoritmo, aplica como enfoque de codificación de los cromosomas un código basado en permutación o código de trabajos usando números enteros, siendo el primer individuo la secuencia obtenida a través de la aproximación heurística. Para crear una nueva generación, se emplea un cruce en dos puntos o two-point crossover y para mantener la diversidad de la población se utiliza una eliminación de clones y un operador de mutación en el cual se eligen dos posiciones aleatorias en la secuencia y se intercambian las órdenes que hay en ellas, lo que se conoce en la literatura como Pairwise Interchange. Como criterio de parada y tomando en cuenta que la herramienta no requiere gran número de generaciones para brindar una buena solución, el algoritmo se

detiene al completar 70 generaciones. A través de un experimento 23 con puntos centrales, se escogió un tamaño de población de 200 individuos y tasas de cruce y mutación de 0.5 y 0.3, respectivamente.

~ 104 ~

La verificación del procedimiento propuesto se realizó a través de un diseño de experimentos de muestras pareadas en tamaños de problema de 7 órdenes y 5 estaciones y 8 órdenes y 7 estaciones, esta última en la que el software de programación matemática GAMS supera el límite establecido de 200.000 segundos de CPU, involucrada de manera que pudiera compararse el desempeño del procedimiento propuesto en una instancia problemática para el enfoque exacto. Para el primer caso, se observa para los valores de la función objetivo una media de las diferencias entre el modelo de programación entera mixta y el procedimiento propuesto de 130,109 unidades monetarias, encontrándose 2 observaciones en los que esta última herramienta arroja una solución óptima, lo cual se considera un buen resultado, teniendo en cuenta que el valor mínimo de la función objetivo alcanza 3304,371 unidades monetarias. De otra parte, las diferencias de la heurística respecto al método exacto y el procedimiento son en promedio de 3038,73 y 2908,625 unidades monetarias, respectivamente, notándose en todos los casos resultados inferiores frente al procedimiento. En torno al tiempo de convergencia de las herramientas, la media de las diferencias alcanza 955,052 segundos de CPU, lo que se considera una cifra importante. De otro lado, la heurística toma en promedio 0,91 segundos de CPU para derivar una solución, lo que se compensa con los resultados inferiores en términos del valor de la función objetivo. Adicionalmente, se agregaron tres medidas de desempeño asociadas a las desviaciones mínima, máxima y promedio de los resultados arrojados por el procedimiento propuesto respecto a las soluciones del modelo de programación entera mixta, observándose porcentajes de 0%, 3,19% y 7,39% en relación con el valor de la función objetivo y de 10,57%, 75,46% y 90,96% en torno al tiempo de corrida de ambas herramientas. Respecto a la segunda instancia considerada, la media de las diferencias del valor de la función objetivo obtenida por el modelo de programación entera mixta y el procedimiento propuesto alcanza 217,68 unidades monetarias, lo que se considera un buen ajuste considerando un valor mínimo de función objetivo de 3759,432 unidades monetarias. Así mismo, se encuentra 1 caso para el que el procedimiento propuesto arroja una solución óptima y otro para el que la diferencia se encuentra a favor del mismo. Por su parte, las diferencias de la heurística respecto al método exacto y el procedimiento son en promedio de 3876,26 y 3658,586 unidades monetarias respectivamente, por lo que en este caso también se observan mejoras sustanciales al involucrar un algoritmo genético. Con relación al tiempo requerido por las herramientas para derivar una solución, se observa una media de las diferencias de 27072,308 segundos de CPU a favor del procedimiento, lo que se considera una cifra significativamente alta, aumentada por 8 casos en los que GAMS superó el tiempo de corrida límite. Eliminando estos puntos extremos, se alcanza una media de las

~ 105 ~

diferencias de 719,704 segundos de CPU, que se considera un valor alto sin ser excesivo, siendo el valor máximo de 2248,2113 segundos a favor del procedimiento propuesto. De otro lado, la heurística toma en promedio 1,32 segundos de CPU para encontrar una solución, lo que se compensa con los resultados inferiores en términos del valor de la función objetivo. Adicionalmente y tomando en consideración las desviaciones mínima, promedio y máxima de los resultados originales, se calcularon porcentajes de divergencia en las utilidades de 0%, 4,42% y 9,33% y de 0%, 62,15% y 99,87% en los segundos de CPU requeridos por el enfoque exacto y el algoritmo. La diferencia notable en los segundos de CPU requeridos por ambos enfoques para derivar una solución, evidenció que aunque las mejores respuestas se alcanzan con una búsqueda exhaustiva, su uso incrementa en gran medida el tiempo computacional. Esto permitió involucrar consideraciones prácticas en torno a su implementación, por lo que teniendo en cuenta que en situaciones reales de manufactura un valor ligeramente inferior de utilidades puede no representar mayores problemas, pero un tiempo de respuesta al cliente sustancialmente mayor puede ocasionar el retiro de la orden y hasta la pérdida del mismo, fue posible demostrar la aplicabilidad del procedimiento propuesto. Adicionalmente, se verificó el desempeño del algoritmo en dos tamaños de problema de mayor tamaño, correspondientes a 20 y 30 órdenes y 10 estaciones, de manera que fuera posible observar si el procedimiento propuesto, ejecutado en el software Visual Basic para Excel, también superaba el tiempo límite de convergencia fijado. Para el primer tamaño considerado, el tiempo que tarda el algoritmo alcanza en promedio 2457,132 segundos de CPU, inferior al límite establecido, cota que tampoco es superada si se realiza un análisis individual de cada uno de los problemas considerados, lo que justifica el análisis de una instancia mayor. En este caso, la heurística toma en promedio 3,22 segundos para llegar a una solución, que se compensa con una divergencia media en términos del valor de la función objetivo de 4104,158 unidades monetarias. Finalmente, el tiempo de corrida en la instancia de 30 órdenes y 10 estaciones fue en promedio de 4550,382 segundos de CPU, que a pesar de ser una cifra considerable, sigue siendo inferior al límite establecido. Fue posible observar que la heurística toma en promedio 3,303 segundos para arrojar una respuesta, compensados con una divergencia media en términos del valor de la función objetivo de 6425,793 unidades monetarias. Estos hallazgos se presentan como la mayor ventaja del procedimiento propuesto, permitiendo resolver problemas de hasta 30 órdenes y 10 estaciones en tiempos computacionales razonables.

~ 106 ~

En todos los casos estudiados, fue posible observar que los resultados de la heurística son mucho mejores en términos de tiempo computacional, por lo que representa una buena alternativa para solucionar problemas de gran tamaño. Sin embargo, dichas respuestas son radicalmente inferiores en torno al valor de la función objetivo, por lo que es justificable el uso de algoritmos genéticos con el propósito de encontrar soluciones cercanas al óptimo. En torno al desarrollo del proyecto, las mayores dificultades que se encontraron se relacionan con la programación del algoritmo genético, ya que los contenidos programáticos en ingeniería industrial no involucran la elaboración de este tipo de herramientas. Sin embargo, se han convertido en una herramienta útil para resolver problemas de optimización en áreas como distribución, producción e incluso seguridad e higiene ocupacional, lo que ha motivado a investigadores de esta ciencia a involucrarse más en su diseño y aplicación. Así mismo, al no encontrarse en la literatura revisada instancias de comparación, la metodología experimental tuvo que fundamentarse en pruebas computacionales exhaustivas, para determinar el comportamiento del problema bajo estudio y ajustarse a los requerimientos de la investigación. 4.2 RECOMENDACIONES

Con base en los alcances de este proyecto, futuras investigaciones pueden enfocarse en situaciones específicas propias del escenario de Aceptación de Órdenes y Scheduling, tales como la pérdida total del cliente una vez se rechaza uno de sus pedidos o asumir una importancia relativa del mismo. También es posible modificar el entorno de manufactura por un ambiente Flexible Job Shop u Open Shop o considerar un escenario probabilístico, que además involucre paradas de máquinas o interrupciones en la ejecución de tareas. Por otra parte, es posible establecer otras funciones objetivo para el modelo de programación entera mixta, por ejemplo, la minimización del makespan o del tiempo de finalización de las órdenes o métricas asociadas al adelanto o tardanza de las mismas. Del mismo modo, puede considerarse otra heurística en la construcción del procedimiento, que guíe la búsqueda y acelere la convergencia del algoritmo, así como aplicar otro tipo de metaheurística como recocido simulado, búsqueda tabú, algoritmos voraces, colonia de hormigas y gotas de agua, en el hallazgo de soluciones al problema planteado, para las que también es posible variar el criterio de elección de las máquinas. Finalmente, el recorrido realizado por el autor permite evidenciar que en la actualidad son muchas las investigaciones que quedan por realizarse en el campo de Aceptación de Órdenes y Scheduling, por lo que considerando

~ 107 ~

problemas aún más ajustados a las situaciones reales de la industria manufacturera, será posible brindar herramientas que apoyen la efectiva toma de decisiones en esta área.

“There are two types of people who will tell you that you cannot make a difference in this world: those who are afraid to try and those who are afraid you will succeed".

- Ray Goforth

~ 108 ~

APÉNDICE A

LÍMITE SUPERIOR DEL MODELO DE PROGRAMACIÓN ENTERA MIXTA

PROPUESTO

Con el objetivo de establecer un tamaño máximo de problema de Aceptación de Órdenes y Scheduling para el que el software de programación matemática GAMS brinda una solución óptima en los 200.000 segundos de CPU fijados – que equivalen a un poco más de 55 horas reloj de corrida, que se considera un tiempo razonable de convergencia–, se llevaron a cabo una serie de pruebas computacionales siguiendo la metodología propuesta que se presenta a continuación y que fue diseñada particularmente para este caso, teniendo en cuenta que las investigaciones previas revisadas difieren notoriamente del escenario escogido.

Gráfico A.1. Metodología del experimento

Inicialmente, se definieron los criterios de interés como:

Número de órdenes Número máximo de máquinas por estación Número de estaciones

En torno a las medidas a trabajar y con base en pruebas experimentales previas, se decide iniciar el estudio estableciendo como límite inferior 5 órdenes y como cota superior momentánea una cantidad de 13. Posteriormente, se asocia a cada una un número máximo de máquinas por estación que corresponde aproximadamente a la mitad de las órdenes, esto con el fin de observar la espera en el procesamiento de algunas de ellas. Así mismo, los experimentos permitieron ubicar el límite inferior de número de estaciones en 3 y se ubicó momentáneamente una cota superior de 19.

•Identificar criterios de interés

•Identificar criterios de interés

•Especificar las medidas que se trabajarán

•Generar aleatoriamente las configuraciones de máquinas

•Especificar las medidas que se trabajarán

•Generar aleatoriamente las configuraciones de máquinas

•Ejecutar el experimento en GAMS modificando los criterios uno a uno

•Ejecutar el experimento en GAMS modificando los criterios uno a uno

•Revisar las decisiones y modificarlas de ser necesario

•Revisar las decisiones y modificarlas de ser necesario

~ 109 ~

Bajo estos niveles, el experimento piloto se definió como se muestra a continuación. Número Órdenes Máximo máquinas por

estación Número Estaciones

5 3 3

6 3 5

7 5 7

8 5 9

9 5 11

10 5 13

11 5 15

12 7 17

13 7 19

Tabla A.1. Prueba piloto diseñada

De esta forma, los experimentos computacionales en GAMS se construyeron evaluando cada número de orden en los niveles considerados de estaciones. Así, por ejemplo, para un número de 7 órdenes se tienen máximo 5 máquinas por estación y se evalúa con 3, 5, 7, 9, 11, 13, 15, 17 y 19 estaciones. Si el tiempo computacional en todos los casos es inferior a 200.000 segundos de CPU se continúa con la instancia de 8 órdenes, procedimiento que se repite hasta que se encuentre un tamaño en el que se supere este tiempo, el cual se define como límite. En todos los casos y teniendo en cuenta que el número de máquinas puede variar de una estación de trabajo a otra, se generaron al azar 7 configuraciones del problema, las cuales, debido al carácter aleatorio de los parámetros de entrada, se ejecutaron 10 veces en el software elegido y se registró el tiempo promedio necesario para derivar una solución óptima –teniendo en consideración que el valor de la función objetivo se mantiene invariante–. Una vez anotados los resultados de cada instancia, se estableció la configuración con tiempo más corto y se hallaron las diferencias respecto a este valor, de manera que pudieran observarse las circunstancias bajo las cuales aumenta el tiempo de corrida. Los resultados computacionales en torno a la instancia de 5 órdenes, mostraron que empleando un número de 11 estaciones el tiempo computacional se incrementa significativamente y toma en algunos casos más de 180.000 segundos de CPU, por lo que se decidió retirar esta instancia del análisis. Considerando que con 10 estaciones se obtienen resultados similares, se decide tomar como límite 9 estaciones. En consecuencia, el experimento se ajusta tal como se muestra en la Tabla A.2.

~ 110 ~

Número Órdenes Máximo máquinas por estación

Número Estaciones

5 3 3

6 3

7 5 5

8 5

9 5 7

10 5

11 5 9

12 7

13 7

Tabla A.2. Configuraciones consideradas en las pruebas computacionales del modelo

formulado

De esta manera, considerando una instancia de 5 órdenes, los resultados alcanzados fueron los siguientes.

Número Órdenes

Número Estaciones

ID Máquinas en cada

estación Elapsed

Time t - T*

Función Objetivo

5

3

1 1 - 1 - 1 2,10114 1,53561 2109,4708

2 1 - 1 - 2 1,09817 0,53263 2109,4708

3 1 - 3 - 3 3,96833 3,40280 2576,80808

4 1 - 2 - 3 1,95001 1,38448 2576,80808

5 2 - 2 - 3 0,56553 0,00000 2576,80808

6 2 - 3 - 3 0,71541 0,14987 2576,80808

7 3 - 3 - 3 0,72111 0,15558 2576,80808

5

1 1 - 1 - 2 - 2 - 3 61,97334 61,21118 2982,85542

2 1 - 1 - 3 - 3 - 2 55,38439 54,62223 3028,81813

3 1 - 3 - 3 - 2 - 3 24,09347 23,33131 3034,16977

4 1 - 2 - 2 - 3 - 2 3,75828 2,99612 3034,16977

5 3 - 2 - 1 - 3 - 2 2,01545 1,25329 3034,16977

6 2 - 3 - 2 - 3 - 2 0,79597 0,03381 3034,16977

7 3 - 3 - 3 - 3 - 3 0,76216 0,00000 3034,16977

7

1 1 - 1 - 1 - 2 - 2 - 3 - 3 45,01641 44,03694 4005,84197

2 1 - 1 - 1 - 3 - 3 - 3 - 2 71,78335 70,80387 4131,54776

3 1 - 1 - 3 - 3 - 3 - 2 - 2 613,76030 612,78083 4210,36622

4 1 - 2 - 2 - 3 - 2 - 3 - 1 134,42485 133,44538 4100,82586

5 3 - 2 - 1 - 3 - 2 - 3 - 2 17,19884 16,21936 4212,27421

6 3 - 3 - 3 - 3 - 2 - 2 - 2 12,70282 11,72335 4212,27421

7 3 - 3 - 3 - 3 - 3 - 3 - 3 0,97947 0,00000 4212,27421

9

1 1 - 2 - 3 - 3 - 1 - 3 - 3 - 3 - 2 3713,80517 3712,68221 3100,77944

2 2 - 2 - 2 - 2 - 3 - 3 - 3 - 2 - 3 42,66051 41,53755 3103,8958

3 1 - 1 - 2 - 3 - 2 - 3 - 3 - 3 - 2 15059,24116 15058,11821 3103,8958

~ 111 ~

4 1 - 2 - 2 - 3 - 2 - 1 - 3 - 2 - 3 121,89622 120,77326 3103,8958

5 3 - 2 - 1 - 3 - 2 - 3 - 2 - 3 - 2 48,56421 47,44126 3103,8958

6 2 - 3 - 2 - 3 - 2 - 1 - 3 - 3 - 3 18,59655 17,47359 3103,8958

7 3 - 3 - 3 - 3 - 3 - 3 - 3 - 3 - 3 1,12296 0,00000 3103,8958

Tabla A.3. Tiempo promedio de corrida para 5 órdenes

Como se observa, en el 75% de los casos, equivalente a 3 de los 4 números de estaciones considerados, los tiempos promedio más cortos se logran en la instancia con tres máquinas en todas las celdas de trabajo. Adicionalmente, es de anotar que en dichos casos se alcanza el mayor valor de la función objetivo. Dado que los tiempos de corrida fueron inferiores al tiempo límite establecido se prosiguió a evaluar un tamaño de 6 órdenes, para el que los resultados se muestran en la Tabla A.4.

Número Órdenes

Número Estaciones


estación Elapsed

Time t - T*

Función Objetivo

6

3

1 1 - 1 - 1 7,82879 6,11789 2158,53149

2 1 - 1 - 2 15,06692 13,35602 2247,24112

3 1 - 3 - 3 14,45546 12,74456 2400,52157

4 1 - 2 - 3 10,44308 8,73218 2371,3482

5 2 - 2 - 3 2,87219 1,16130 2574,18664

6 2 - 3 - 3 1,87134 0,16045 2574,18664

7 3 - 3 - 3 1,71089 0,00000 2574,18664

5

1 1 - 1 - 2 - 2 - 3 270,69477 268,01538 2858,37495

2 1 - 1 - 3 - 3 - 2 127,43052 124,75113 2892,89466

3 1 - 3 - 3 - 2 - 3 455,73614 453,05676 3041,09248

4 1 - 2 - 2 - 3 - 2 954,50503 951,82565 2951,64961

5 3 - 2 - 1 - 3 - 2 146,24202 143,56263 3204,58098

6 2 - 3 - 2 - 3 - 2 22,43844 19,75905 3204,58098

7 3 - 3 - 3 - 3 - 3 2,67938 0,00000 3204,58098

7

1 1 - 1 - 1 - 2 - 2 - 3 - 3 566,72648 522,05720 3734,02908

2 1 - 1 - 1 - 3 - 3 - 3 - 2 1655,25836 1610,58907 3734,02908

3 1 - 1 - 3 - 3 - 3 - 2 - 2 15437,88583 15393,21654 3734,02908

4 1 - 2 - 2 - 3 - 2 - 3 - 1 17036,57959 16991,91031 3759,46988

5 3 - 2 - 1 - 3 - 2 - 3 - 2 14068,55364 14023,88435 4001,70294

6 3 - 3 - 3 - 3 - 2 - 2 - 2 44,66929 0,00000 4001,70294

7 3 - 3 - 3 - 3 - 3 - 3 - 3 55,53650 10,86721 4001,70294

9 1 1 - 2 - 3 - 3 - 1 - 3 - 3 - 3 - 2 164,71419 160,50700 4240,87977

2 2 - 2 - 2 - 2 - 3 - 3 - 3 - 2 - 3 20,54358 16,33639 4240,87977

~ 112 ~

3 1 - 1 - 2 - 3 - 2 - 3 - 3 - 3 - 2 869,33424 865,12705 4240,87977

4 1 - 2 - 2 - 3 - 2 - 1 - 3 - 2 - 3 458,10258 453,89540 4240,87977

5 3 - 2 - 1 - 3 - 2 - 3 - 2 - 3 - 2 109,94239 105,73521 4240,87977

6 2 - 3 - 2 - 3 - 2 - 1 - 3 - 3 - 3 25,42073 21,21355 4240,87977

7 3 - 3 - 3 - 3 - 3 - 3 - 3 - 3 - 3 4,20719 0,00000 4240,87977


De forma similar al caso anterior, al considerar 6 órdenes, en 3 de las 4 estaciones definidas, los tiempos promedio más cortos se logran en la instancia con tres máquinas en todas las estaciones. El comportamiento contrario se presenta cuando se consideran estaciones con una sola máquina, especialmente si se trata de la última celda de trabajo. En este caso, no se supera el límite de tiempo impuesto al programa por lo que se formulan 7 nuevas instancias tomando un número máximo de 5 máquinas por estación y se evalúa un tamaño de problema de 7 órdenes. Los resultados obtenidos se muestran en la Tabla A.5.

Número Órdenes

Número Estaciones


estación Elapsed

Time t - T*

Función Objetivo

7

3

1 1 - 1 - 2 359,09317 357,87316 3898,20722

2 1 - 2 - 3 320,52664 319,30663 3898,20722

3 1 - 3 - 5 39,69960 38,47959 3863,02902

4 2 - 4 - 4 9,82994 8,60993 4048,95395

5 2 - 3 - 4 10,11160 8,89159 4048,95395

6 3 - 4 - 5 1,66480 0,44479 4052,90502

7 5 - 5 - 5 1,22001 0,00000 4052,90502

5

1 1 - 2 - 3 - 2 - 5 124,51395 123,30045 4071,29921

2 1 - 3 - 5 - 2 - 4 441,49992 440,28642 4071,29921

3 1 - 4 - 4 - 3 - 5 88,11622 86,90272 4071,29921

4 2 - 2 - 5 - 4 - 5 20,36600 19,15250 4071,29921

5 2 - 3 - 4 - 2 - 1 38,11494 36,90144 4071,29921

6 3 - 4 - 4 - 5 - 3 8,33022 7,11672 4071,29921

7 5 - 5 - 5 - 5 - 5 1,21350 0,00000 4071,29921

7

1 1 - 2 - 2 - 3 - 4 - 5 - 4 523,51238 520,55413 4074,99743

2 1 - 3 - 3 - 5 - 5 - 4 - 4 564,14427 561,18603 4074,99743

3 2 - 4 - 5 - 5 - 2 - 3 - 4 28,32368 25,36544 4074,99743

4 1 - 2 - 3 - 2 - 5 - 4 - 2 997,46559 994,50735 4074,99743

5 3 - 4 - 5 - 2 - 1 - 5 - 2 35,40132 32,44307 4074,99743

6 2 - 3 - 5 - 2 - 4 - 1 - 3 157,57672 154,61848 4074,99743

7 5 - 5 - 5 - 5 - 5 - 5 - 5 2,95824 0,00000 4074,99743

~ 113 ~

9

1 1 - 2 - 2 - 3 - 4 - 5 - 4 - 3 - 3 8,29806 6,99002 3596,05908

2 1 - 3 - 3 - 5 - 5 - 4 - 4 - 5 - 2 3,53277 2,22473 3596,05908

3 2 - 4 - 5 - 5 - 2 - 3 - 4 - 2 - 5 2,30943 1,00139 3596,05908

4 1 - 2 - 3 - 2 - 5 - 4 - 2 - 1 - 5 6,82867 5,52063 3596,05908

5 3 - 4 - 5 - 2 - 1 - 5 - 2 - 4 - 3 5,58521 4,27717 3596,05908

6 5 - 3 - 5 - 4 - 4 - 5 - 3 - 2 - 5 1,30804 0,00000 3596,05908

7 5 - 5 - 5 - 5 - 5 - 5 - 5 - 5 - 5 1,85563 0,54759 3596,05908


Para un tamaño de 7 órdenes se observa que en 3 de los 4 números de estaciones considerados se alcanzan los menores tiempos promedio en las configuraciones con 5 máquinas en todas las celdas de trabajo, instancias en las que siempre se obtienen los mayores valores de función objetivo. El caso restante, corresponde a una configuración que no contempla estaciones con una sola máquina. Cuando este es el caso y adicionalmente se tienen menos de 5 máquinas en la estación final, el tiempo de corrida es mayor. Dado que en todos los casos se alcanza una solución óptima dentro del tiempo límite establecido, se prosigue a evaluar un tamaño de problema de 8 órdenes, para el que los resultados se muestran a continuación.

Número Órdenes

Número Estaciones


estación Elapsed

Time t - T*

Función Objetivo

8

3

1 1 - 1 - 2 164,56749 162,30399 3383,37407

2 1 - 2 - 3 3138,64054 3136,37704 3512,05369

3 1 - 3 - 5 1001,34211 999,07861 3699,2373

4 2 - 4 - 4 3,39700 1,13350 4100,21519

5 2 - 3 - 4 22,54077 20,27727 4100,21519

6 3 - 4 - 5 2,26350 0,00000 4100,21519

7 5 - 5 - 5 3,01472 0,75122 4100,21519

5

1 1 - 2 - 3 - 2 - 5 1982,20416 1980,74566 3546,58823

2 1 - 3 - 5 - 2 - 4 2793,57839 2792,11989 3546,58823

3 1 - 4 - 4 - 3 - 5 76,80319 75,34469 3546,58823

4 2 - 2 - 5 - 4 - 5 31,50361 30,04511 3546,58823

5 2 - 3 - 4 - 2 - 1 9036,21016 9034,75166 3546,58823

6 3 - 4 - 4 - 5 - 3 27,96857 26,51007 3546,58823

7 5 - 5 - 5 - 5 - 5 1,45850 0,00000 3546,58823

7

1 1 - 2 - 2 - 3 - 4 - 5 - 4 4319,92331 4312,51108 5619,29747

2 1 - 3 - 3 - 5 - 5 - 4 - 4 1253,81390 1246,40167 5619,29747

3 2 - 4 - 5 - 5 - 2 - 3 - 4 151,14539 143,73317 5619,29747

4 1 - 2 - 3 - 2 - 5 - 4 - 2 200422,943 200415,53077 5486,38641

~ 114 ~

5 3 - 4 - 5 - 2 - 1 - 5 - 2 200515,842 200508,42977 5486,38641

6 2 - 3 - 5 - 2 - 4 - 1 - 3 219,93811 212,52588 5619,29747

7 5 - 5 - 5 - 5 - 5 - 5 - 5 7,41223 0,00000 5619,29747

9

1 1 - 2 - 2 - 3 - 4 - 5 - 4 - 3 - 3 180398,459 180319,65632 5724,35534

2 1 - 3 - 3 - 5 - 5 - 4 - 4 - 5 - 2 180318,502 180239,69959 5724,35534

3 2 - 4 - 5 - 5 - 2 - 3 - 4 - 2 - 5 3308,41462 3229,61172 5724,35534

4 1 - 2 - 3 - 2 - 5 - 4 - 2 - 1 - 5 200313,115 200234,31210 5557,92171

5 3 - 4 - 5 - 2 - 1 - 5 - 2 - 4 - 3 200301,611 200222,80810 5557,92171

6 5 - 3 - 5 - 4 - 4 - 5 - 3 - 2 - 5 168,10187 89,29897 5724,35534

7 5 - 5 - 5 - 5 - 5 - 5 - 5 - 5 - 5 78,80290 0,00000 5724,35534


De forma similar al caso presentado anteriormente, en 3 de los 4 números de estaciones considerados se alcanzan los menores tiempos promedio en las configuraciones con 5 máquinas en todas las celdas de trabajo, instancias en las que siempre se obtienen los mayores valores de función objetivo. El caso restante, corresponde a una configuración que no contempla estaciones con una sola máquina, configuraciones que aumentan el tiempo de corrida del modelo. Sin embargo y teniendo en cuenta que el objetivo del modelo es encontrar una solución óptima para cualquier tipo de configuración de máquinas y que a partir de 7 estaciones el tiempo límite establecido no fue suficiente para la convergencia de 2 de ellas en ninguna de las réplicas realizadas, se toman 5 estaciones como la cota superior del modelo en este criterio y se decide evaluar hasta este límite un tamaño de problema de 9 órdenes, de manera que sea posible corroborar si el modelo puede brindar una solución con un tamaño superior de este criterio.

Número Órdenes

Número Estaciones


estación Elapsed

Time t - T*

Función Objetivo

9

3

1 1 - 1 - 2 725,771557 722,23736 5534,78304

2 1 - 2 - 3 908,159869 904,62568 5664,45732

3 1 - 3 - 5 1660,50234 1656,96815 6082,39938

4 2 - 4 - 4 31021,6424 31018,10824 6409,56035

5 2 - 3 - 4 315,591597 312,05740 6409,56035

6 3 - 4 - 5 24,7432099 21,20902 6509,09567

7 5 - 5 - 5 3,53419384 0,00000 6509,09567

5

1 1 - 2 - 3 - 2 - 5 200172,49 200166,88284 6729,71413

2 1 - 3 - 5 - 2 - 4 164616,528 164610,92084 6475,36213

3 1 - 4 - 4 - 3 - 5 200577,339 200571,73184 6287,57508

4 2 - 2 - 5 - 4 - 5 465,360009 459,75285 6766,62974

5 2 - 3 - 4 - 2 - 1 200565,075 200559,46784 6736,27616

~ 115 ~

6 3 - 4 - 4 - 5 - 3 188,277382 182,67023 6766,62974

7 5 - 5 - 5 - 5 - 5 5,60715603 0,00000 6766,62974


La Tabla A.7 muestra los resultados obtenidos en este caso. Como se observa, no es posible alcanzar dentro de los límites de tiempo computacional fijados, una solución óptima en ninguna de las réplicas realizadas en 3 de las 7 configuraciones de máquinas establecidas con 5 estaciones. Pruebas adicionales incluyendo los demás números de celdas de trabajo considerados y otros números de órdenes arrojaron resultados similares. De esta manera se concluye entonces que el límite superior del modelo se ubica en 8 órdenes y 5 estaciones.

~ 116 ~

APÉNDICE B

RESULTADOS EXPERIMENTALES DEL DISEÑO FACTORIAL 𝟐𝟑

PROPUESTO PARA ESTABLECER LOS PARÁMETROS DEL ALGORITMO

GENÉTICO

De manera que fuera posible construir un algoritmo genético contrastable con los resultados del modelo matemático formulado y la aproximación heurística

propuesta, se lleva a cabo un experimento factorial 23 para establecer si los diferentes niveles de los factores considerados: tamaño de la población y tasas de mutación y cruce, ejercen algún efecto sobre el valor de la función objetivo formulada a lo largo de todo el proyecto, relacionada con la maximización de las utilidades totales del ejercicio y de ser así, seleccionar la mejor combinación posible. La metodología a seguir se presenta en la siguiente imagen.

Gráfico B.1. Metodología del experimento

Los niveles de cada factor analizados se establecieron teniendo en cuenta los siguientes criterios. Inicialmente, para el tamaño de la población, se definió un límite inferior de 100 individuos, atendiendo a las recomendaciones de Rom y Slotnick (2009). A través de pruebas computacionales previas, en las que se definió un tamaño máximo de 1000 individuos, fue posible observar que a partir de 300 el valor de la función objetivo es aproximadamente constante, mientras que el tiempo computacional se incrementa significativamente al aumentar esta cifra, por lo que se tomó como límite superior un tamaño de 300 individuos. En torno a la tasa de cruce, se prueba el rango de probabilidades superiores a 0 e inferiores a 1, teniendo como límite inferior 0.1 y cota superior 0.9. Finalmente, para la tasa de mutación, considerando que según la literatura especializada este operador tiene una probabilidad de ocurrencia usualmente baja, se contempla el rango entre 0.1 y 0.5.

•Elegir los factores a analizar

•Estimar los niveles de cada factor

•Determinar el punto central

•Realizar el experimento factorial

•Escoger los niveles de cada factor adecuados para el algoritmo.

~ 117 ~

De esta manera, el experimento se construye tal como se muestra en la Tabla B.1.

Factor

Niveles

Bajo Punto Central Alto

Tamaño Población 100 200 300

Probabilidad Cruce 0.1 0.5 0.9

Probabilidad Mutación 0.1 0.3 0.5

Tabla B.1. Factores y niveles analizados

Con ayuda del software estadístico SPSS se realizaron las pruebas necesarias a través del análisis del Modelo lineal general univariante de efectos fijos, dado que el interés se concentra únicamente en los niveles elegidos [1]. En los siguientes apartados se encuentran los hallazgos más relevantes de este estudio.

ANÁLISIS DESCRIPTIVO

De forma inicial, se realiza un análisis descriptivo con el fin de observar las diferencias existentes entre las medias del valor de la función objetivo en todos los niveles de los factores considerados, obteniéndose los resultados que se muestran en la siguiente tabla.

Estadísticos descriptivos

Variable dependiente: F_Objetivo

Población P_Cruce P_Mutación Media Desviación

típica

N

100

,1

,1 3977,372425 263,8882860 100

,5 3978,529630 266,2955415 100

Total 3977,951028 264,4283766 200

,9

,1 3967,128258 264,9096093 100

,5 3965,386313 268,2169770 100

Total 3966,257286 265,8992428 200

Total

,1 3972,250341 263,7842681 200

,5 3971,957972 266,6670321 200

Total 3972,104156 264,8970307 400

200

,5 ,3 3983,189528 263,7118266 100

Total 3983,189528 263,7118266 100

Total ,3 3983,189528 263,7118266 100

Total 3983,189528 263,7118266 100

~ 118 ~

300

,1

,1 3987,354845 265,4191391 100

,5 3986,964895 265,9123602 100

Total 3987,159870 264,9975933 200

,9

,1 3981,805781 265,3913083 100

,5 3983,154538 265,5891726 100

Total 3982,480160 264,8232208 200

Total

,1 3984,580313 264,7521486 200

,5 3985,059716 265,0891396 200

Total 3984,820015 264,5886174 400

Total

,1

,1 3982,363635 264,0364371 200

,5 3982,747263 265,4682490 200

Total 3982,555449 264,4214015 400

,5 ,3 3983,189528 263,7118266 100

Total 3983,189528 263,7118266 100

,9

,1 3974,467020 264,5858297 200

,5 3974,270426 266,3837776 200

Total 3974,368722 265,1534456 400

Total

,1 3978,415327 264,0094507 400

,3 3983,189528 263,7118266 100

,5 3978,508844 265,6268587 400

Total 3978,987357 264,4069607 900

Tabla B.2. Estadísticos descriptivos Función Objetivo

Se aprecia de esta forma que las medias arrojadas por los tres factores son bastante homogéneas entre sí, por lo que podría pensarse que no ejercen ningún efecto sobre el valor de la función objetivo.

ANÁLISIS DE VARIANZAS – ANOVA

Para comprobar este supuesto, se realiza un análisis de varianzas ANOVA, que permite contrastar la hipótesis nula de que las medias de 𝐾 poblaciones

(𝐾 > 2) son iguales, frente a la hipótesis alternativa de que por lo menos una de las poblaciones difiere de las demás en cuanto a su valor esperado [2, 3]. De esta manera se formula la siguiente prueba de hipótesis: Para el factor 𝐴 (Tamaño de la población):

𝐻0: 𝜏1 = 𝜏2 = ⋯ = 𝜏𝑎 = 0 𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 𝜏𝑖 ≠ 0

~ 119 ~

Para el factor 𝐵 (Tasa de cruce):

𝐻0: 𝛽1 = 𝛽2 = ⋯ = 𝛽𝑏 = 0 𝐻𝑎 : 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 𝛽𝑗 ≠ 0

Para el factor 𝐶 (Probabilidad de mutación):

𝐻0: 𝛾1 = 𝛾2 = ⋯ = 𝛾𝑐 = 0 𝐻𝑎 : 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 𝛾𝑘 ≠ 0

Y entorno a las interacciones se tiene:

𝐻0: (𝜏𝛽)𝑖𝑗 = 0

𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 (𝜏𝛽)𝑖𝑗 ≠ 0

𝐻0: (𝜏𝛾)𝑖𝑘 = 0

𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 (𝜏𝛾)𝑖𝑘 ≠ 0

𝐻0: (𝛽𝛾)𝑗𝑘 = 0

𝐻𝑎: 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 (𝛽𝛾)𝑗𝑘 ≠ 0

𝐻0: (𝜏𝛽𝛾)𝑖𝑗𝑘 = 0

𝐻𝑎 : 𝑎𝑙 𝑚𝑒𝑛𝑜𝑠 𝑢𝑛𝑎 (𝜏𝛽𝛾)𝑖𝑗𝑘 ≠ 0

Los resultados obtenidos se muestran en la Tabla B.3.

Pruebas de los efectos inter-sujetos


Origen Suma de

cuadrados tipo

III

gl Media

cuadrática

F Sig.

Modelo corregido 50506,727a 8 6313,341 ,090 ,999

Intersección 11830944742,9

08

1 11830944742,9

08

167857,524 ,000

Población 32338,610 1 32338,610 ,459 ,498

P_Cruce 13404,497 1 13404,497 ,190 ,663

P_Mutación 1,749 1 1,749 ,000 ,996

Población * P_Cruce 2459,832 1 2459,832 ,035 ,852

Población * P_Mutación 29,782 1 29,782 ,000 ,984

P_Cruce * P_Mutación 16,833 1 16,833 ,000 ,988

Población * P_Cruce *

P_Mutación

268,871 1 268,871 ,004 ,951

~ 120 ~

Error 62799519,031 891 70482,064

Total 14311956374,2

07

900

Total corregida 62850025,758 899

a. R cuadrado = ,001 (R cuadrado corregida = -,008)

Tabla B.3. Análisis de varianzas – ANOVA Función Objetivo

El primer resultado de interés, se encuentra en el nivel de significancia de los términos del modelo. Como se observa, en todos los casos demarcados se obtiene un p-valor superior al nivel de significancia establecido en 5% (correspondiente a un nivel de confianza del 95%), por lo que se acepta la hipótesis nula comprobándose el supuesto emitido en el análisis descriptivo y dado que el modelo no se construye únicamente con la intersección, se concluye que el valor de la función objetivo no se encuentra influenciado por los factores considerados. Sin embargo, se decidió analizar de forma separada las estimaciones y gráficos de perfil de cada factor, de manera que pudiera observarse en detalle su efecto sobre la variable de respuesta. Los resultados alcanzados se muestran a continuación.

1. Tamaño de la Población

Estimaciones


Población Media Error típ. Intervalo de confianza 95%

Límite inferior Límite superior

100 3972,104a 13,274 3946,052 3998,157

200 3983,190a 26,548 3931,085 4035,294

300 3984,820a 13,274 3958,768 4010,872

a. Basada en la media marginal poblacional modificada.

Tabla B.4. Estimaciones de Función Objetivo respecto al Tamaño de la Población

~ 121 ~

Gráfico B.2. Gráfico de Perfil Función Objetivo respecto al Tamaño de la Población

Como se observa, en este caso se alcanzan mejores resultados considerando una población de 300 individuos, aunque la diferencia es bastante escasa respecto a un tamaño de 200.

2. Probabilidad de cruce

Estimaciones


P_Cruce Media Error típ. Intervalo de confianza 95%


,1 3982,555a 13,274 3956,503 4008,608

,5 3983,190a 26,548 3931,085 4035,294

,9 3974,369a 13,274 3948,316 4000,421


Tabla B.5. Estimaciones de Función Objetivo respecto a la Probabilidad de Cruce

~ 122 ~

Gráfico B.3. Gráfico de Perfil Función Objetivo respecto a la Probabilidad de Cruce

En este caso, se observan buenos resultados considerando tasas de cruce de 0.1 y 0.5, siendo esta última ligeramente mejor.

3. Probabilidad de Mutación

Estimaciones


P_Mutación Media Error típ. Intervalo de confianza 95%


,1 3978,415a 13,274 3952,363 4004,468

,3 3983,190a 26,548 3931,085 4035,294

,5 3978,509a 13,274 3952,456 4004,561


Tabla B.6. Estimaciones de Función Objetivo respecto a la Probabilidad de Mutación

~ 123 ~

Gráfico B.4. Gráfico de Perfil Función Objetivo respecto a la Probabilidad de Mutación

Finalmente, para la probabilidad de mutación se alcanzan mejores resultados con una tasa de 0.3. Es de anotar que existe alta similitud en los valores de la función objetivo alcanzados con los otros dos niveles. Tomando en consideración estos resultados, se decidió analizar la variable de respuesta concerniente al tiempo que tarda el algoritmo en derivar una solución óptima con los diferentes niveles de los tres factores analizados. Las observaciones de este nuevo análisis se muestran en los siguientes apartados.

ANÁLISIS DESCRIPTIVO

Una vez más, se realizó un análisis descriptivo para evidenciar las diferencias existentes entre las medias en el tiempo de corrida observado en todos los niveles de los factores considerados. Las observaciones se muestran en laTabla B.7.

~ 124 ~

Estadísticos descriptivos

Variable dependiente: TiempoCorrida

Población P_Cruce P_Mutación Media Desviación

típica

N

100

,1

,1 130,412015 16,6083686 100

,5 132,790952 15,1661339 100

Total 131,601484 15,9083540 200

,9

,1 138,097937 16,4312794 100

,5 148,396799 16,5479930 100

Total 143,247368 17,2393447 200

Total

,1 134,254976 16,9228711 200

,5 140,593876 17,6592601 200

Total 137,424426 17,5623871 400

200

,5 ,3 197,943226 16,5088546 100

Total 197,943226 16,5088546 100

Total ,3 197,943226 16,5088546 100

Total 197,943226 16,5088546 100

300

,1

,1 261,275672 15,3426246 100

,5 267,362464 16,8157108 100

Total 264,319068 16,3428581 200

,9

,1 266,824965 14,5188410 100

,5 273,058058 15,3343398 100

Total 269,941512 15,2187576 200

Total

,1 264,050319 15,1562759 200

,5 270,210261 16,3035111 200

Total 267,130290 16,0202258 400

Total

,1

,1 195,843844 67,5068210 200

,5 200,076708 69,3197307 200

Total 197,960276 68,3663379 400

,5 ,3 197,943226 16,5088546 100

Total 197,943226 16,5088546 100

,9

,1 202,461451 66,3525672 200

,5 210,727429 64,4813206 200

Total 206,594440 65,4725049 400

Total

,1 199,152647 66,9302980 400

,3 197,943226 16,5088546 100

,5 205,402068 67,0725839 400

Total 201,795788 63,4461103 900

Tabla B.7. Estadísticos Descriptivos Tiempo de Corrida

~ 125 ~

Como se observa, existen diferencias importantes entre los niveles considerados, especialmente entre los tamaños de población, por lo que podría inferirse que los factores ejercen un efecto sobre el tiempo de corrida del algoritmo.

ANÁLISIS DE VARIANZAS – ANOVA

Para verificar este supuesto, se realiza un análisis de varianzas ANOVA, para el que se formula la misma prueba de hipótesis empleada en el análisis del valor de la función objetivo. Los resultados se muestran en la Tabla B.8.

Pruebas de los efectos inter-sujetos


Origen Suma de

cuadrados tipo

III

gl Media

cuadrática

F Sig.

Modelo corregido 3392497,151a 8 424062,144 1669,304 ,000

Intersección 30233920,828 1 30233920,828 119014,639 ,000

Población 3364722,231 1 3364722,231 13245,097 ,000

P_Cruce 14909,758 1 14909,758 58,692 ,000

P_Mutación 7811,053 1 7811,053 30,748 ,000

Población * P_Cruce 1814,092 1 1814,092 7,141 ,008

Población * P_Mutación 1,601 1 1,601 ,006 ,937

P_Cruce * P_Mutación 813,300 1 813,300 3,202 ,074

Población * P_Cruce *

P_Mutación

755,365 1 755,365 2,973 ,085

Error 226345,462 891 254,035

Total 40268228,501 900

Total corregida 3618842,613 899

a. R cuadrado = ,937 (R cuadrado corregida = ,937)

Tabla B.8. Análisis de Varianzas – ANOVA Tiempo de Corrida

Inicialmente, es de importancia el valor de R cuadrado corregida, que indica que el 93.7% de la variabilidad se encuentra explicada por el modelo, lo cual representa un buen ajuste. Así mismo, en todos los casos se obtienen valores del estadístico F positivos, por lo que se consideran favorables. En torno a los valores de significancia se observa que:

1. Intersección: al obtenerse un p-valor de 0, inferior al nivel de significancia establecido en 5% se rechaza la hipótesis nula y por tanto puede concluirse que existe diferencia entre las muestras y que el modelo tiene sentido.

~ 126 ~

2. Tamaño de la Población: Al calcularse un p-valor de 0, inferior al nivel de significancia de 0.05, es posible rechazar la hipótesis nula y concluir que el modelo tiene sentido y por tanto, el tiempo que tarda el algoritmo en brindar una solución es diferente según el tamaño de la población que se defina.

3. Probabilidad de Cruce: se obtiene un p-valor de 0 inferior al nivel de significancia, por lo que se rechaza la hipótesis nula y es posible afirmar que el modelo tiene sentido y que el tiempo de corrida es diferente dependiendo de la probabilidad de cruce empleada.

4. Probabilidad de Mutación: al calcularse un p-valor de 0, inferior al nivel de significancia, se rechaza la hipótesis nula y se concluye que el modelo tiene sentido y que el tiempo de convergencia del algoritmo varía según la probabilidad de mutación escogida.

5. Tamaño de la Población * Probabilidad de Cruce: se calcula un p-valor de 0.008, inferior al 5% por lo que existen argumentos estadísticos para rechazar la hipótesis nula y concluir que el modelo tiene sentido y que existe relación entre los factores.

En los demás casos, se calcula un p-valor superior al nivel de significancia establecido en 5%, por tanto se acepta la hipótesis nula y se concluye que estos términos no ejercen ningún efecto sobre el tiempo de corrida del algoritmo. Con ayuda del software estadístico Minitab 15, fue posible estimar los coeficientes de la siguiente manera:

Tabla B.9. Resultados Ajuste Factorial para Tiempo de Corrida - Minitab 15

Por tanto, el modelo resultante se escribe de acuerdo con el modelo de efectos

como se muestra a continuación. Siendo 𝑦 el tiempo que tarda el algoritmo en derivar una respuesta.

~ 127 ~

𝑦 = 202.277 + 64.853(Tamaño Población) + 4.317(Probabilidad de Cruce)+ 3.125(Probabilidad de Mutación) − 1.506(Población ∗ P. Cruce)+ 𝜖𝑖𝑗𝑘𝑙

INTERPRETACIÓN O ANÁLISIS DE MEDIAS

Con base en los resultados obtenidos en el análisis de varianza, se procede a realizar de manera inicial una prueba de homogeneidad de varianzas de Levene, para la que se formuló la siguiente prueba de hipótesis:

𝐻0: 𝜎12 = 𝜎𝑚

2 = ⋯ = 𝜎𝑛2 (Las muestras tienen varianzas iguales)

𝐻𝑎 : Existen 𝑖 y 𝑗: 𝜎𝑚2 ≠ 𝜎𝑛

2 (Las muestras tienen varianzas diferentes)

Contraste de Levene sobre la igualdad de las varianzas

errora


F gl1 gl2 Sig.

1,089 8 891 ,368

Contrasta la hipótesis nula de que la varianza error de la

variable dependiente es igual a lo largo de todos los grupos.

a. Diseño: Intersección + Población + P_Cruce + P_Mutación +

Población * P_Cruce + Población * P_Mutación + P_Cruce *

P_Mutación + Población * P_Cruce * P_Mutación

Tabla B.10. Contraste de Levene sobre la igualdad de varianzas

Como se observa, se calcula un p-valor de 0.368, superior al nivel de significancia establecido en 5%, por lo que se acepta la hipótesis nula y se concluye que las muestras tienen varianzas iguales. Una vez comprobada esta hipótesis, se elige una prueba de comparación de medias de Scheffé, con el objetivo de visualizar la relación real que existe entre las muestras. Para ello, se formula la siguiente prueba de hipótesis: 𝐻0: 𝜇𝑚 = 𝜇𝑛 (No hay diferencia de medias)

𝐻𝑎 : 𝜇𝑚 ≠ 𝜇𝑛 (Existe diferencia entre medias) Los resultados de la prueba, así como las estimaciones y gráficos de perfil se presentan en los siguientes numerales.

~ 128 ~

1. Tamaño de la Población

Comparaciones por pares


(I)Población (J)Población Diferencia de

medias (I-J)

Error típ. Sig.d Intervalo de confianza al 95 %

para la diferenciad


100 200 -60,519

*,b,c 1,782 ,000 -64,016 -57,021

300 -129,706*,b,c

1,127 ,000 -131,918 -127,494

200 100 60,519

*,b,c 1,782 ,000 57,021 64,016

300 -69,187*,b,c

1,782 ,000 -72,684 -65,690

300 100 129,706

*,b,c 1,127 ,000 127,494 131,918

200 69,187*,b,c

1,782 ,000 65,690 72,684

Basadas en las medias marginales estimadas.

*. La diferencia de medias es significativa al nivel ,05.

b. Una estimación de la media marginal poblacional modificada (I).

c. Una estimación de la media marginal poblacional modificada (J).

d. Ajuste para comparaciones múltiples: Diferencia menos significativa (equivalente a la ausencia de ajuste).

Tabla B.11. Diferencia de muestras de Scheffé Tamaño de la Población

Como se observa, se ha calculado en todos los casos un p-valor de 0, inferior a 0.05, por lo que se rechaza la hipótesis nula y se concluye que existen diferencias entre los tamaños de población considerados. La menor divergencia se presenta entre 100 y 200 individuos, siendo la primera de ellas la que arroja mejores resultados.

Estimaciones


Población Media Error típ. Intervalo de confianza 95%


100 137,424a ,797 135,860 138,988

200 197,943a 1,594 194,815 201,071

300 267,130a ,797 265,566 268,694


Tabla B.12. Estimaciones de Tiempo de Corrida respecto al Tamaño de la Población

~ 129 ~

Gráfico B.5. Gráfico de Perfil Tiempo de Corrida respecto al Tamaño de la Población

Soportando las conclusiones de la prueba de Scheffé y tal como se muestra en el Gráfico B.5, el tiempo de corrida tiene un comportamiento aproximadamente lineal respecto al tamaño de la población que se defina, por lo que en este caso los menores tiempos se alcanzan con 100 individuos.

~ 130 ~

2. Probabilidad de Cruce



(I)P_Cruce (J)P_Cruce Diferencia de

medias (I-J)


para la diferenciad


,1 ,5 ,017

a,b 1,782 ,992 -3,480 3,514

,9 -8,634a,b,*

1,127 ,000 -10,846 -6,422

,5 ,1 -,017

a,b 1,782 ,992 -3,514 3,480

,9 -8,651a,b,*

1,782 ,000 -12,149 -5,154

,9 ,1 8,634

a,b,* 1,127 ,000 6,422 10,846

,5 8,651a,b,*

1,782 ,000 5,154 12,149



a. Una estimación de la media marginal poblacional modificada (I).

b. Una estimación de la media marginal poblacional modificada (J).


Tabla B.13. Diferencia de muestras de Scheffé Probabilidad de Cruce

Tal como se evidencia en la tabla, se notan dos casos: para las comparaciones entre las muestras resaltadas en rojo se ha calculado un p-valor inferior al nivel de significancia de 5%, por lo que existen argumentos estadísticos para rechazar la hipótesis nula y afirmar que existen diferencias entre medias. Por otra parte, las comparaciones no resaltadas indican un p-valor superior al nivel de significancia, lo que permite aceptar la hipótesis nula y concluir que no hay diferencia estadística entre los tiempos de corrida del algoritmo. El segundo caso se presenta entre las tasas de cruce 0.1 y 0.5, siendo ligeramente mejor esta última. La mayor diferencia se presenta en las probabilidades 0.5 y 0.9, siendo mejor la primera.

Estimaciones


P_Cruce Media Error típ. Intervalo de confianza 95%


,1 197,960a ,797 196,396 199,524

,5 197,943a 1,594 194,815 201,071

,9 206,594a ,797 205,030 208,159


Tabla B.14. Estimaciones de Tiempo de Corrida respecto a la Probabilidad de Cruce

~ 131 ~

Gráfico B.6. Gráfico de Perfil Tiempo de Corrida respecto a la Probabilidad de Cruce

Apoyando las conclusiones de la prueba de Scheffé, en el Gráfico B.6 se observa que las diferencias entre las tasas de cruce 0.1 y 0.5 son bastante escasas, por lo que en cualquiera de los dos casos se obtienen tiempos computacionales favorables.

~ 132 ~

3. Probabilidad de Mutación



(I)P_Mutación (J)P_Mutación Diferencia de

medias (I-J)


para la diferenciad


,1 ,3 1,209

a,b 1,782 ,498 -2,288 4,707

,5 -6,249a,b,*

1,127 ,000 -8,461 -4,037

,3 ,1 -1,209

a,b 1,782 ,498 -4,707 2,288

,5 -7,459a,b,*

1,782 ,000 -10,956 -3,961

,5 ,1 6,249

a,b,* 1,127 ,000 4,037 8,461

,3 7,459a,b,*

1,782 ,000 3,961 10,956



a. Una estimación de la media marginal poblacional modificada (I).

b. Una estimación de la media marginal poblacional modificada (J).


Tabla B.15. Diferencia de muestras de Scheffé Probabilidad de Mutación

De forma similar a la tasa de cruce, para la probabilidad de mutación se notan dos casos: para las comparaciones entre las muestras resaltadas en rojo se ha calculado un p-valor inferior al nivel de significancia de 5%, por lo que existen argumentos estadísticos para rechazar la hipótesis nula y afirmar que existen diferencias entre medias. Por otra parte, la comparación entre las tasas 0.1 y 0.3, alcanza un p-valor superior al nivel de significancia, lo que permite aceptar la hipótesis nula y concluir que no hay diferencia estadística entre los tiempos de corrida del algoritmo. En este caso, es ligeramente mejor una probabilidad de 0.3. La mayor diferencia se encuentra entre las probabilidades 0.3 y 0.5, siendo mejor la primera.

Estimaciones


P_Mutación Media Error típ. Intervalo de confianza 95%


,1 199,153a ,797 197,589 200,717

,3 197,943a 1,594 194,815 201,071

,5 205,402a ,797 203,838 206,966


Tabla B.16. Estimaciones de Tiempo de Corrida respecto a la Probabilidad de Mutación

~ 133 ~

Gráfico B.7. Gráfico de Perfil Tiempo de Corrida respecto a la Probabilidad de Mutación

Apoyando las conclusiones de la prueba de Scheffé, el Gráfico B.7 muestra mejores resultados cuando se emplea una tasa de mutación de 0.3. Una vez presentados los resultados del análisis de los factores de forma individual, a continuación se muestran las estimaciones y gráficos de perfil para la interacción que influye en el modelo. Tamaño de la Población * Probabilidad de Cruce

Población * P_Cruce


Población P_Cruce Media Error típ. Intervalo de confianza 95%


100 ,1 131,601

a 1,127 129,390 133,813

,9 143,247a 1,127 141,035 145,459

200 ,5 197,943a 1,594 194,815 201,071

300 ,1 264,319

a 1,127 262,107 266,531

,9 269,942a 1,127 267,730 272,153


Tabla B.17. Estimaciones de Tiempo de Corrida respecto al Tamaño de la Población *

Probabilidad de Cruce

~ 134 ~

Gráfico B.8. Gráfico de Perfil Tiempo de Corrida respecto al Tamaño de Población * Probabilidad de Cruce

Como se observa y ratificando las conclusiones previas, el tiempo de corrida tiene un comportamiento aproximadamente lineal a medida que aumenta el tamaño de la población. Los menores tiempos de corrida se alcanzan con una población de 100 individuos y una tasa de cruce de 0.1.

ANÁLISIS DE RESIDUALES

Como último paso del análisis y sustentado en la prueba de homogeneidad de varianzas de Levene presentada en la Tabla B.10 en el apartado rotulado: Interpretación o análisis de medias, es necesario corroborar si los residuales tipificados se distribuyen normalmente. Con el fin de comprobar este supuesto, se realiza un test de Kolmogorov-Smirnov, gracias a su buen ajuste en muestras de tamaño mayor a 50 datos, para el cual se formula la siguiente prueba de hipótesis:

~ 135 ~

𝐻0: Los residuales siguen una distribución normal 𝐻𝑎 : No se puede asumir normalidad de los residuales




Residuo estandarizado

para TiempoCorrida

,031 900 ,046 ,993 900 ,000


Tabla B.18. Prueba de normalidad de residuales

El p-valor calculado para esta prueba alcanza una cifra de 0.046, aunque es ligeramente inferior al nivel de significancia de 0.05, debido al buen ajuste del modelo y a los Gráficos B.9 y B.10, donde se observa que los datos se ajustan en su mayoría a la curva esperada de la distribución normal, se decide disminuir ligeramente el nivel de significancia de esta prueba a 1% y aceptar la hipótesis nula, siendo posible concluir que los residuos se distribuyen normalmente.

Gráfico B.9. Q-Q Plot Residuo Estandarizado

~ 136 ~

Gráfico B.10. Histograma de Residuo

Una vez comprobada la normalidad de los residuales, es necesario verificar el supuesto de independencia de los mismos. Para ello, se realizó en primera instancia un diagrama de dispersión de los residuos tipificados respecto al orden en que se obtuvieron. Tal como se observa en el Gráfico B.11, la nube de puntos no refleja regiones de concentración de las observaciones, por lo que no hay razón para suponer que exista alguna violación a este supuesto [4].

Gráfico B.11. Diagrama de residuales respecto a su orden

~ 137 ~

Para soportar estas conclusiones, se construyó el diagrama de series de tiempo de los residuos que se muestra en el Gráfico B.12, donde se observan dos características primordiales [3]:

Los residuos se mueven aleatoriamente alrededor del punto 0, lo que sugiere que el supuesto de que existe una relación lineal entre los factores es razonable.

No se observan puntos destacables entre la tendencia aleatoria de los residuales, lo que sugiere que no existen puntos extremos.

Gráfico B.12. Series de tiempo de Residuo tipificado

Finalmente, se construyó el diagrama de residuos respecto a los valores ajustados que se muestra en el Gráfico B.13, donde al no encontrarse una estructura fija, es decir, una tendencia obvia en las observaciones, se concluye finalmente que el modelo es correcto y que los supuestos se satisfacen.

Gráfico B.13. Diagrama de residuos vs. valores ajustados

~ 138 ~

ELECCIÓN DE LOS PARÁMETROS DEL ALGORITMO GENÉTICO

Tomando en cuenta los resultados del análisis de ambas variables de respuesta, se tomó la decisión respecto a los parámetros del algoritmo genético de la siguiente manera. En primera instancia, en torno al tamaño de la población inicial, los resultados del análisis ANOVA que se presenta en la Tabla B.3, relacionado con el efecto de los factores sobre el valor de la función objetivo, permiten notar que no existe un nivel estadísticamente superior a otro y tomando en consideración que de acuerdo con el Gráfico B.5, el tiempo de corrida del algoritmo es inferior cuando se emplea un tamaño de 100 individuos, se estima que estadísticamente este es el nivel ideal del factor. Sin embargo, gracias al tamaño de la muestra, fue posible observar en detalle el efecto de los niveles sobre las variables de respuesta, notándose que con 200 y 300 individuos se obtiene la solución óptima al problema de 7 órdenes y 5 estaciones elegido, resultado al que no es posible llegar considerando un tamaño de 100 individuos, sin importar el nivel de los demás factores. Adicionalmente y teniendo en cuenta que tal como se muestra en los Gráficos B.5 y B.8, el tiempo de corrida se incrementa de forma aproximadamente lineal respecto al tamaño considerado y que en las pruebas experimentales emplear un tamaño de 300 individuos incrementa notoriamente el tiempo computacional en comparación con los demás niveles, pero como se observa en el Gráfico B.2, no presenta diferencias sustanciales en la utilidad respecto al uso de 200 individuos, se elige entonces un tamaño de población de 200. Una vez se fija el nivel de este factor, se procede a analizar las tasas de cruce y mutación. En el primer caso, la diferencia de medias, estimadores y gráficos de perfil permiten observar que para ambas variables de respuesta se encuentran mejores resultados con una tasa de 0.5. Respecto a la probabilidad de mutación, el análisis estadístico realizado de las variables de respuesta permite concluir que las mejores soluciones se obtienen con una tasa de 0.3.

~ 139 ~

BIBLIOGRAFÍA

[1] G. C. Canavos, Probabilidad y Estadística. Aplicaciones y métodos, México, D.F.: McGraw-Hill, 1988.

[2] Universidad de Barcelona, «Análisis de la varianza con un factor,» [En línea]. Available: http://www.ub.edu/aplica_infor/spss/cap4-7.htm. [Último acceso: 2 Agosto 2015].

[3] L. E. Castillo, Notas de Clase. Diseño de Experimentos y Análisis de Datos, Bogotá: Maestría en Ingeniería Industrial. Universidad Distrital Francisco José de Caldas, 2013.

[4] G. A. Méndez Giraldo, Notas de Clase. Simulación de Sistemas., Bogotá: Maestría en Ingeniería Industrial. Universidad Distrital Francisco José de Caldas, 2014.

Documents

DISEÑO DE UN PROCEDIMIENTO BASADO EN ALGORITMOS ...repository.udistrital.edu.co/bitstream/11349/2785/1... · diseÑo de un procedimiento basado en algoritmos genÉticos para dar