Un procedimiento heurístico para la resolución del problema del taller

Enrique C. DIEZ DE CASTRO Universidad H ispalense UN PROCEDIMIENTO HEURISTICO PARA LA RESOLUCION DEL PROBLEMA DEL TALLER El problema del taller como todos los problemas de secuenciación son de gran complejidad. Los procedimientos de resolución no son fáciles de aplicar. Por ello presentamos un procedimiento sencillo que permita salvar los inconvenientes anteriores. I) INTRODUCCION De los cinco procesos básicos que componen la administración (Planificación, Organización, dirección, dotación de Personal y con trol), el más importante, primario y que prevalece sobre los demás es el de planificación. Todo proceso planificador implica la constitución de una serie de líneas posibles de acción y la selección o elección de una de ellas, es decir, comporta una toma de decisiones. Para efectuar la elección entre las diferentes alternativas posee mos tres criterios válidos (1): a) LA EXPERIMENTACION.- Consiste en probar las diferentes alternativas seleccionando aquella que nos proporcione me jores resultados. Sin embargo, tal como afirma Newman (2) la técnica expe rimental debería ser utilizada como un último instrumento una vez que se hayan probado otras técnicas de planifica ción. b) LA EXPERIENCIA.- Es un factor muy importante que combi nado con la intuición puede conseguir resultados muy satis factorios. c) INVESTIGACION Y ANALISIS.- Es el criterio más efectivo y usado para seleccionar alternativas. Una de las aproximacio nes mas completas de investigación y análisis en la toma de decisiones la constituye la investigación Operativa, también denominada análisis operacional o “Ciencia de la Adminis tración”. 57 No obstante, la Investigación Operativa a la hora de tomar decisiones no pasa de ser una recomendación, una ayuda para que el responsable de la toma de decisiones pueda es coger un camino mejor que le lleve a alcanzar los objetivos de la empresa (3). Conscientes de la gran importancia que representan los criterios empíricos, intuitivos y de investigación y análisis para tomar decisiones, hemos procurado diseñar un modelo, para la resolución del problema del taller, que tenga inclui dos todos los criterios citados anteriormente. II) PROBLEMA DEL TALLER: ENUNCIADO.- (4 a 9) También denominado “problema de secuencias”, “machine se quencing” o “Job shop scheduling”. El problema del taller investiga una secuencia óptima (o en su de fecto lo más próxima posible) para procesar “n” artículos en “m” má quinas, siendo el óptimo aquella secuencia que minimiza el tiempo to tal de ejecución (tiempo necesario para realizar todas las operaciones (10) que comportan los artículos). Respetando las siguientes condiciones: A) Relativas a las máquinas: 1o) Podemos elegir libremente la secuencia de operaciones en cada máquina. 2o) Ninguna máquina puede realizar dos tareas simultáneamen te. B) Relativas a ios artículos: 3o) Las operaciones requeridas por un artículo tienen que ser realizadas en unas máquinas específicas. 4o) Las operaciones son realizadas en un orden técnicamente prescrito. 5o) Hay operaciones que pueden realizarse consecutivamente; otras, sin embargo, tienen que realizarse necesariamente de una manera secuencial. 6o) Se usan tiempos determinísticos. 7o) El tiempo de proceso es independiente de la secuencia. 8o) Se asigna a cada operación un tiempo finito. Es decir, el tiempo necesario para que se realice la tarea y, para que ca da par de operaciones, que se deban ser efectuadas conse cutivamente, tengan un retraso mínimo entre el comienzo de la primera y de la segunda. 9o) Cada operación debe ser llevada a cabo antes de las tareas que le siguen. 58 C) Otras consideraciones: 10°) Los tiempos de transporte, inicio y final de actividad son considerados despreciables o bien parte del tiempo de trata miento. 11°) No existen cancelaciones. 12°) No se tiene en cuenta las averías de las máquinas y la fuer za humana se considera constante. Este problema se inserta, por lo tanto, dentro de la clase de pro blemas que constituyen el problema central del ordenamiento, una vez traducidas las restricciones disyuntivas en desigualdades de poten cial. El que no se produzcan o se den las condiciones mencionadas an teriormente, no impide la resolución del problema. Sin embargo, la complejidad del mismo aumenta en mayor o menor medida si no se respetan. Hay que tener en cuenta que para “m” máquinas y “n” artículos existen (n)m combinaciones. NOTAS: 1o) Un artículo para su terminación necesita, generalmente, ser procesado en todas las máquinas. En caso contrario, para estas situaciones crearemos una operación ficticia de dura ción “0”. 2o) Para los artículos hay una indiferencia en el orden de realiza ción de l'as tareas en cada máquina, (así por la máquina 1 deben pasar “n” artículos, pero puede hacerlo primeramente la operación correspondiente al primer artículo, al segundo o al enésimo; en segundo lugar, puede ejecutarse cualquiera de las n-1 tareas restantes, y así sucesivamente). Esta carac terística, nos muestra que el problema es altamente combi natorio. 3o) Problema combinatorio según N. Agin (11) es “aquel que se le atribuyen unos valores discretos númericos a cierto con junto finito de variables, de tal manera que satisfaga un con junto de restricciones y reduzca al mínimo la función objeti vo de dichas variables”. Los problemas de taller podemos clasificarlos, a su vez en dos ti pos distintos: TIPO I.- Los artículos se procesan en las máquinas en un orden co mún. Una vez fijado el orden de paso de los artículos en una máquina, ese mismo orden se sigue para las restantes máquinas. TIPO II.- Cada artículo tiene un orden diferente de paso por las má quinas. Este orden viene especificado por el problema. 59 Ill) METODOS DE RESOLUCION Debido a la extraordinaria complejidad del problema, una solu ción obtenida mediante una técnica que nos oriente hacia una secuen cia óptima o próxima ai óptimo sin tener que probar la totalidad o la mayoría de tales soluciones tiene un valor considerable. Existen para este problema tres tipos de métodos: A) METODOS DE SIMULACION.- Estos métodos se utilizan co mo un instrumento auxiliar en la resolución de problemas de naturaleza combinatorio. Así, Kauffmann (12) señala que “cuando no se conoce un algoritmo (13) de optimización, o falta un método heurístico aceptable para mejorar una solu ción inicial se puede utilizar un método de simulación”. La simulación fué la primera vía por la que se intentó la resolución del problema del taller. Su validez es discutible, y la aparición de otros métodos más refinados postergaron su empleo en la resolución del problema que nos ocupa. B) METODOS HEURISTICOS.- Estos métodos se utilizan cuando no se conoce ningún algoritmo de optimización, y existe la necesidad práctica de encontrar una solución bien situada en relación al óptimo (que evidentemente no se conoce). Se parte de una solución factible (la que satisface las restriccio nes) y se va mejorando mediante el método, sin tener la se guridad de que se converge hacia el subconjunto de solucio nes óptimas (14). Este concepto de Kauffmann puede ser complementado con el de Battersby (15): “tales métodos se utilizan cuando no se puede obtener la mejor solución por no conocerse un método analítico adecuado o si se conoce por no ser técni camente realizable”. A nuestro juicio la mejor definición de método heurístico la encontramos en Kauffmann (16): Se trata de un método que no se puede aceptar del todo rigurosamente, pero que proporciona resultados suficientes para la práctica. C) METODOS DE OPTIMIZACION.- Con estos métodos, se intenta conseguir una economía relativa, es decir, que la proximidad del ópti mo alcanzada nos reporte un mayor beneficio que el coste utilizado pa ra dicho fin. Los métodos de optimización consisten, según Kauffmann (17), en separar el conjunto de soluciones en dos partes, una de las cuales contiene con toda seguridad el subconjunto de soluciones óptimas y la otra no, con lo cual se va pasando de unos subconjuntos a otros me nores hasta obtener mediante este cribado el subconjunto óptimo. Se puede operar también siguiendo el procedimiento de descomposición imponiendo solamente que en la parte seleccionada haya con toda se guridad alguna (o algunas) solución óptima, pero pudiendo haber algu nas, también, en la parte desechada; de esta forma, al final no se ten drá, tal vez, el’ subconjunto óptimo entero, pero si algunos de sus ele mentos que es lo que habitualmente se busca. 60 Las soluciones mas relevantes por cada método de resolución y para los diferentes tipos se relacionan a continuación (18): METODO TIPO I TIPO II -Á) SIMULACION Ramboz (19) Rowe-Jachson (20) B) HEURISTICOS Johnson (21) Palmer (22) C) OPTIMOS Lomnichi (23) Ignall-Schrage (24) Bowman (25) Manne (26) Greenberg (27) IV) PROCEDIMIENTO PROPUESTO PARA LA RESOLUCION DEL PRO BLEMA DE TALLER DEL TIPO II. Es un procedimiento heurístico consistente en la construcción de una arborescencia. Para su elaboración nos apoyaremos en resultados obtenidos mediante la realización de un conjunto de diagramas de Gantt. Estos diagramas estarán compuestos por un número de barras igual al número de artículos considerados en el problema. Cada barra llevará marcado el tiempo empleado en las sucesivas máquinas por el artículo y, por supuesto, en el orden de ejecución tecnológicamente prescrito por el problema. ALGORITMO.- Consta de tres fases: A) COMIENZO.- Sumamos las duraciones de las tareas corres pondientes a cada artículo. El valor mas alto obtenido lo asignamos al nudo inicial que constituye la cota raiz de la arborescencia. B) DESARROLLO.- Una restricción disyuntiva implica dos alter nativas: que un trabajo preceda a otro en una máquina ó, ca so contrario, sea continuación del mismo. La solución del problema del taller se consigue con la eliminación de las restricciones disyuntivas y su conservación en desigualda des de potencial. La conversión se puede hacer de dos for mas: 1. °) Empíricamente, previo examen detenido del problema, pode mos elegir una de las alternativas que indica una restricción disyuntiva sin tener que probar cual de las dos es la mejor. Representamos el problema en un diagrama de barras que contempla esta restricción. El valor de tiempo resultante en el gráfico constituye la cota de una rama descendente desde el nudo previo. Cuando la elección en base al exámen del problema no es clara, procederemos a realizarla a través de la segunda for ma. 2. °) A partir del nudo de cota menor hacemos dos ramas descen dentes. Cada rama representa una alternativa de una restric ción disyuntiva. Procedemos a su representacióh y obten ción de cotas. 61 Repetimos iterativamente este apartado B) hasta que al cancemos el final del problema (apartado C). C) FINAL.- La solución del problema se habrá alcanzado cuan do lleguemos a un nudo que represente una solución facti ble (todas las restricciones disyuntivas han sido transforma das en desigualdades de potencial) y el valor de la cota co rrespondiente, sea la menor de la arborescencia. En el anexo I presentamos un caso ilustrativo. V) CONSIDERACIONES. Respecto al procedimiento aquí descrito conviene establecer las siguientes puntualizaciones: a) Solo es válido para problemas de dimensión reducida. b) Para el desarrollo del procedimiento y obtención de una so lución satisfactoria, juega un papel fundamental la intuición y experiencia en la resolución de problemas de este tipo. No recomendamos su utilización en aquellas personas no versa das y no conocedoras del problema. c) Es fácil comprender que el deshacer empíricamente una res tricción disyuntiva ocasionará, si la decisión adoptada es errónea, una solución más o menos alejada del óptimo, se gún sea la trascendencia de dicha decisión. d) Las decisiones empíricas, indudablemente, reducen en gran medida la complejidad del problema, su predominio está en relación directa con la dimensión del problema a resolver. ANEXO 1.- CASO ILUSTRATIVO. Tres artículos deben ser procesados en máquinas. El artículo 1 de be ser procesado primero en la máquina 3 y posteriormente en la 2. El artículo 2 debe, en primer lugar, ser tratado en la máquina 2 y a conti nuación en la 1. El artículo 3 sigue en las máquinas el siguiente orden: máquina una-tres-dos. Los tiempos de realización se dan en el siguiente cuadro. ARTICULOS MAQUINA 1 MARQUINA 2 MAQUINA 3 1308 2730 3543 62 A) COMIENZO.- Artículo 1 ” 2 RAIZ B) DESARROLLO MAQUINA 1 a) Artículo 1 y 2 antes que el 3. Artículo 1 ” 2 ” 3 63 b) Artículo 1 antes que artículo 2. c) Artículo 2 antes que el artículo 1. i ------------- 1 ------------- 1 ------------- 1 ------------- 1 0 5 10 15 20 A1 antes MAQUINA 2 Artículo 2 antes artículo 3 A1 antes A3 A2 ” A3 A2 antes A1 A3 antes A3 MAQUINA 1 MAQUINA 2 64 MAQUINA 3.- Artículo 1 antes que artículo 3. Artículo 1 M3 M1 M2 M1 M1 M3 M2 10 15 MAQUINA 1 MAQUINA 2 MAQUINA 3 SOLUCION: Orden de paso de los artículos por las máquinas. Máquina 1.- Artículo 3-2-1 Máquina 2.- ” 2-3 Máquina 3.- ” 1-3 ■¿S E B E .65