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

En ique C. DIEZ DE CASTRO Uni e sidad H ispalense UN PROCEDIMIENTO HEURISTICO PARA LA RESOLUCION DEL PROBLEMA DEL TALLER El p oblema del alle como odos los p oblemas de secuencia- ción son de g an complejidad. Los p ocedimien os de esolución no son áciles de aplica . Po ello p esen amos un p ocedimien o sencillo que pe mi a sal a los incon enien es an e io es. I) INTRODUCCION De los cinco p ocesos básicos que componen la adminis ación (Plani icación, O ganización, di ección, do ación de Pe sonal y con ol), el más impo an e, p ima io y que p e alece sob e los demás es el de plani icación. Todo p oceso plani icado implica la cons i ución de una se ie de líneas posibles de acción y la selección o elección de una de ellas, es deci , compo a una oma de decisiones. Pa a e ec ua la elección en e las di e en es al e na i as posee mos es c i e ios álidos (1): a) LA EXPERIMENTACION.- Consis e en p oba las di e en es al e na i as seleccionando aquella que nos p opo cione me jo es esul ados. Sin emba go, al como a i ma Newman (2) la écnica expe imen al debe ía se u ilizada como un úl imo ins umen o una ez que se hayan p obado o as écnicas de plani ica ción. b) LA EXPERIENCIA.- Es un ac o muy impo an e que combi nado con la in uición puede consegui esul ados muy sa is ac o ios. c) INVESTIGACION Y ANALISIS.- Es el c i e io más e ec i o y usado pa a selecciona al e na i as. Una de las ap oximacio nes mas comple as de in es igación y análisis en la oma de decisiones la cons i uye la in es igación Ope a i a, ambién denominada análisis ope acional o “Ciencia de la Adminis ación”. 57 No obs an e, la In es igación Ope a i a a la ho a de oma decisiones no pasa de se una ecomendación, una ayuda pa a que el esponsable de la oma de decisiones pueda es coge un camino mejo que le lle e a alcanza los obje i os de la emp esa (3). Conscien es de la g an impo ancia que ep esen an los c i e ios empí icos, in ui i os y de in es igación y análisis pa a oma decisiones, hemos p ocu ado diseña un modelo, pa a la esolución del p oblema del alle , que enga inclui dos odos los c i e ios ci ados an e io men e. II) PROBLEMA DEL TALLER: ENUNCIADO.- (4 a 9) También denominado “p oblema de secuencias”, “machine se quencing” o “Job shop scheduling”. El p oblema del alle in es iga una secuencia óp ima (o en su de ec o lo más p óxima posible) pa a p ocesa “n” a ículos en “m” má quinas, siendo el óp imo aquella secuencia que minimiza el iempo o al de ejecución ( iempo necesa io pa a ealiza odas las ope aciones (10) que compo an los a ículos). Respe ando las siguien es condiciones: A) Rela i as a las máquinas: 1o) Podemos elegi lib emen e la secuencia de ope aciones en cada máquina. 2o) Ninguna máquina puede ealiza dos a eas simul áneamen e. B) Rela i as a ios a ículos: 3o) Las ope aciones eque idas po un a ículo ienen que se ealizadas en unas máquinas especí icas. 4o) Las ope aciones son ealizadas en un o den écnicamen e p esc i o. 5o) Hay ope aciones que pueden ealiza se consecu i amen e; o as, sin emba go, ienen que ealiza se necesa iamen e de una mane a secuencial. 6o) Se usan iempos de e minís icos. 7o) El iempo de p oceso es independien e de la secuencia. 8o) Se asigna a cada ope ación un iempo ini o. Es deci , el iempo necesa io pa a que se ealice la a ea y, pa a que ca da pa de ope aciones, que se deban se e ec uadas conse cu i amen e, engan un e aso mínimo en e el comienzo de la p ime a y de la segunda. 9o) Cada ope ación debe se lle ada a cabo an es de las a eas que le siguen. 58 C) O as conside aciones: 10°) Los iempos de anspo e, inicio y inal de ac i idad son conside ados desp eciables o bien pa e del iempo de a a mien o. 11°) No exis en cancelaciones. 12°) No se iene en cuen a las a e ías de las máquinas y la ue  za humana se conside a cons an e. Es e p oblema se inse a, po lo an o, den o de la clase de p o blemas que cons i uyen el p oblema cen al del o denamien o, una ez aducidas las es icciones disyun i as en desigualdades de po en cial. El que no se p oduzcan o se den las condiciones mencionadas an e io men e, no impide la esolución del p oblema. Sin emba go, la complejidad del mismo aumen a en mayo o meno medida si no se espe an. Hay que ene en cuen a que pa a “m” máquinas y “n” a ículos exis en (n)m combinaciones. NOTAS: 1o) Un a ículo pa a su e minación necesi a, gene almen e, se p ocesado en odas las máquinas. En caso con a io, pa a es as si uaciones c ea emos una ope ación ic icia de du a ción “0”. 2o) Pa a los a ículos hay una indi e encia en el o den de ealiza ción de l'as a eas en cada máquina, (así po la máquina 1 deben pasa “n” a ículos, pe o puede hace lo p ime amen e la ope ación co espondien e al p ime a ículo, al segundo o al enésimo; en segundo luga , puede ejecu a se cualquie a de las n-1 a eas es an es, y así sucesi amen e). Es a ca ac e ís ica, nos mues a que el p oblema es al amen e combi na o io. 3o) P oblema combina o io según N. Agin (11) es “aquel que se le a ibuyen unos alo es disc e os núme icos a cie o con jun o ini o de a iables, de al mane a que sa is aga un con jun o de es icciones y eduzca al mínimo la unción obje i o de dichas a iables”. Los p oblemas de alle podemos clasi ica los, a su ez en dos i pos dis in os: TIPO I.- Los a ículos se p ocesan en las máquinas en un o den co mún. Una ez ijado el o den de paso de los a ículos en una máquina, ese mismo o den se sigue pa a las es an es máquinas. TIPO II.- Cada a ículo iene un o den di e en e de paso po las má quinas. Es e o den iene especi icado po el p oblema. 59 Ill) METODOS DE RESOLUCION Debido a la ex ao dina ia complejidad del p oblema, una solu ción ob enida median e una écnica que nos o ien e hacia una secuen cia óp ima o p óxima ai óp imo sin ene que p oba la o alidad o la mayo ía de ales soluciones iene un alo conside able. Exis en pa a es e p oblema es ipos de mé odos: A) METODOS DE SIMULACION.- Es os mé odos se u ilizan co mo un ins umen o auxilia en la esolución de p oblemas de na u aleza combina o io. Así, Kau mann (12) señala que “cuando no se conoce un algo i mo (13) de op imización, o al a un mé odo heu ís ico acep able pa a mejo a una solu ción inicial se puede u iliza un mé odo de simulación”. La simulación ué la p ime a ía po la que se in en ó la esolución del p oblema del alle . Su alidez es discu ible, y la apa ición de o os mé odos más e inados pos e ga on su empleo en la esolución del p oblema que nos ocupa. B) METODOS HEURISTICOS.- Es os mé odos se u ilizan cuando no se conoce ningún algo i mo de op imización, y exis e la necesidad p ác ica de encon a una solución bien si uada en elación al óp imo (que e iden emen e no se conoce). Se pa e de una solución ac ible (la que sa is ace las es iccio nes) y se a mejo ando median e el mé odo, sin ene la se gu idad de que se con e ge hacia el subconjun o de solucio nes óp imas (14). Es e concep o de Kau mann puede se complemen ado con el de Ba e sby (15): “ ales mé odos se u ilizan cuando no se puede ob ene la mejo solución po no conoce se un mé odo analí ico adecuado o si se conoce po no se écni camen e ealizable”. A nues o juicio la mejo de inición de mé odo heu ís ico la encon amos en Kau mann (16): Se a a de un mé odo que no se puede acep a del odo igu osamen e, pe o que p opo ciona esul ados su icien es pa a la p ác ica. C) METODOS DE OPTIMIZACION.- Con es os mé odos, se in en a consegui una economía ela i a, es deci , que la p oximidad del óp i mo alcanzada nos epo e un mayo bene icio que el cos e u ilizado pa a dicho in. Los mé odos de op imización consis en, según Kau mann (17), en sepa a el conjun o de soluciones en dos pa es, una de las cuales con iene con oda segu idad el subconjun o de soluciones óp imas y la o a no, con lo cual se a pasando de unos subconjun os a o os me no es has a ob ene median e es e c ibado el subconjun o óp imo. Se puede ope a ambién siguiendo el p ocedimien o de descomposición imponiendo solamen e que en la pa e seleccionada haya con oda se gu idad alguna (o algunas) solución óp ima, pe o pudiendo habe algu nas, ambién, en la pa e desechada; de es a o ma, al inal no se en d á, al ez, el’ subconjun o óp imo en e o, pe o si algunos de sus ele men os que es lo que habi ualmen e se busca. 60 Las soluciones mas ele an es po cada mé odo de esolución y pa a los di e en es ipos se elacionan a con inuación (18): METODO TIPO I TIPO II -Á) SIMULACION Ramboz (19) Rowe-Jachson (20) B) HEURISTICOS Johnson (21) Palme (22) C) OPTIMOS Lomnichi (23) Ignall-Sch age (24) Bowman (25) Manne (26) G eenbe g (27) IV) PROCEDIMIENTO PROPUESTO PARA LA RESOLUCION DEL PRO BLEMA DE TALLER DEL TIPO II. Es un p ocedimien o heu ís ico consis en e en la cons ucción de una a bo escencia. Pa a su elabo ación nos apoya emos en esul ados ob enidos median e la ealización de un conjun o de diag amas de Gan . Es os diag amas es a án compues os po un núme o de ba as igual al núme o de a ículos conside ados en el p oblema. Cada ba a lle a á ma cado el iempo empleado en las sucesi as máquinas po el a ículo y, po supues o, en el o den de ejecución ecnológicamen e p esc i o po el p oblema. ALGORITMO.- Cons a de es ases: A) COMIENZO.- Sumamos las du aciones de las a eas co es pondien es a cada a ículo. El alo mas al o ob enido lo asignamos al nudo inicial que cons i uye la co a aiz de la a bo escencia. B) DESARROLLO.- Una es icción disyun i a implica dos al e  na i as: que un abajo p eceda a o o en una máquina ó, ca so con a io, sea con inuación del mismo. La solución del p oblema del alle se consigue con la eliminación de las es icciones disyun i as y su conse ación en desigualda des de po encial. La con e sión se puede hace de dos o  mas: 1. °) Empí icamen e, p e io examen de enido del p oblema, pode mos elegi una de las al e na i as que indica una es icción disyun i a sin ene que p oba cual de las dos es la mejo . Rep esen amos el p oblema en un diag ama de ba as que con empla es a es icción. El alo de iempo esul an e en el g á ico cons i uye la co a de una ama descenden e desde el nudo p e io. Cuando la elección en base al exámen del p oblema no es cla a, p ocede emos a ealiza la a a és de la segunda o  ma. 2. °) A pa i del nudo de co a meno hacemos dos amas descen den es. Cada ama ep esen a una al e na i a de una es ic ción disyun i a. P ocedemos a su ep esen acióh y ob en ción de co as. 61 Repe imos i e a i amen e es e apa ado B) has a que al cancemos el inal del p oblema (apa ado C). C) FINAL.- La solución del p oblema se hab á alcanzado cuan do lleguemos a un nudo que ep esen e una solución ac i ble ( odas las es icciones disyun i as han sido ans o ma das en desigualdades de po encial) y el alo de la co a co espondien e, sea la meno de la a bo escencia. En el anexo I p esen amos un caso ilus a i o. V) CONSIDERACIONES. Respec o al p ocedimien o aquí desc i o con iene es ablece las siguien es pun ualizaciones: a) Solo es álido pa a p oblemas de dimensión educida. b) Pa a el desa ollo del p ocedimien o y ob ención de una so lución sa is ac o ia, juega un papel undamen al la in uición y expe iencia en la esolución de p oblemas de es e ipo. No ecomendamos su u ilización en aquellas pe sonas no e sa das y no conocedo as del p oblema. c) Es ácil comp ende que el deshace empí icamen e una es icción disyun i a ocasiona á, si la decisión adop ada es e ónea, una solución más o menos alejada del óp imo, se gún sea la ascendencia de dicha decisión. d) Las decisiones empí icas, indudablemen e, educen en g an medida la complejidad del p oblema, su p edominio es á en elación di ec a con la dimensión del p oblema a esol e . ANEXO 1.- CASO ILUSTRATIVO. T es a ículos deben se p ocesados en máquinas. El a ículo 1 de be se p ocesado p ime o en la máquina 3 y pos e io men e en la 2. El a ículo 2 debe, en p ime luga , se a ado en la máquina 2 y a con i nuación en la 1. El a ículo 3 sigue en las máquinas el siguien e o den: máquina una- es-dos. Los iempos de ealización se dan en el siguien e cuad o. ARTICULOS MAQUINA 1 MARQUINA 2 MAQUINA 3 1308 2730 3543 62 A) COMIENZO.- A ículo 1 ” 2 RAIZ B) DESARROLLO MAQUINA 1 a) A ículo 1 y 2 an es que el 3. A ículo 1 ” 2 ” 3 63 b) A ículo 1 an es que a ículo 2. c) A ículo 2 an es que el a ículo 1. i ------------- 1 ------------- 1 ------------- 1 ------------- 1 0 5 10 15 20 A1 an es MAQUINA 2 A ículo 2 an es a ículo 3 A1 an es A3 A2 ” A3 A2 an es A1 A3 an es A3 MAQUINA 1 MAQUINA 2 64 MAQUINA 3.- A ículo 1 an es que a ículo 3. A ículo 1 M3 M1 M2 M1 M1 M3 M2 10 15 MAQUINA 1 MAQUINA 2 MAQUINA 3 SOLUCION: O den de paso de los a ículos po las máquinas. Máquina 1.- A ículo 3-2-1 Máquina 2.- ” 2-3 Máquina 3.- ” 1-3 ■¿S E B E .65