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.