Artículos de investigación
Resumen: Para problemas multi-objetivo, los métodos de poda actuales son útiles para reducir de forma considerable la cantidad de soluciones que son obtenidas en un frente de Pareto, además de satisfacer la mayoría de las características que el decisor requiere para tomar una decisión correcta en la elección de una solución. Sin embargo, estos métodos pueden llegar a ser muy complejos y carecer de algunas propiedades relevantes para calcular la solución óptima. Basándonos en las necesidades que el decisor tiene para seleccionar la mejor solución en un problema de planeación de la producción, este trabajo presenta un nuevo método de poda que obtiene mejores valores en las funciones objetivo, un número no mayor a 10 soluciones para que el decisor sea capaz de hacer una elección rápida y precisa, y está basado en operaciones simples que facilitan su implementación.
Palabras clave: Método de Poda, Problema Multi-Objetivo, Óptimo de Pareto.
Abstract: For multi-objective problems, the current pruning methods are useful to reduce considerably the number of solutions obtained in a Pareto front, besides of satisfying most of the features that the decision maker requires in order to choose a better solution. However, these methods can be very complex and lack of some relevant properties to calculate the optimal solution. Based on the needs that a decision maker has for selecting the best solution in production planning problem, this work presents a new pruning method that obtains solutions with better values in the objective functions, no more than 10 solutions in order to make a quick and accurate decision, and it is based on simple operations which facilitate its implementation.
Keywords: Multi-objective problem, Pareto optimum.
1. Introducción
En la actualidad, muchos de los problemas de ingeniería implican la optimización de múltiples objetivos, donde el decisor busca una solución que optimice de mejor forma todas las metas del problema. Sin embargo, al considerar múltiples objetivos se pueden obtener un número bastante grande de soluciones sub-óptimas (óptimo de Pareto o frente de Pareto) (Guo et al., 2013); y para el decisor no siempre es práctico tener tantas soluciones. En la actualidad, la mayoría de las veces el conocimiento, la intuición y la experiencia previa del decisor sirven para disminuir considerablemente el número de soluciones y obtener una que satisfaga sus requerimientos. El análisis de un frente de Pareto, posiblemente compuesto por cientos de soluciones, para seleccionar una única solución que mejor refleja las preferencias del decisor, puede ser una tarea desalentadora (Smith-Quintero et al., 2004). Otro factor importante a considerar es el manejo de los parámetros que cada problema en particular presenta para determinar la solución que mejor se adapte a las funciones objetivo. Por esta razón, proponemos un nuevo método de poda que minimice la cantidad de soluciones, que la experiencia del decisor no sea el factor esencial en la elección de la mejor poda, y que contenga soluciones con características que faciliten al decisor elegir la solución correcta.
La experimentación del método está realizada en resultados ya publicados por Guo et al. (2013), cuyo trabajo trata la asignación de órdenes de producción para un proceso textil que considera diferentes plantas y cada planta puede contener hasta cinco procesos. El propósito del estudio es optimizar las siguientes tres funciones objetivo:
1. Función Objetivo 1: Minimizar la tardanza total de todas las órdenes de producción.
2. Función Objetivo 2: Reducir al mínimo el tiempo de procesamiento total de todas las ordenes de producción.
3. Función Objetivo 3: Reducir al mínimo el tiempo de inactividad total de todos los departamentos de producción.
2. Sistema de Producción Textil
La etapa de planeación y programación de órdenes de producción debe de tener en cuenta el entorno de producción del mundo real de las empresas manufactureras, donde existen múltiples plantas situadas en distintos lugares y con múltiples departamentos de producción. Las empresas manufactureras de este tipo reciben un gran número de pedidos de producción de diferentes clientes, que deben ser asignados a las plantas de producción. La producción de un producto (o una orden de producción) implica múltiples procesos de producción, incluyendo los procesos ordinarios y procesos especiales. Cada planta puede producir todos los procesos ordinarios. Sin embargo, no todas las plantas pueden producir procesos especiales ya que carecen del departamento de producción requerido. La asignación de órdenes de producción a una determinada planta genera la posibilidad de que ésta no tenga el proceso de producción requerido, por tal motivo el producto tenga que ser trasladado a otra planta. El fabricante debe determinar cómo asignar cada orden de producción a la planta adecuada y determinar la hora de inicio de cada proceso en un horizonte de planificación de varios meses, a lo que le llamaremos problema de programación de órdenes de producción multi-sitio. Este problema es enfrentado por un gran número de empresas manufactureras, como la industria del vestido. La investigación sobre este problema es muy importante, porque su ejecución afecta en gran medida el rendimiento y el control de la producción, así como la administración de la cadena de suministros.
De acuerdo a Guo et al. (2013), el proceso de producción textil considera n plantas de producción, ubicadas en lugares diferentes. Estas plantas incluyen los N departamentos de producción numeradas de 1 a N, que realizan respectivamente N tipos de diferentes procesos productivos indicados como proceso de tipo 1 al tipo de proceso N. Estos departamentos de producción se pueden clasificar en dos categorías: categoría ordinaria y categoría especial. Cada categoría involucra múltiples departamentos de producción. La planta que pertenece a la categoría ordinaria incluye todos los departamentos de producción, mientras que la categoría especial incluye a las plantas que sólo tienen algunos de los N departamentos de producción. La Figura 1 muestra las plantas ordinarias y especiales del proceso textil
2.1 Funciones Objetivo
Los valores de las funciones objetivo son determinados de la siguiente manera:
Función objetivo 1 (Días de tardanza total de todas las órdenes de producción):
Donde:
= Hora de inicio del proceso
= Proceso de producción del tipo j de la órden
= Órdenes de producción
= Indica si el proceso
se asigna al departamento de
producción
= Departamento de producción de tipo j en la planta k
= Tardanza (días de tardanza de la orden
)
= Número de órdenes de producción
= Fecha de vencimiento de la órden
= Tiempo de acabado de la orden , el tiempo en que
sea entregado en el almacén
Función objetivo 2 (reducir al mínimo el tiempo (días) de procesamiento total de todas las órdenes de producción):
Donde:
= Tiempo de producción de la orden
= Hora de inicio del proceso
= Plazo de ejecución para llevar acabo todos los procesos
de producción de cada orden
Función objetivo 3 (reducir al mínimo el tiempo (días) de inactividad total de todos los departamentos de producción):
Donde:
= El tiempo de espera, tiempo de esperar la llegada del
proceso
en el departamento de producción
equivale a
menos el tiempo de finalización del anterior proceso de producción realizado en el mismo departamento de producción. Este último se determina por el simulador de procesos de producción propuesto.
2.2 Simulador del Proceso de producción
Se desarrolló un simulador en Matlab para obtener el costo de los tres objetivos para una solución propuesta. El simulador determina la capacidad de cada departamento y la hora de inicio de cada proceso de producción según su asignación en una planta determinada. La entrada del simulador es una asignación (o cromosoma) que indica la asignación de cada grupo de orden en una planta de producción inicial. El conjunto de valores en las funciones objetivo es la salida del simulador. El simulador requiere la inicialización de los siguientes datos de entrada: tiempo de entrega, producción asignada en cada departamento y tiempo de transporte. Las órdenes de producción forman grupos de orden según sus fechas de vencimiento. Cada grupo de orden se asigna a una planta inicial única en la que se debe procesar cada orden del grupo. Si la planta no tiene el departamento de producción necesario, la orden se asigna al azar a una planta con el departamento requerido; de lo contrario, permanece en la planta asignada. Las órdenes de producción se subdividen de acuerdo a un porcentaje α de la capacidad de producción diaria en el departamento número 4. Se calcula el retraso total de las órdenes de producción, el tiempo de procesamiento total y el tiempo de inactividad de los departamentos de producción. La Figura 2 muestra el proceso de simulación, las reglas detalladas que especifican cómo funciona el simulador pueden consultarse en (Guo et al., 2013).
El algoritmo evolutivo NSGA-II (Deb et al., 2002), es uno de los mejores algoritmos de optimización multi-objetivo para obtener soluciones satisfactorias. Este algoritmo, junto con el simulador del proceso de producción textil, obtienen como resultado el óptimo de Pareto.
El NSGA-II fue ejecutado considerando una población de 500 cromosomas creados de forma aleatoria y 500 generaciones para llegar al óptimo de Pareto.
3. Nuevo Método de Poda
El método de podado está basado en el principio de Sturges, (Scott, 2011), y sus principales características son:
· Reduce de forma significativa el método de Pareto.
· Conserva la diversidad entre las soluciones.
· Mantiene las soluciones óptimas para cada objetivo.
· Minimiza el grado de complejidad en la implementación.
· El decisor puede o no tener la experiencia sobre el problema a optimizar.
3.1 Metodología de Poda
I) El decisor propone el número máximo de soluciones y el ancho de intervalo, para cada función objetivo. Si el tomador de decisiones no tiene la experiencia necesaria para determinar el ancho de intervalo, éste se inicializa en cero.
II) Si fuera el caso se eliminan todos menos uno de los cromosomas que sean exactamente iguales, y se cuantifican los cromosomas restantes.
III) Se realiza la comparación; si la cantidad de cromosomas restantes es menor a la cantidad de soluciones que el decisor propuso el algoritmo termina, de lo contrario sigue.
IV) Se calcula el rango para cada objetivo y se determina la clase ([C=3.3*log(Número de cromosomas)+1]*Inc), donde inicialmente Inc=1; de acuerdo a la regla de Sturges con la finalidad de obtener el ancho de cada intervalo.
V) Si el ancho del intervalo es menor o igual al propuesto por el decisor el algoritmo finaliza, de lo contrario continúa.
VI) Se evalúan los valores de las funciones objetivo de cada solución para cada uno de los intervalos de cada objetivo. Si por lo menos un valor de las funciones objetivo de una solución pertenece a uno de los intervalos, el cromosoma se mantiene, de lo contrario se elimina.
VII) En el caso de que no se haya eliminado ningún cromosoma, la variable Inc se incrementa en 0.1 y regresamos al paso número III.
4. Resultados
Guo et al. (2013), considera los tres problemas siguientes:
a) Problema 1: 50 órdenes de producción y 10 grupos de orden.
b) Problema 2: 75 órdenes de producción y 12 grupos de orden.
c) Problema 3: 145 órdenes de producción y 15 grupos de orden.
El objetivo 1 se considera de mayor importancia que el objetivo 2 y 3, y a su vez el objetivo 2 es considerado de mayor importancia que el objetivo 3. De acuerdo a lo anterior se realiza el análisis de los resultados del nuevo método de poda y la poda propuesta por Taboada.
Para las podas obtenidas en cada uno de los tres problemas expuestos, las soluciones están codificadas de la siguiente forma:
· A – Soluciones obtenidas por la nueva poda propuesta.
· B – Soluciones propuestas usando el método en (Taboada y Coit, 2008).
· AB – Soluciones donde coinciden ambos metodos.
La Figura 3 muestra la poda obtenida por ambos métodos referente al Problema 1. Como podemos observar todas las soluciones fueron obtenidas por el método propuesto. El método de Taboada y Coit (2008) obtiene la mayoría de las soluciones. Sin embargo, las soluciones que este método no calcula se pueden considerar importantes para decidir la solución idónea.
La Figura 4 muestra los resultados obtenidos para el Problema 2, como podemos observar las soluciones con mejores valores óptimos son obtenidas por el nuevo método de poda, lo que permite realizar una mejor selección para elegir una única solución.
La Figura 5 muestra la poda obtenida por ambos métodos para el Problema 3. Como podemos observar, el nuevo método de poda obtiene soluciones con mayor factibilidad y diversidad, dando mayor perspectiva para la selección final de una solución.
5. Conclusiones
El nuevo método de poda que se presenta en este trabajo obtiene soluciones en los tres problemas planteados con valores para cada objetivo con mayor eficiencia, diversidad y con un número de soluciones no mayor a quince contra el método con el que se está comparando. Otro punto importante son los óptimos de cada objetivo, que aunque muchas de las veces no son soluciones óptimas, dan un panorama del rango en que se encuentra situada la solución óptima de cada función objetivo, lo que permite tomar una mejor decisón.
Por esta razón, consideramos que el método de poda desarrollado obtiene un panorama más amplio para la selección de la mejor solución en un problema multi-objetivo.
Referencias
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Guo, Z. X., Wong W. K., Li, Z., Ren, P. (2013). Modeling and Pareto Optimization of Multi-Objective Order Scheduling Problems in Production Planning. Computers & Industrial Engineering, 64, 972-986.
Scott, D. W. (2011). Sturges’ and Scott’s Rules, in: International Encyclopedia of Statistical Science, Springer, 1563–1566.
Smith-Quintero, R., Corral-Espinal, A., Aristizábal, J. A. (2004). Un Enfoque de Análisis Multi-objetivo para la Planeación Agregada de Producción. Dyna, 71 (141), 15-27.
Taboada H. A., Coit D. W. (2008). Multi-objective scheduling problems: determination of pruned Pareto sets, IIE Transactions 40(5), 552–564.
