Estimacion Del Frente Optimo De Parteto Utilizando MOGA

Estimación del Frente Óptimo de Pareto, aplicando el método MOGA en un sistema de producción tipo flow shop

Raúl Leonel Santillán Menchaca1, Sergio Manuel Ramírez Campos2

Instituto Tecnológico de Saltillo

Departamento de Estudios de Posgrados e Investigación

Saltillo, Coahuila, México

Email: raul_santillan@hotmail.com, sramirez@its.mx

Resumen

En este artículo se presenta una aplicación del método MOGA ó Multi-Objective Genetic Algotithm basado en el Frente Óptimo de Pareto que atiende un caso real de planeación de la producción en un sistema tipo flow shop donde se procesan guantes de látex considerando dos objetivos en conflicto: minimizar el número de ciclos y maximizar el cumplimiento de pedidos, esta situación implica que un objetivo puede mejorar a costa de empeorar al otro. Dichas características corresponden a un problema con objetivos múltiples (multi-objective problem ó MOP). Los resultados muestran que el modelo genético desarrollado logra buenas aproximaciones al Frente de Pareto donde se pueden identificar soluciones aceptables para ambos objetivos.

Palabras clave: problema multi-objetivo, algoritmo genético, Frente Óptimo de Pareto,

Abstract

In this paper it show an application of MOGA or Multi_Objective Genetic Algorithm method based on the Optimal Front of Pareto that it takes care a real case of planning of the production in a flow shop system where gloves latex are processed considering two objectives in conflict: to minimize the number of cycles and maximize the fulfillment of the dates of delivery, this situation implies that an objective can improve at the cost of getting worse to the other. These characteristics correspond to a multi-objective problem or MOP. The results shows that the developed genetic model obtains goods approaches to Front of Pareto where acceptable solutions for both objectives can be identified.

Key Words: Multi-objective Problem (MOP), genetic algorithm, Optimal Front of Pareto

Introducción

En los problemas de optimización lo habitual es considerar unas restricciones y un solo objetivo como puede ser maximizar un beneficio ó minimizar un gasto, Arsham (2009). Sin embargo como todos sabemos, en las empresas los objetivos son múltiples y a veces excluyentes, es decir el cumplimiento de un objetivo se hace a cuestas de incumplir otros, Por ejemplo una compañía desea maximizar el tiempo de vida del producto mientras que también intenta minimizar el costo de producción. Comúnmente, estos dos objetivos no se pueden alcanzar con una sola solución, por lo tanto es necesario realizar algunos ajustes a los parámetros del modelo, la compañía puede buscar que combinaciones de esos objetivos son posibles, dado un conjunto de restricciones. En los problemas de programación y secuenciación de la producción en un grupo de maquinas recibe considerable atención en la literatura. La decisión de qué tareas deben asignarse a las maquinas y en qué orden se tiene qué atender a la producción, forman parte de un problema combinatorio casi siempre muy complicado y frecuentemente es NP complejo, de acuerdo a Oduguwa et al. (2004) la mayoría de los problemas del mundo real generalmente son a gran escala, presentan no linealidades y alta incertidumbre, son multi-dimensionales y difíciles de modelar.

Esta nueva área de investigación llamada ahora optimización evolutiva con objetivos múltiples ha crecido considerablemente y esto se refleja con un notable incremento sobre todo en los últimos 20 años de artículos técnicos en revistas internacionales, sesiones especiales en conferencias especializadas y algunos grupos de interés, desde Tamaki et al. (1996) que hace una revisión muy breve y superficial de algunas de las técnica más importantes y Fonseca y Fleming (1995) que hacen una excelente reseña de los principales problemas que se enfrentan al tratar de lidiar con objetivos múltiples usando una técnica evolutiva.

Hasta algunos desarrollos importantes como los de Zhou et al. (2005) donde exploran la regularidad que presentan las distribuciones de las soluciones Óptimas de Pareto considerando solo dos objetivos basándose en el análisis de componentes principales y el ajuste por mínimos cuadrados para construir el modelo. Laumanns et al. (2002) proponen algunas estrategias que ayudan a construir MOEAs (Multi-Objetive Evolutive Algorithm simple), que muestren propiedades deseables de convergencia y diversidad en una sola corrida.

Relacionado con esto último, Deb y Jain (2002) aportan dos métricas normalizadas para medir ambas propiedades (convergencia y diversidad) facilitando una mayor visión de los MOEAs y una comparación entre sí. Fieldsend et al. (2001) demuestran el impacto indeseable de restringir el número de soluciones en el archivo de Pareto y proponen nuevas estructuras de datos (soluciones dominadas y soluciones no dominadas). La optimización con objetivos múltiples es, sin duda, un área de investigación muy importante tanto para los científicos como para los ingenieros, no sólo debido a que la mayoría de los problemas del mundo real tienen objetivos múltiples, sino también porque todavía restan por resolver muchas interrogantes en esta disciplina.

La investigación está relacionada con un sistema de manufactura tipo flow shop en donde se hace una aplicación del método Múltiple Objective Genétic Algorithm (MOGA) modelado atreves de algoritmos genéticos basados en el Frente Óptimo de Pareto donde se da resolución a dos objetivos que están en conflicto, uno de ellos es minimizar el número de ciclos y el otro es maximizar el cumplimiento de producción en las fechas de entrega.

Información relevante del proceso

En este artículo se presenta una metaheurística para una problemática en la fabricación de guantes de látex. Los detalles del proceso, las limitantes, constantes, las variables así como los cálculos se encuentran en un artículo anterior Ramírez et al. (2009).

Un ejemplo relacionado es el problema de secuenciación en línea como el que se muestra en la (Figura 1), donde en un sistema de flujo en línea se tienen 3 tareas que deben ser procesadas en un conjunto de 4 máquinas y cada tarea tiene el mismo orden de secuencia a través de las máquinas, es decir, cada una de las tareas debe ser procesada primero en la máquina 1, luego en la máquina 2, y así sucesivamente hasta llegar a la máquina 4. El tiempo de procesamiento de la tarea j en la máquina i se denota por Pij y el tiempo total de procesamiento se denomina Cmax.

El problema de esta investigacion es encontrar la secuencia en que los números de parte se van a programar de acuerdo a una demanda que se tiene que cumplir en un periodo de 14 días hábiles: del 15 de Abril del

...