Un modelo CSP para la planificación de la sustitución óptima de piezas defectuosas

In eligencia A i icial, Re is a Ibe oame icana de In eligencia A i icial. No.17 (O oño 2002), pp. 83-92. ISSN: 1137-3601. © AEPIA (h p://www.aepia.o g/). Un modelo CSP pa a la plani icación de la sus i ución óp ima de piezas de ec uosas Ca melo Del Valle, Ra ael M. Gasca, Juan A. O ega, Ma ía T. Gómez Dep o. Lenguajes y Sis emas In o má icos Uni e sidad de Se illa A da. Reina Me cedes, s/n Se illa, 41012 {ca melo,gasca,o ega,may e}@lsi.us.es Resumen La aplicación de mé odos de diagnosis basada en modelos pe mi e ob ene los posibles componen es in oluc ados en el compo amien o anómalo del sis ema de es udio. T as la diagnosis, el obje i o es es ablece el uncionamien o deseado median e la epa ación o sus i ución de ales componen es. En sis emas complejos pueden exis i muy di e sas o mas de ealiza dicho p oceso, y esul a de in e és hace lo de mane a óp ima. En es e abajo se p esen a un modelo CSP (P oblema de Sa is acción de Res icciones) pa a el secuenciamien o óp imo de a eas en la sus i ución de piezas de ec uosas cuando se suponen únicamen e allos simples. Pa a ello, se pa e de un modelo pa a la selección de secuencias óp imas de ensamblaje en sis emas con múl iples máquinas. Pa a es e úl imo modelo, el obje i o del plan esul an e es la minimización del iempo o al del ensamblaje, y pa a el an e io , del p oceso global de epa ación. Pa a ello, el modelo conside a, además de las du aciones y los ecu sos u ilizados po las a eas, los iempos necesa ios pa a el cambio de con igu ación (he amien as) en las máquinas de ensamblaje, y los e a dos asociados al anspo e de submon ajes in e medios en e dis in as máquinas. El p oblema puede se isualizado median e un g a o And/O , que incluye el conjun o de odos los planes de mon aje ac ibles pa a un p oduc o. Es a ep esen ación ecoge po un lado las es icciones de p ecedencia en e a eas, y po o o las elaciones en e las a eas pa a compone un plan co ec o. En el p esen e abajo se u iliza una ex ensión de es a ep esen ación que incluye odas las es icciones que apa ecen en el p oblema, añadiéndose aquellas asociadas al uso de ecu sos. A pa i de la ep esen ación an e io , se p oponen sendos modelos CSP que ecogen el conjun o de odas las es icciones del p oblema del ensamblado del p oduc o comple o y del p oblema de la sus i ución de una pieza de ec uosa. Palab as cla e: Plani icación y Scheduling, Sa is acción de Res icciones, Diagnosis, Recupe ación de Fallos, Ensamblado y Desensamblado. 1. In oducción La aplicación de mé odos de diagnosis basada en modelos [DeKlee 87] [Rei e 87] pe mi e ob ene el mínimo núme o de componen es in oluc ados en el compo amien o anómalo del sis ema obse ado. T as la diagnosis, el obje i o es es ablece el uncionamien o deseado median e la epa ación o sus i ución de ales componen es. En sis emas complejos, compues os po un núme o ele ado de componen es, y con acceso limi ado a muchos de ellos, pueden exis i muy di e sas o mas de ealiza dicho p oceso, y esul a de in e és hace lo de mane a óp ima. Se a a pues de plani ica el secuenciamien o óp imo de las a eas que lo lle en a cabo. En e dichas a eas se encuen an las del desensamblado y ensamblado del p oduc o. Los p oblemas de secuenciamien o ep esen an una clase de p oblemas especialmen e di íciles de esol e . Muchos de ellos han sido es udiados ampliamen e median e el uso de écnicas de sa is acción de es icciones, como el p oblema de Job Shop Scheduling [Caseau95] [Esqui ol96]. En es e abajo se plan ea po un lado un modelo CSP (P oblema de Sa is acción de Res icciones) pa a la selección de secuencias de ensamblaje. Es e p oblema supone un mayo g ado de complejidad, ya que se añade a la de e minación del o den y los iempos de las a eas, la p opia selección de las mismas den o de un conjun o de planes al e na i os. Es a p oblemá ica ha sido poco es udiada, po lo que es de especial in e és el desa ollo de écnicas de búsqueda CSP que la con emplen [Beck00]. Po o o lado, cuando se ob ienen los esul ados de aplica los mé odos de diagnosis basada en modelos a los sis emas con múl iples piezas, nos en en amos a la du a a ea de ealiza el desensamblado óp imo del sis ema has a encon a la pieza esul an e del p oceso de diagnosis, suponiendo que sólo se a iende a allos simples, es deci , asociados a una sola pieza o bloque. La Figu a 1 mues a un esquema del p oceso global, en el que los esul ados ob enidos en la diagnosis se in oducen en el plani icado , que debe á de e mina la secuencia adecuada de ope aciones pa a ex ae la pieza de ec uosa, la p opia sus i ución o epa ación de la misma y el pos e io eensamblado del sis ema. Ex acción de pieza de ec uosa Diagnosis Sus i ución/ epa ación de la pieza de ec uosa Reensamblado del p oduc o Modelo CSP Figu a 1. Esquema del p oceso diagnosis/ epa ación. Es e p oblema ha sido a ado poco en la bibliog a ía y es el obje i o p incipal de es e abajo. Ello se lle a á a cabo median e el modelado de dicho p oblema median e un p oblema de sa is acción de es icciones que conside a además de los ecu sos u ilizados en las a eas, las du aciones de las mismas. La esolución del mismo puede ealiza se median e he amien as de p og amación con es icciones. El modelo de plani icado p opues o conside a á que la diagnosis p opo ciona la de ección de un allo simple. El es o del a ículo se es uc u a de la siguien e mane a: en la sección 2 se desc ibe el p oblema de la selección de secuencias de ensamblaje, y en la sección 3 se de alla el modelo de plani icación p opues o. En la sección 4 se es ablece el modelo CSP pa a el p oblema de plani icación co espondien e al ensamblaje comple o de un p oduc o a pa i de las piezas sepa adas, haciendo especial hincapié en la dis inción de la selección de a eas al e na i as. La sección 5 mues a el modelo CSP pa a la sus i ución o epa ación de una pieza de ec uosa, de ec ada median e un p oceso de diagnosis basada en modelos. Po úl imo, en la sección 6 se indican las conclusiones y se azan las líneas de abajo u u o a desa olla a pa i del modelo p opues o. 2. Selección de secuencias de ensamblaje La plani icación del ensamblaje es un p oblema de especial in e és en la ab icación de p oduc os. En él se con emplan la iden i icación, selección y secuenciamien o de ope aciones de ensamblaje, conside adas desde el pun o de is a de su e ec o sob e las piezas a ensambla . La iden i icación de las a eas de ensamblaje se abo da median e el análisis de la es uc u a del p oduc o, u ilizando un sis ema expe o in e ac i o [Bou jaul 84] [DeFazio87], o de o ma au omá ica a pa i de modelos geomé icos y elacionales [Homem91] y de modelos CAD y o as in o maciones de ipo no geomé ico [Romney95] [Cal on99]. La iden i icación de las ope aciones de ensamblaje conduce no malmen e al conjun o de odos los planes de ensamblaje ac ibles. El núme o de ellos c ece exponencialmen e con el núme o de piezas, y depende de o os ac o es, ales como la o ma en que las piezas es án in e conec adas en el ensamblaje comple o, ep esen ado a a és del g a o de conexiones. De hecho, es e p oblema ha sido p obado como NP-comple o [Wilson95]. La siguien e conside ación es la ob ención de un plan de mon aje óp imo, seleccionado del conjun o de odos los planes de ensamblaje ac ibles. En la mayo ía de los casos, el obje i o es minimiza la apa ición de elemen os p oblemá icos pa a la ejecución del ensamblaje, como mo imien os complicados o ines ables, y a eas no p oduc i as, como cambios de disposi i os de ijación y eo ien ación de piezas. En [Goldwasse 99] se indica un amplio conjun o de c i e ios de selección. Se han usado g a os And/O pa a la ep esen ación del conjun o de odos los planes de ensamblaje ac ibles [Homem90]. En al ep esen ación, los nodos O se co esponden con submon ajes, siendo el nodo aíz el que hace e e encia al p oduc o comple o, y los nodos hoja a las piezas indi iduales. Cada nodo And se co esponde con la a ea de mon aje que une los submon ajes de sus nodos hijos p oduciendo el submon aje de su nodo pad e. Un á bol de ensamblaje es un camino del g a o And/O que comienza en el nodo aíz y e mina en los nodos hoja, y ep esen a un plan de mon aje, que ecoge las es icciones de p ecedencia en e las a eas que lo o man. Una secuencia de mon aje es una secuencia o denada de a eas de mon aje, que sa is ace las es icciones de o den de a eas. Cada plan de mon aje se co esponde con una o más secuencias de mon aje. Una impo an e en aja de es a ep esen ación, usada en es e abajo, es que el g a o And/O mues a la independencia de las a eas de ensamblaje que pueden ejecu a se en pa alelo. La Figu a 2 ilus a un ejemplo de es a ep esen ación. A B C D E A B C D A B T1T2 T3T4 T5T6 A C D A C A D C D B E T11 T9T10 T8 T7 A B C D E Figu a 2. G a o And/O pa a el ensamblaje del p oduc o ABCDE. 3. Modelo de plani icación p opues o El p oblema plan eado es la selección de un plan de mon aje, es deci , uno de los á boles que componen el g a o And/O , y el secuenciamien o de las a eas que lo componen. El c i e io seguido en es e abajo es la minimización del iempo o al del ensamblaje en un sis ema con a ias máquinas de ensamblaje [DelValle96], po lo que se han conside ado odos aquellos ac o es que pueden in lui en al medida. Pa a ello, se pa e de una es imación p e ia de los ecu sos necesa ios (máquina y he amien a) y du ación ap oximada de cada una de las a eas de mon aje. El modelo conside a una única combinación du ación-máquina-he amien a pa a cada a ea de mon aje. Sin emba go, puede se ex endido sin di icul ad cuando se engan a ias opciones pa a la cons ucción de un submon aje a pa i del mismo g upo de componen es: bas a con supone que cada opción se co esponde con una a ea de mon aje di e en e, lo que signi ica ía la adición de nodos And en el g a o And/O en e los mismos nodos O . O o ac o que ha sido conside ado es el iempo necesa io pa a el cambio de he amien as en las máquinas, que suele se del mismo o den que las p opias du aciones de las a eas de mon aje, po lo que no deben desp ecia se. ∆ch (M, H, H') deno a á el iempo necesa io pa a ins ala en la máquina M la he amien a H' si p e iamen e es aba ins alada la he amien a H. Debe obse a se que cualquie cambio de con igu ación en las máquinas que deba ealiza se en e la ejecución de dos a eas puede modela se de es a o ma, aunque aquí se ha isualizado a a és del uso de he amien as. También se ienen en cuen a en el modelo los e a dos asociados al anspo e de piezas y submon ajes. El modelo p opues o supone un sis ema bien dimensionado en el que exis e un sis ema logís ico pe ec o, de o ma que cuando una pieza sea eque ida en una máquina pa a ealiza una ope ación de ensamblaje, es é p esen e allí. Lo mismo no puede asegu a se pa a un submon aje in e medio, ya que és e pod ía se ensamblado en una máquina e inmedia amen e se eque ido en o a dis in a pa a o ma o o submon aje. De es a o ma, deno a emos median e ∆mo (SA, M, M') al e a do asociado al anspo e del submon aje SA desde la máquina M hacia la máquina M'. O o pun o de in e és del modelo p opues o es que los esul ados que se de i an de él pueden se usados en dis in as e apas del p oceso de plani icación, desde el p opio diseño del p oduc o y del sis ema de ensamblaje has a su ejecución inal. Asimismo, como se mues a en el p esen e abajo, ambién es ácilmen e ex ensible pa a se usado en el man enimien o pos e io del p oduc o, median e a eas de sus i ución o epa ación de componen es de ec uosos, que hayan podido se de ec ados median e p ocesos de diagnosis. 4. El modelo CSP pa a el ensamblaje de un p oduc o La ep esen ación median e g a os And/O ecoge po un lado las es icciones de p ecedencia en e a eas, y po o o las elaciones en e las a eas pa a cons ui un plan co ec o. En el p esen e abajo se p opone una ex ensión de es a ep esen ación de o ma que se incluyan odas las es icciones que apa ecen en el p oblema, añadiéndose aquéllas asociadas al uso de ecu sos po las a eas. Po mo i os de mayo cla idad en la exposición, se mues a en p ime luga el modelo co espondien e al caso en que no hay planes al e na i os, pa a pasa a con inuación a o mula el modelo pa a el caso gene al. Cada nodo del g a o And/O end á una se ie de a iables asociadas o a ibu os. En la sección an e io se indica on aquellos que pueden conside a se como cons an es: pa a cada a ea T (nodo And), su du ación du (T), máquina donde se ejecu a y he amien a u ilizada en ella; pa a los submon ajes (nodos O ), los e a dos asociados a su anspo e en e cada dos máquinas. Apa e de ello, conside a emos pa a ambos ipos de nodos dis in as a iables empo ales: pa a cada a ea T, sus iempos de comienzo, i(T), y de inalización, (T); pa a cada submon aje SA, el iempo en que ue cons uido, OR(SA). 4.1. Modelo CSP sin a eas al e na i as En la Figu a 3 se mues a un g a o And/O donde sólo exis e un plan de mon aje, po lo que odos los nodos deben o ma pa e de la solución. El p oblema es de e mina los alo es de las a iables empo ales asociadas a ellos, de o ma simila a los p oblemas de scheduling disyun i o. También se indican en la misma igu a los dis in os ipos de es icciones que apa ecen en el p oblema. En la Tabla 1 se enume a el conjun o de odas las es icciones asociadas al g a o de la Figu a 3. El p ime ipo iden i ica los iempos de los nodos O con los de inalización de las a eas que los o man. El segundo ipo elaciona los iempos de comienzo y inalización de las a eas, conside ando la du ación de las mismas. Las es icciones del ipo (3) incluyen, apa e de la p ecedencia en e los iempos de inicio de los nodos And y los de los nodos O , los posibles e a dos asociados al anspo e de los submon ajes en e dis in as máquinas. A B C D E T2 T5 M1 H2 M2 H3 M1 H1 M2 H3 A C D A C B E T11 T8 A B C D E (1) (2) (3) (4) (5) Figu a 3. Ex ensión del g a o And/O pa a el p oduc o ABCDE con un solo plan de ensamblaje. Las es icciones del ipo (4) se co esponden con el e a do asociado al cambio de he amien as en e la ejecución de a eas con es icciones de p ecedencia. Nó ese que pa a cada a ea, sólo se á necesa io elaciona la con o a si uada más a iba en el g a o And/O , la más ce cana que u ilice la misma máquina. Cuando además u ilicen ambas la misma he amien a, la es icción esul an e es supe lua y puede se eliminada. Pa a ep esen a es e ipo de es icciones se ha añadido un nue o ipo de enlace en e nodos And en la Figu a 3. Po úl imo, las es icciones del ipo (5) exp esan los dos posibles ó denes de ejecución de cada pa de a eas, no elacionadas median e p ecedencia, que u ilizan una misma máquina, pudiendo conlle a ambién un cambio de he amien as. Pa a el ejemplo mos ado, se a a de que las a eas T5 y T11, que u ilizan ambas la máquina M2, no pueden ejecu a se simul áneamen e, es deci , la ejecución de T11 se ejecu a ía as la inalización de T5 o ice e sa, ob eniéndose la disyunción co espondien e. Pa a ep esen a es e ipo de es icciones ambién se ha añadido un nue o ipo de enlace en e nodos And en la Figu a 3. 4.2. Modelo CSP con a eas al e na i as En la Figu a 4 se mues a la ex ensión del g a o And/O en el caso gene al en el que pueden exis i dis in os planes de ensamblaje. Aho a, las dis in as a eas pueden apa ece en la solución inal o no, y el conjun o de a eas que pueden o ma una solución co ec a ienen ligadas en e sí de o ma que pe enezcan odas a un mismo á bol de ensamblaje. A su ez, el hecho de ejecu a unas a eas u o as implica que se o men unos submon ajes in e medios u o os. De es a o ma, a los a ibu os de los nodos se les añade una a iable booleana que indique si el nodo en cues ión es seleccionado como pa e de la solución, deno ándose como s(T) y s(SA) pa a una a ea gené ica T y un submon aje gené ico SA espec i amen e. Po o o lado, dado que un de e minado submon aje puede se o mado en dis in as máquinas, dependiendo de la a ea que se escoja pa a su mon aje, se á necesa io añadi un nue o a ibu o pa a los nodos O , deno ándose median e m(SA) a la máquina donde se ensambla el submon aje SA. Puede obse a se que los ipos de es icciones son simila es al modelo an e io , de o ma que se han usado los mismos elemen os en el g a o And/O ex endido pa a ep esen a los. Las o mas que ienen aho a las es icciones son más complejas, ya que inco po an oda la in o mación necesa ia a la selección de a eas (y submon ajes) al e na i as. En la Tabla 2 se mues a el conjun o de es icciones que de inen el p oblema asociado a la Figu a 4, y que se co esponde con el g a o And/O de la Figu a 2, en donde se han especi icado los ecu sos u ilizados po las dis in as a eas. A B C D E A B C D A B T1T2 T3T4 T5T6 M2 H4 M1 H2 M2 H4 M2 H3 M1 H1 M2 H3 M1 H2 M1 H1 M1 H2M2 H4 M2 H3 (1) (2) (3) (4) (5) ... A C D A C A D C D B E T11 T9T10 T8 T7 A B C D E Figu a 4. Ex ensión del g a o And/O pa a el p oduc o ABCDE. Las es icciones del ipo (1) elacionan la selección de las a eas con la de los submon ajes, exp esado a a és del ope ado OR exclusi o, dado que una y sólo una de las a eas que pueden o ma un submon aje de e minado puede se escogida, si dicho submon aje o ma pa e de la solución. A su ez, de inen las es icciones asociadas a los a ibu os (máquina y iempo de o mación) de los nodos O en elación con las a eas que pueden se escogidas. Un caso especial se da pa a el p oduc o comple o y pa a las piezas indi iduales, que siemp e o ma án pa e de la solución, po lo que las a iables booleanas s oman el alo ue. Nó ese que, po es a misma azón, la especi icación de OR Tipo Res icciones 2 ()() OR ABCDE T= 5 () () OR ACD T= 11 () () OR BE T= 8 () () OR AC T= (1) () () () () () 0 OR OR OR OR OR ABCD E ==== == 22 2 () () () i T T du T=+ 55 5 () () () i T T du T=+ 11 11 11 () () () i T T du T=+ (2) 88 8 () () () i T T du T=+ 221 () ( ) ( , , ) iOR mo ACD ACD T M M≥+∆ 221 () () (, , ) iOR mo BE BE T M M≥+∆ 512 () ( ) ( , , ) iOR mo AC AC T MM≥+∆ 5 () () iOR T D≥ 11 () () iOR T B≥ 11 () () iOR T E≥ 8 () () iOR T A≥ (3) 8 () () iOR T C≥ (4) 28 112 () () ( , , ) i ch T T M HH≥+∆ (5) 511 115 () () () () i i T T T T≥∨≥ () OR ABCDEminimiza Tabla 1. Conjun o de es icciones pa a el g a o And/O de la Figu a 3. Tipo Res icciones ( ) () () () () ()ABCDEABCDE s sssss ue====== () 12 ()() ()ABCDE s sT XORsT⇒ () 121 () () ()() OR ABCDE ABCDE s Tm M T⇒=∧ = () 212 () () ()() OR ABCDE ABCDE s Tm M T⇒=∧ = () () 34 34 ( ) () () ( ) () ()ABCD ABCDssTXORsTs sTsT⇒∧¬ ⇒¬∧¬ () 323 () () ()() OR ABCD ABCD s Tm M T⇒=∧ = () 414 () () ()() OR ABCD ABCD s Tm M T⇒=∧ = () () 56 56 () () () () () ()ACD ACD s sT XORsT s sT sT⇒∧¬ ⇒¬∧¬ () 525 () () () () OR ACD ACD s Tm M T⇒=∧ = () 616 () () () () OR ACD ACD s Tm M T⇒=∧ = () 72 7 7 () () () () () () () OR AB AB AB AB s sT m M T s sT⇒∧=∧ = ∧¬⇒¬ () 81 8 8 () () () () () () () OR AC AC AC ACssTmM T s sT⇒∧=∧ = ∧¬⇒¬ () 91 9 9 () () () () () () () OR AD AD AD AD s sT m M T s sT⇒∧=∧ = ∧¬⇒¬ () 10 2 10 10 () () () () () () () OR CD CD CD CD s sT m M T s sT⇒∧=∧ = ∧¬⇒¬ () 11 2 11 11 () () () () () () () OR BE BE BE BE s sT m M T s sT⇒∧=∧ = ∧¬⇒¬ (1) () () () () () 0 OR OR OR OR OR ABCDE ===== 111 1 () () () () i s T T T du T⇒=+ ! (2) 11 11 11 11 () () () () i s T T Tdu T⇒=+ () 11 2 () ( ) () ( ) ( ,( ), ) iOR mo ABCD ABCD ABCD ABCDsT s T m M⇒∧≥ +∆ 11 () () () iOR EsT T ⇒≥ () 22 1 () ( ) () ( ) ( ,( ), ) iOR mo ACD ACD ACD ACDsT s T m M⇒∧≥ +∆ () 22 21 () () () () (, , ) iOR mo BE BE BEsT s T M M⇒∧≥+∆ () 33 2 () () () () (() ) iOR AB AB AB s Ts T m M⇒∧≥ = () 33 2 () ( ) () ( ) (( ) ) iOR CD CD CD s Ts T m M⇒∧≥ = ! 11 11 () () () iOR BsT T ⇒≥ (3) 11 11 () () () iOR EsT T ⇒≥ () 51 1 5 234 () () () () ( , , ) i ch s TsT T T MHH∧⇒≥+∆ () 64 4 6 121 () () () () ( , , ) i ch s TsT T T MHH∧⇒≥+∆ () 73 3 7 234 () () () () ( , , ) i ch s TsT T T MHH∧⇒≥+∆ (4) () 82 2 8 112 () () () () ( , , ) i ch s TsT T T MHH∧⇒≥+∆ () () 511 5 11 11 5 () () () () () () i i s TsT T T T T∧⇒≥∨≥ (5) () ()() () 7 10 7 10 243 10 7 234 () () () () ( , , ) () () ( , , ) i ch i ch sT sT T T M H H T T M H H∧⇒≥+∆ ∨≥+∆ () OR ABCDEminimiza Tabla 2. Conjun o de es icciones pa a el g a o And/O de la Figu a 4. pa a las piezas indi iduales es más simple (igual a ce o). El es o de es icciones ambién ienen o ma de implicación, de mane a que en el consecuen e apa ecen las exp esiones del modelo an e io , y se usan como an eceden es las exp esiones booleanas que exp esan la selección de las a eas que apa ecen en el consecuen e. Las es icciones de ipo (3) elacionan además la selección de los submon ajes con la de las a eas que los u ilizan pa a o ma o o mayo . Es necesa io hace no a que pa a o ma las es icciones disyun i as, del ipo (5), es p eciso ene en cuen a, que sólo deben con empla se en e a eas que puedan o ma pa e de una misma solución, es deci , pe enecien es a un mismo á bol de ensamblaje, además de usa la misma máquina. Ello puede ealiza se ácilmen e a ando de empa eja , pa a cada nodo And del g a o And/O , cada a ea po debajo de uno de los nodos O hijos con cada una de las que es án po debajo del o o nodo O hijo. Puede obse a se cómo el ca ác e combina o io del p oblema iene dado po las es icciones de los ipos (1) y (5), co espondien es a la selección de a eas al e na i as y al uso exclusi o de ecu sos compa idos po a eas no elacionadas median e p ecedencia. 5. Modelo CSP pa a la sus i ución de una pieza de ec uosa El modelo cons uido en la sección an e io puede se ex endido con acilidad pa a abo da el p oblema de la sus i ución o epa ación de piezas de ec uosas. En es e abajo se supone que a pa i de un p oceso de diagnosis basada en modelos se de ec a un allo en una de las piezas del p oduc o. La epa ación del sis ema se ealiza a pa i de una secuencia de a eas, las p ime as de desmon aje pa a ex ae la pieza de ec uosa, a con inuación la epa ación o sus i ución de la misma y po úl imo las a eas necesa ias pa a ol e a ensambla el p oduc o comple o. El g a o And/O puede u iliza se pa a ep esen a an o el p oceso de mon aje como el opues o, el desensamblado. Pa a ello, puede supone se en p ime luga que pa a cada a ea de ensamblaje T, exis e su co espondien e de desmon aje, a la que deno a emos median e T', sin que la incluyamos explíci amen e en el g a o And/O , po mo i os de cla idad. Hay que ene en cuen a que no siemp e iene po qué se cie a esa suposición, de mane a que pueda se ac ible la a ea de uni dos submon ajes dados pa a ob ene el esul an e mien as que la opues a no sea posible ealiza la, o ice e sa. Sin emba go, bas a con asigna una du ación muy ele ada a la a ea no ac ible pa a que la suposición ealizada pueda se conside ada como álida. Pa a cada a ea de desmon aje T', se end án como da os los ecu sos a u iliza , máquina y he amien a, y su du ación es imada. Téngase en cuen a que no ienen po qué coincidi las máquinas y he amien as pa a las a eas de ensamblaje y desmon aje co espondien es al mismo nodo And, aunque lo no mal es que así sea, al menos pa a la máquina de ensamblaje. O a suposición que aquí se ha á es que si pa a ex ae la pieza de ec uosa se ealiza a a és de una secuencia dada de a eas de desmon aje, ob eniendo unos submon ajes in e medios de e minados, el p oceso de mon aje usa á las a eas equi alen es de ensamblaje, es deci , se usa án los mismos submon ajes ob enidos, sin que apa ezcan o os submon ajes dis in os. Además, odo submon aje que no con enga a la pieza de ec uosa se man end á comple o, es deci , sin desensambla . De lo an e io se desp ende que la solución buscada es una secuencia lineal de a eas, es deci , no se ejecu a án a eas en pa alelo. De es a o ma, no apa ece án en el modelo las es icciones disyun i as co espondien es al uso de ecu sos compa idos –del ipo (5) en el modelo de la sección an e io –. Apa e de las nue as a eas a conside a espec o al modelo de la sección an e io , hay o as a iables que apa ecen en el p oblema CSP. Pa a un submon aje dado SA, po un lado hay que dis ingui en e la máquina donde se cons uye, a la que segui emos deno ando median e m(SA), y la máquina donde queda as el desmon aje p oceden e de uno mayo , a la que deno a emos median e m'(SA). A su ez, ambién hab á que dis ingui pa a cada submon aje en e el iempo en que es cons uido, as la ejecución de la a ea de ensamblaje co espondien e, al que segui emos deno ando median e OR(SA), y el iempo en que se ob iene as la ejecución de una a ea de desmon aje, al que deno a emos median e 'OR(SA). Con las suposiciones an e io es, las a iables booleanas co espondien es a la selección de planes al e na i os pueden segui siendo usadas las mismas, de mane a que pa a los nodos And, s(T) indica á que la solución con iene an o a la a ea de ensamblaje T como a su co espondien e de desmon aje T'. Pa a el caso de los nodos O , el sen ido de la a iable s(SA) es más ob io, ya que supone la apa ición del submon aje SA en el p oceso comple o, no habiendo modi icación con espec o al modelo an e io . Un úl imo ac o in e iene en el p oblema, el co espondien e al iempo necesa io pa a la sus i ución o epa ación de la pieza de ec uosa, que se á deno ado median e ∆sus (P), siendo P la pieza en cues ión, y que supond emos independien e de la máquina en donde se ex aiga. Pa a la ob ención de la solución puede ealiza se una simpli icación del g a o And/O , en el sen ido de que no in e end án aquellos nodos And si uados po debajo de nodos O co espondien es a submon ajes que no con engan a la pieza de ec uosa. Es o puede ealiza se median e un eco ido en p o undidad del g a o. Aho a los nodos O hojas pueden co esponde se an o con piezas indi iduales como con submon ajes que no con ienen a la pieza de ec uosa. Todos esos nodos end án el mismo a amien o, a excepción del co espondien e a la pieza de ec uosa. La Figu a 5 mues a la simpli icación del g a o And/O esul an e pa a el p oduc o ABCDE u ilizado en los ejemplos an e io es, cuando la pieza a sus i ui es la D. En dicha simpli icación puede obse a se cómo no apa ecen algunos de los nodos And, conc e amen e los que es aban si uados po debajo de los nodos O que no con ienen a D. El hecho de que no haya desapa ecido ningún nodo O en el ejemplo se debe a la casuís ica del mismo: odos los submon ajes que no con ienen a D ienen a lo sumo dos piezas, y odas las piezas dis in as a D se pueden sepa a de algún submon aje que con iene a D, po lo que odas las hojas del g a o o iginal (piezas indi iduales) pe manecen en el g a o simpli icado. La Tabla 3 mues a las es icciones esul an es pa a el ejemplo de la Figu a 5. Po simplicidad se ha supues o en el mismo que las a eas de ensamblaje y de desmon aje co espondien es a un mismo nodo And u ilizan la misma máquina y la misma he amien a. De es a mane a, los submon ajes co espondien es a nodos O hojas pe manecen en la máquina co espondien e (o su en o no) has a se u ilizados de nue o en las a eas de mon aje. Puede obse a se po un lado, así como en la Figu a 5, que no apa ecen es icciones del ipo (5) co espondien es al modelo de la sección an e io , como se indicó p e iamen e. Po o o lado, las es icciones son algo más complicadas en gene al al in oluc a ambién las a eas de desmon aje. Así, las es icciones del ipo (1) en e un submon aje gené ico SA y una a ea T (y su equi alen e T') incluyen, apa e de lo ya indicado en la sección an e io , las elaciones en e 'OR y el iempo de inicio de T', en donde se conside a el posible anspo e del submon aje desde la máquina en que ue ob enido as el desmon aje hacia la máquina en donde se ejecu a T'. Un caso pa icula lo cons i uyen los nodos O hojas, pa a los cuales se es ablece la igualdad en e 'OR y OR, excep o pa a la pieza de ec uosa, pa a la que se conside a el posible e a do asociado a su epa ación o sus i ución. El o igen del iempo se es ablece pa a 'OR del p oduc o comple o, siendo el obje i o a minimiza su co espondien e OR. A B C D E A B C D A B T1T2 T3T4 T5T6 M2 H4 M1 H2 M2 H4 M1 H1 M2 H3 M1 H2 M1 H2M2 H4 (1) (2) (3) (4) ... A C D A C A D C D B E T9T10 A B C D E Figu a 5. Ex ensión del g a o And/O pa a la sus i ución de la pieza D en el p oduc o ABCDE. Las es icciones del ipo (2) incluyen ob iamen e las elaciones en e el iempo de comienzo y inalización de las a eas de desmon aje. Las es icciones del ipo (3) incluyen las elaciones en e 'OR y el iempo de inalización de las a eas de desmon aje, y pe mi e ob ene la a iable co espondien e a la máquina m' a a és de la a ea de desmon aje. Debido a las suposiciones ealizadas en cuan o al uso de la misma máquina y he amien a po las a eas de ensamblaje y desmon aje co espondien es al mismo nodo And, no apa ecen nue as es icciones del ipo (4) que in oluc en a o os nodos en el g a o And/O . Eso sí, las es icciones aho a ambién ienen en cuen a el e a do co espondien e en las a eas de desmon aje. Tipo Res icciones ()() ()0 OR ABCDE D ABCDEss ue ′ == ∧ = () 12 ()() ()ABCDE s sT XORsT⇒ () 1211 () () ()()()() OR i OR ABCDE ABCDE ABCDEsT m M T T ′′ ⇒=∧ = ∧ ≥ () 2122 () ( ) ( ) () () ( ) OR i OR ABCDE ABCDE ABCDEsT m M T T ′′ ⇒=∧ = ∧ ≥ () () 34 34 ( ) () () ( ) () ()ABCD ABCDssTXORsTs sTsT⇒∧¬ ⇒¬∧¬ () ( ) 3233 2 () ( ) ( ) () () ( ) , ( ), ) OR i OR mo ABCD ABCD ABCD ABCD ABCDsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () ( ) 4144 1 () () ()()() () ,(),) OR i OR mo ABCD ABCD ABCD ABCD ABCDsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () () 56 56 () () () () () ()ACD ACD s sT XORsT s sT sT⇒∧¬ ⇒¬∧¬ () () 5255 2 () () () ()() () ,(),) OR i OR mo ACD ACD ACD ACD ACDsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () () 6166 1 () ( ) ( ) () () ( ) , ( ), ) OR i OR mo ACD ACD ACD ACD ACDsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ 9 () ()AD s sT= () () 9199 1 () ( ) ( ) () () ( ) , ( ), OR i OR mo AD AD AD AD ADsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ 10 () ()CD s sT= () () 10 2 10 10 2 () () () () () () ,(), OR i OR mo CD CD CD CD CDsT m M T T m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () { } () () () () (), ,,,,,, OR OR AB AC BE A B C Es SA m SA m SA SA SA SA ′′ ⇒=∧ = ∈ (1) () () () () () () () OR OR sus DDDDDDsmm ′′ ⇒=∧ =+∆ ( ) 1111111 () () () () () () () i i s T T T du T T T du T ′′ ′ ⇒=+ ∧ =+ ! (2) () 10 10 10 10 10 10 10 () () () () () () () i i s T T T du T T T du T ′′ ′ ⇒=+ ∧ =+ ( ( 1211 2 () ()() ()()() () ,(), OR i OR mo ABCD ABCD ABCD ABCD ABCD ABCD s Ts m M T T m M ′′′ ⇒∧=∧=∧≥+∆ () 1211 () () () () () () () OR i OR E EE EsT s m M T T ′′′ ⇒∧=∧ =∧≥ () ( ) 2122 1 () ( ) ( ) ( ) () () ( ) ,( ), OR i OR mo ACD ACD ACD ACD ACD ACDsT s m M T T m M ′′′ ⇒∧=∧ =∧≥ +∆ () 2122 () () () () () () () OR i OR BE BE BE BEsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 3233 () () () () () () () OR i OR AB AB AB ABsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 3233 () () () () () () () OR i OR CD CD CD CDsT s m M T T ′′′ ⇒∧=∧=∧≥ (m(CD)=M2) ( ) 4144 ( ) () () () ( ) ( ) () OR i OR BB B BsT s m M T T ′′′ ⇒∧=∧ = ∧≥ () ( ) 4144 1 () ( ) ( ) ( ) () () ( ) ,( ), OR i OR mo ACD ACD ACD ACD ACD ACDsT s m M T T m M ′′′ ⇒∧=∧ =∧≥ +∆ () 5255 () () () () () () () OR i OR AC AC AC ACsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 5255 ( ) () () () ( ) ( ) () OR i OR DD D DsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 6166 () () () () () () () OR i OR CC C CsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 6166 () () () () () () () OR i OR AD AD AD ADsT s m M T T ′′′ ⇒∧=∧ =∧≥ (m(AD)=M1) () 9199 ( ) () () () ( ) ( ) () OR i OR AA A AsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 9199 () () () () () () () OR i OR DD D DsT s m M T T ′′′ ⇒∧=∧ =∧≥ () 10 2 10 10 () () () () () () () OR i OR CC C CsT s m M T T ′′′ ⇒∧=∧= ∧≥ (3) () 10 2 10 10 () () () () () () () OR i OR DD D DsT s m M T T ′′′ ⇒∧=∧= ∧≥ () () 51 5 1 243 1 5 234 () () () () ( , , ) () () ( , , ) i ch i ch sT sT T T M H H T T M H H ′′ ∧⇒≥+∆ ∧≥+∆ (4) () () 64 6 4 112 4 6 121 () () () () ( , , ) () () ( , , ) i ch i ch sT sT T T M H H T T M H H ′′ ∧⇒≥+∆ ∧≥+∆ () OR ABCDEminimiza Tabla 3. Conjun o de es icciones pa a el g a o And/O de la Figu a 5.