PROGRAMACION MULTIOBJETIVO DE MAQUINAS EN PARALELO IMPLEMENTANDO HEURISTICA GENERICA PARA EL PROBLEMA Qm \ ri \ Cmax ,Fi LUIS CONRADO PUELLO IVAN

DIAZ TATIS ENRIQUE MANOTAS ARAUJO

RESUMEN El siguiente trabajo introduce una heurstica genrica que permite hallar una solucin ptima a la configuracin que se plantea en la programacin de la produccin con maquinas en paralelo. Esta heurstica genera soluciones en base a experimentos realizados, planteados para procesos con m maquinas en paralelo y tiempos de liberacin i, minimizando el tiempo de fabricacin y el Tiempo Total del Flujo de Trabajo dentro del proceso productivo. Estos objetivos tienen impacto directo tanto en la productividad del proceso como en la capacidad de cumplimiento en las fechas de entrega de los productos a los clientes.

INTRODUCCION Los problemas de programacin de la produccin se han estudiado desde siempre, dado su carcter variable y su nivel de complejidad es difcil encontrar una solucin ptima que se ajuste a los objetivos trazados, incluso el clculo manual de estos puede ser no preciso y tedioso. A esto se suma el hecho de que los problemas reales por lo general son multiobjetivos por naturaleza, es decir rara vez una decisin es tomada en base a un solo criterio. Por esta razn, resulta de gran inters el desarrollo de herramientas que reflejen las necesidades industriales y que puedan entregar soluciones en un tiempo razonable. Es por esta razn que las heursticas surgen como una alternativa prctica para resolver este tipo de situaciones. El presente artculo, hace una breve descripcin de una heursticas multiobjetivo como una nueva herramienta propuesta por los autores, este algoritmo propuesto, es aplicado a un problema con m maquinas en paralelo para n trabajos y pretende minimizar los tiempos de flujo mximos y los tiempos mximos de terminacin. Los resultados obtenidos indican claramente las ventajas del algoritmo lo que implica una mejora en la eficiencia de la programacin de la produccin, importante en el mejoramiento de los sistemas productivos actuales.

ABSTRACT This work presents a multiobjective optimization heuristic generic that allows finding an optimal solution to the configuration that considers in the programming of the production with machines in parallel. This heuristic one generates solutions on the basis of experiments made, raised for processes with m machines in parallel and times of liberation i, diminishing the time of manufacture and the Total Time of the Job stream within the productive process. These objectives as much have direct hit in the productivity of the process as in the capacity of fulfillment in the dates of delivery of products to the clients.

REVISION BIBLIOGRAFICA El problema de La Programacin Multiobjetivo puede definirse como la bsqueda de un vector de variables de decisin que satisfagan un cierto conjunto de restricciones y optimice un conjunto de funciones objetivo. Estas funciones forman una descripcin matemtica de los criterios de desempeo que suelen estar en conflicto unos con otros y que se suelen medir en unidades diferentes. Se desea encontrar un vector de decisin Con ERn, que deber satisfacer restricciones de desigualdad gi 0 i=1,2 , ... ,w y optimizar el vector de funciones

y reensayos. El mtodo consiste en generar candidatos de soluciones posibles de acuerdo a un patrn dado; luego los candidatos son sometidos a pruebas de acuerdo a un criterio que caracteriza a la solucin. Si un candidato no es aceptado, se genera otro; y los pasos dados con el candidato anterior no se consideran.

DEFINICION Y MODELADO DEL PROBLEMA La mayora de problemas de programacin de la produccin real tienen varios objetivos que deben satisfacerse simultneamente y se encuentras sujetos a ciertas restricciones de su propio entorno. Debido a esta condicin de mltiples objetivos, la concepcin de solucin ptima cambia completamente refirindose a estos problemas de produccin, en este caso ya no obtendremos una nica solucin posible, tendremos un conjunto de soluciones. Consideraremos el problema de programacin para n trabajos independientes y m maquinas en paralelo con diferentes tiempos de procesamiento disponibles desde el tiempo cero. El objetivo es minimizar el mximo tiempo de terminacin y el mximo tiempo de flujo. En el modelo asumimos lo siguiente: 1. Las maquinas se encuentran en paralelo y poseen diferentes tiempo de procesamiento para cada trabajo. 2. Cada mquina puede procesar un solo trabajo al tiempo. 3. Una vez comienza un trabajo en la maquina este debe ser terminado

que generalmente cumple con . Una vez encontradas las soluciones optima para el problema, definimos la Dominancia de Pareto, sean dos soluciones u, v se dice que u domina a v (denotado como u v) si es mejor o igual que v en cada uno de los objetivos y estrictamente mejor en al menos un objetivo.

Las mejores soluciones en un problema multi objetivo estn dadas por el ptimo global de Pareto lo cual representa el subconjunto no dominado de todas las soluciones factibles. La imagen de este subconjunto se conoce como el Frente de Pareto. En programacin se dice que un algoritmo es heurstico cuando la solucin no se determina en forma directa, sino mediante ensayos, pruebas

4. Todos los trabajos estn disponibles de acuerdo a su tiempo de liberacin, sin embargo algunas maquinas podran no estar disponible para ese momento especifico. 5. Los tiempos de preparacin son independientes de la secuencia y estn incluidos en los tiempos de procesamiento. A continuacin describimos las variables involucradas en nuestra heurstica: Datos: a =[1 hasta n] n, Numero de trabajos totales i, Trabajo i, k, posicin en el vector j, Maquina j m, numero de maquinas totales Cmax, Makespan F, tiempo de flujo Variables: Ri, tiempo de liberacin del trabajo i Pij, i=1,,, n, j=1,,,m tiempo de procesamiento del trabajo i en la maquina j El programa optimiza el siguiente problema Qm \ ri \ Cmax ,Fi para maquinas en paralelo, donde los objetivos en produccin son minimizar el lapso de tiempo Cmax de produccin y los tiempos de flujo totales Fi. En orden de encontrar respuestas optimas que solucionen nuestro problema, realizaremos un algoritmo cuya base es la heurstica, nos basamos en el principio TPC (Tiempo de Procesamiento Ms Corto) para minimizar el tiempo del flujo de trabajo, se ordenan los tiempos de liberacin de menor a mayor ya que nos indican la disposicin que tiene cada trabajo para ser procesado a lo largo del tiempo.

Una vez ordenados los Rj, seleccionaremos el trabajo con menor tiempo de liberacin y observaremos el tiempo de procesamiento que tiene este en cada una de las maquinas, ubicando la elaboracin del trabajo en la maquina con menor tiempo de procesamiento, asi sucesivamente hasta asignar el ltimo trabajo a la ultima maquina, teniendo en cuenta que las maquinas solo pueden realizar un trabajo a la vez y solo pueden asignarles trabajos si estn disponibles. Los tiempos de liberacin de cada trabajo se almacenaran en un vector como parte del desarrollo del algoritmo. Los tiempos de terminacin de cada trabajo se guardaran en un vector, de igual forma como se hizo con los tiempos de liberacin. Realizamos la sumatoria de los tiempos de terminacin y le restaremos la sumatoria de los tiempos de liberacin, hallando el tiempo total de flujo. Dentro del vector que contiene los tiempos de terminacin seleccionamos el dato con mayor valor, este ser nuestro Cmax. A continuacin planteamos la secuencia de pasos lgicos para llegar a la solucin deseada Algoritmo: Paso 1: Ordenar los n trabajos, de acuerdo a su fecha de liberacin en orden creciente en un vector []. Paso 2: Asignar el trabajo i que est en la posicin k=a del vector del paso 1 a la mquina j de acuerdo al tiempo de procesamiento ms corto. Paso 3: Determinar el tiempo de terminacin para el trabajo asignado en el paso 2,

esto es Ri+ Pij y luego guardando este resultado en un vector V[] Paso 4: Despus de asignar el primer trabajo se tiene que determinar si para la siguiente Ri todas las maquinas estn disponibles, si no es as se restringe la maquina ocupada, esto es, comparando el tiempo de terminacin de los trabajos (Ri+ Pij) asignados en el paso 2 con las Ri que siguen, luego se sigue al paso 2 de nuevo y se repite la secuencia hasta que sean asignados todos los trabajos Paso 5: Se calcula el Cmax buscando el mayor valor del vector utilizado en el paso 3 y el tiempo de flujo primero sumando los vectores de los pasos 1 y 3, y luego restando el total del vector del paso 1 al vector del paso 3