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

Inteligencia Artificial, Revista Iberoamericana de Inteligencia Artificial. No.17 (Otoño 2002), pp. 83-92. ISSN: 1137-3601. © AEPIA (http://www.aepia.org/). Un modelo CSP para la planificación de la sustitución óptima de piezas defectuosas Carmelo Del Valle, Rafael M. Gasca, Juan A. Ortega, María T. Gómez Depto. Lenguajes y Sistemas Informáticos Universidad de Sevilla Avda. Reina Mercedes, s/n Sevilla, 41012 {carmelo,gasca,ortega,mayte}@lsi.us.es Resumen La aplicación de métodos de diagnosis basada en modelos permite obtener los posibles componentes involucrados en el comportamiento anómalo del sistema de estudio. Tras la diagnosis, el objetivo es restablecer el funcionamiento deseado mediante la reparación o sustitución de tales componentes. En sistemas complejos pueden existir muy diversas formas de realizar dicho proceso, y resulta de interés hacerlo de manera óptima. En este trabajo se presenta un modelo CSP (Problema de Satisfacción de Restricciones) para el secuenciamiento óptimo de tareas en la sustitución de piezas defectuosas cuando se suponen únicamente fallos simples. Para ello, se parte de un modelo para la selección de secuencias óptimas de ensamblaje en sistemas con múltiples máquinas. Para este último modelo, el objetivo del plan resultante es la minimización del tiempo total del ensamblaje, y para el anterior, del proceso global de reparación. Para ello, el modelo considera, además de las duraciones y los recursos utilizados por las tareas, los tiempos necesarios para el cambio de configuración (herramientas) en las máquinas de ensamblaje, y los retardos asociados al transporte de submontajes intermedios entre distintas máquinas. El problema puede ser visualizado mediante un grafo And/Or, que incluye el conjunto de todos los planes de montaje factibles para un producto. Esta representación recoge por un lado las restricciones de precedencia entre tareas, y por otro las relaciones entre las tareas para componer un plan correcto. En el presente trabajo se utiliza una extensión de esta representación que incluye todas las restricciones que aparecen en el problema, añadiéndose aquellas asociadas al uso de recursos. A partir de la representación anterior, se proponen sendos modelos CSP que recogen el conjunto de todas las restricciones del problema del ensamblado del producto completo y del problema de la sustitución de una pieza defectuosa. Palabras clave: Planificación y Scheduling, Satisfacción de Restricciones, Diagnosis, Recuperación de Fallos, Ensamblado y Desensamblado. 1. Introducción La aplicación de métodos de diagnosis basada en modelos [DeKleer87] [Reiter87] permite obtener el mínimo número de componentes involucrados en el comportamiento anómalo del sistema observado. Tras la diagnosis, el objetivo es restablecer el funcionamiento deseado mediante la reparación o sustitución de tales componentes. En sistemas complejos, compuestos por un número elevado de componentes, y con acceso limitado a muchos de ellos, pueden existir muy diversas formas de realizar dicho proceso, y resulta de interés hacerlo de manera óptima. Se trata pues de planificar el secuenciamiento óptimo de las tareas que lo lleven a cabo. Entre dichas tareas se encuentran las del desensamblado y ensamblado del producto. Los problemas de secuenciamiento representan una clase de problemas especialmente difíciles de resolver. Muchos de ellos han sido estudiados ampliamente mediante el uso de técnicas de satisfacción de restricciones, como el problema de Job Shop Scheduling [Caseau95] [Esquirol96]. En este trabajo se plantea por un lado un modelo CSP (Problema de Satisfacción de Restricciones) para la selección de secuencias de ensamblaje. Este problema supone un mayor grado de complejidad, ya que se añade a la determinación del orden y los tiempos de las tareas, la propia selección de las mismas dentro de un conjunto de planes alternativos. Esta problemática ha sido poco estudiada, por lo que es de especial interés el desarrollo de técnicas de búsqueda CSP que la contemplen [Beck00]. Por otro lado, cuando se obtienen los resultados de aplicar los métodos de diagnosis basada en modelos a los sistemas con múltiples piezas, nos enfrentamos a la dura tarea de realizar el desensamblado óptimo del sistema hasta encontrar la pieza resultante del proceso de diagnosis, suponiendo que sólo se atiende a fallos simples, es decir, asociados a una sola pieza o bloque. La Figura 1 muestra un esquema del proceso global, en el que los resultados obtenidos en la diagnosis se introducen en el planificador, que deberá determinar la secuencia adecuada de operaciones para extraer la pieza defectuosa, la propia sustitución o reparación de la misma y el posterior reensamblado del sistema. Extracción de pieza defectuosa Diagnosis Sustitución/reparación de la pieza defectuosa Reensamblado del producto Modelo CSP Figura 1. Esquema del proceso diagnosis/reparación. Este problema ha sido tratado poco en la bibliografía y es el objetivo principal de este trabajo. Ello se llevará a cabo mediante el modelado de dicho problema mediante un problema de satisfacción de restricciones que considera además de los recursos utilizados en las tareas, las duraciones de las mismas. La resolución del mismo puede realizarse mediante herramientas de programación con restricciones. El modelo de planificador propuesto considerará que la diagnosis proporciona la detección de un fallo simple. El resto del artículo se estructura de la siguiente manera: en la sección 2 se describe el problema de la selección de secuencias de ensamblaje, y en la sección 3 se detalla el modelo de planificación propuesto. En la sección 4 se establece el modelo CSP para el problema de planificación correspondiente al ensamblaje completo de un producto a partir de las piezas separadas, haciendo especial hincapié en la distinción de la selección de tareas alternativas. La sección 5 muestra el modelo CSP para la sustitución o reparación de una pieza defectuosa, detectada mediante un proceso de diagnosis basada en modelos. Por último, en la sección 6 se indican las conclusiones y se trazan las líneas de trabajo futuro a desarrollar a partir del modelo propuesto. 2. Selección de secuencias de ensamblaje La planificación del ensamblaje es un problema de especial interés en la fabricación de productos. En él se contemplan la identificación, selección y secuenciamiento de operaciones de ensamblaje, consideradas desde el punto de vista de su efecto sobre las piezas a ensamblar. La identificación de las tareas de ensamblaje se aborda mediante el análisis de la estructura del producto, utilizando un sistema experto interactivo [Bourjault84] [DeFazio87], o de forma automática a partir de modelos geométricos y relacionales [Homem91] y de modelos CAD y otras informaciones de tipo no geométrico [Romney95] [Calton99]. La identificación de las operaciones de ensamblaje conduce normalmente al conjunto de todos los planes de ensamblaje factibles. El número de ellos crece exponencialmente con el número de piezas, y depende de otros factores, tales como la forma en que las piezas están interconectadas en el ensamblaje completo, representado a través del grafo de conexiones. De hecho, este problema ha sido probado como NP-completo [Wilson95]. La siguiente consideración es la obtención de un plan de montaje óptimo, seleccionado del conjunto de todos los planes de ensamblaje factibles. En la mayoría de los casos, el objetivo es minimizar la aparición de elementos problemáticos para la ejecución del ensamblaje, como movimientos complicados o inestables, y tareas no productivas, como cambios de dispositivos de fijación y reorientación de piezas. En [Goldwasser99] se indica un amplio conjunto de criterios de selección. Se han usado grafos And/Or para la representación del conjunto de todos los planes de ensamblaje factibles [Homem90]. En tal representación, los nodos Or se corresponden con submontajes, siendo el nodo raíz el que hace referencia al producto completo, y los nodos hoja a las piezas individuales. Cada nodo And se corresponde con la tarea de montaje que une los submontajes de sus nodos hijos produciendo el submontaje de su nodo padre. Un árbol de ensamblaje es un camino del grafo And/Or que comienza en el nodo raíz y termina en los nodos hoja, y representa un plan de montaje, que recoge las restricciones de precedencia entre las tareas que lo forman. Una secuencia de montaje es una secuencia ordenada de tareas de montaje, que satisface las restricciones de orden de tareas. Cada plan de montaje se corresponde con una o más secuencias de montaje. Una importante ventaja de esta representación, usada en este trabajo, es que el grafo And/Or muestra la independencia de las tareas de ensamblaje que pueden ejecutarse en paralelo. La Figura 2 ilustra un ejemplo de esta representació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 Figura 2. Grafo And/Or para el ensamblaje del producto ABCDE. 3. Modelo de planificación propuesto El problema planteado es la selección de un plan de montaje, es decir, uno de los árboles que componen el grafo And/Or, y el secuenciamiento de las tareas que lo componen. El criterio seguido en este trabajo es la minimización del tiempo total del ensamblaje en un sistema con varias máquinas de ensamblaje [DelValle96], por lo que se han considerado todos aquellos factores que pueden influir en tal medida. Para ello, se parte de una estimación previa de los recursos necesarios (máquina y herramienta) y duración aproximada de cada una de las tareas de montaje. El modelo considera una única combinación duración-máquina-herramienta para cada tarea de montaje. Sin embargo, puede ser extendido sin dificultad cuando se tengan varias opciones para la construcción de un submontaje a partir del mismo grupo de componentes: basta con suponer que cada opción se corresponde con una tarea de montaje diferente, lo que significaría la adición de nodos And en el grafo And/Or entre los mismos nodos Or. Otro factor que ha sido considerado es el tiempo necesario para el cambio de herramientas en las máquinas, que suele ser del mismo orden que las propias duraciones de las tareas de montaje, por lo que no deben despreciarse. ∆cht(M, H, H') denotará el tiempo necesario para instalar en la máquina M la herramienta H' si previamente estaba instalada la herramienta H. Debe observarse que cualquier cambio de configuración en las máquinas que deba realizarse entre la ejecución de dos tareas puede modelarse de esta forma, aunque aquí se ha visualizado a través del uso de herramientas. También se tienen en cuenta en el modelo los retardos asociados al transporte de piezas y submontajes. El modelo propuesto supone un sistema bien dimensionado en el que existe un sistema logístico perfecto, de forma que cuando una pieza sea requerida en una máquina para realizar una operación de ensamblaje, esté presente allí. Lo mismo no puede asegurarse para un submontaje intermedio, ya que éste podría ser ensamblado en una máquina e inmediatamente ser requerido en otra distinta para formar otro submontaje. De esta forma, denotaremos mediante ∆mov(SA, M, M') al retardo asociado al transporte del submontaje SA desde la máquina M hacia la máquina M'. Otro punto de interés del modelo propuesto es que los resultados que se derivan de él pueden ser usados en distintas etapas del proceso de planificación, desde el propio diseño del producto y del sistema de ensamblaje hasta su ejecución final. Asimismo, como se muestra en el presente trabajo, también es fácilmente extensible para ser usado en el mantenimiento posterior del producto, mediante tareas de sustitución o reparación de componentes defectuosos, que hayan podido ser detectados mediante procesos de diagnosis. 4. El modelo CSP para el ensamblaje de un producto La representación mediante grafos And/Or recoge por un lado las restricciones de precedencia entre tareas, y por otro las relaciones entre las tareas para construir un plan correcto. En el presente trabajo se propone una extensión de esta representación de forma que se incluyan todas las restricciones que aparecen en el problema, añadiéndose aquéllas asociadas al uso de recursos por las tareas. Por motivos de mayor claridad en la exposición, se muestra en primer lugar el modelo correspondiente al caso en que no hay planes alternativos, para pasar a continuación a formular el modelo para el caso general. Cada nodo del grafo And/Or tendrá una serie de variables asociadas o atributos. En la sección anterior se indicaron aquellos que pueden considerarse como constantes: para cada tarea T (nodo And), su duración dur(T), máquina donde se ejecuta y herramienta utilizada en ella; para los submontajes (nodos Or), los retardos asociados a su transporte entre cada dos máquinas. Aparte de ello, consideraremos para ambos tipos de nodos distintas variables temporales: para cada tarea T, sus tiempos de comienzo, ti(T), y de finalización, tf(T); para cada submontaje SA, el tiempo en que fue construido, tOR(SA). 4.1. Modelo CSP sin tareas alternativas En la Figura 3 se muestra un grafo And/Or donde sólo existe un plan de montaje, por lo que todos los nodos deben formar parte de la solución. El problema es determinar los valores de las variables temporales asociadas a ellos, de forma similar a los problemas de scheduling disyuntivo. También se indican en la misma figura los distintos tipos de restricciones que aparecen en el problema. En la Tabla 1 se enumera el conjunto de todas las restricciones asociadas al grafo de la Figura 3. El primer tipo identifica los tiempos de los nodos Or con los de finalización de las tareas que los forman. El segundo tipo relaciona los tiempos de comienzo y finalización de las tareas, considerando la duración de las mismas. Las restricciones del tipo (3) incluyen, aparte de la precedencia entre los tiempos de inicio de los nodos And y los de los nodos Or, los posibles retardos asociados al transporte de los submontajes entre distintas 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) Figura 3. Extensión del grafo And/Or para el producto ABCDE con un solo plan de ensamblaje. Las restricciones del tipo (4) se corresponden con el retardo asociado al cambio de herramientas entre la ejecución de tareas con restricciones de precedencia. Nótese que para cada tarea, sólo será necesario relacionarla con otra situada más arriba en el grafo And/Or, la más cercana que utilice la misma máquina. Cuando además utilicen ambas la misma herramienta, la restricción resultante es superflua y puede ser eliminada. Para representar este tipo de restricciones se ha añadido un nuevo tipo de enlace entre nodos And en la Figura 3. Por último, las restricciones del tipo (5) expresan los dos posibles órdenes de ejecución de cada par de tareas, no relacionadas mediante precedencia, que utilizan una misma máquina, pudiendo conllevar también un cambio de herramientas. Para el ejemplo mostrado, se trata de que las tareas T5 y T11, que utilizan ambas la máquina M2, no pueden ejecutarse simultáneamente, es decir, la ejecución de T11 se ejecutaría tras la finalización de T5 o viceversa, obteniéndose la disyunción correspondiente. Para representar este tipo de restricciones también se ha añadido un nuevo tipo de enlace entre nodos And en la Figura 3. 4.2. Modelo CSP con tareas alternativas En la Figura 4 se muestra la extensión del grafo And/Or en el caso general en el que pueden existir distintos planes de ensamblaje. Ahora, las distintas tareas pueden aparecer en la solución final o no, y el conjunto de tareas que pueden formar una solución correcta vienen ligadas entre sí de forma que pertenezcan todas a un mismo árbol de ensamblaje. A su vez, el hecho de ejecutar unas tareas u otras implica que se formen unos submontajes intermedios u otros. De esta forma, a los atributos de los nodos se les añade una variable booleana que indique si el nodo en cuestión es seleccionado como parte de la solución, denotándose como s(T) y s(SA) para una tarea genérica T y un submontaje genérico SA respectivamente. Por otro lado, dado que un determinado submontaje puede ser formado en distintas máquinas, dependiendo de la tarea que se escoja para su montaje, será necesario añadir un nuevo atributo para los nodos Or, denotándose mediante m(SA) a la máquina donde se ensambla el submontaje SA. Puede observarse que los tipos de restricciones son similares al modelo anterior, de forma que se han usado los mismos elementos en el grafo And/Or extendido para representarlos. Las formas que tienen ahora las restricciones son más complejas, ya que incorporan toda la información necesaria a la selección de tareas (y submontajes) alternativas. En la Tabla 2 se muestra el conjunto de restricciones que definen el problema asociado a la Figura 4, y que se corresponde con el grafo And/Or de la Figura 2, en donde se han especificado los recursos utilizados por las distintas tareas. 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 Figura 4. Extensión del grafo And/Or para el producto ABCDE. Las restricciones del tipo (1) relacionan la selección de las tareas con la de los submontajes, expresado a través del operador OR exclusivo, dado que una y sólo una de las tareas que pueden formar un submontaje determinado puede ser escogida, si dicho submontaje forma parte de la solución. A su vez, definen las restricciones asociadas a los atributos (máquina y tiempo de formación) de los nodos Or en relación con las tareas que pueden ser escogidas. Un caso especial se da para el producto completo y para las piezas individuales, que siempre formarán parte de la solución, por lo que las variables booleanas s toman el valor true. Nótese que, por esta misma razón, la especificación de tOR Tipo Restricciones 2 ()() OR f ABCDEttT= 5 () () OR f ACDttT= 11 () () OR f BEttT= 8 () () OR f ACttT= (1) () () () () () 0 OR OR OR OR OR ABCD E tttt t ==== == 22 2 () () () fi tT tT durT=+ 55 5 () () () fi tT tT durT=+ 11 11 11 () () () fi tT tT durT=+ (2) 88 8 () () () fi tT tT durT=+ 221 () ( ) ( , , ) iOR mov ACD ACDtT t M M≥+∆ 221 () () (, , ) iOR mov BE BEtT t M M≥+∆ 512 () ( ) ( , , ) iOR mov AC ACtT t MM≥+∆ 5 () () iOR tT t D≥ 11 () () iOR tT t B≥ 11 () () iOR tT t E≥ 8 () () iOR tT t A≥ (3) 8 () () iOR tT t C≥ (4) 28 112 () () ( , , ) if cht tT t T M HH≥+∆ (5) 511 115 () () () () if i f tT t T tT t T≥∨≥ () OR ABCDEminimizar t Tabla 1. Conjunto de restricciones para el grafo And/Or de la Figura 3. Tipo Restricciones ( ) () () () () ()ABCDEABCDE s ssssstrue====== () 12 ()() ()ABCDE s sT XORsT⇒ () 121 () () ()() OR f ABCDE ABCDE s Tm Mt tT⇒=∧ = () 212 () () ()() OR f ABCDE ABCDE s Tm Mt tT⇒=∧ = () () 34 34 ( ) () () ( ) () ()ABCD ABCDssTXORsTs sTsT⇒∧¬ ⇒¬∧¬ () 323 () () ()() OR f ABCD ABCD s Tm Mt tT⇒=∧ = () 414 () () ()() OR f ABCD ABCD s Tm Mt tT⇒=∧ = () () 56 56 () () () () () ()ACD ACD s sT XORsT s sT sT⇒∧¬ ⇒¬∧¬ () 525 () () () () OR f ACD ACD s Tm Mt tT⇒=∧ = () 616 () () () () OR f ACD ACD s Tm Mt tT⇒=∧ = () 72 7 7 () () () () () () () OR f AB AB AB AB s sT m M t t T s sT⇒∧=∧ = ∧¬⇒¬ () 81 8 8 () () () () () () () OR f AC AC AC ACssTmMttT s sT⇒∧=∧ = ∧¬⇒¬ () 91 9 9 () () () () () () () OR f AD AD AD AD s sT m M t t T s sT⇒∧=∧ = ∧¬⇒¬ () 10 2 10 10 () () () () () () () OR f CD CD CD CD s sT m M t t T s sT⇒∧=∧ = ∧¬⇒¬ () 11 2 11 11 () () () () () () () OR f BE BE BE BE s sT m M t t T s sT⇒∧=∧ = ∧¬⇒¬ (1) () () () () () 0 OR OR OR OR OR ABCDEttttt===== 111 1 () () () () fi s T t T t T dur T⇒=+ ! (2) 11 11 11 11 () () () () fi s TtTtTdurT⇒=+ () 11 2 () ( ) () ( ) ( ,( ), ) iOR mov ABCD ABCD ABCD ABCDsT s t T t m M⇒∧≥ +∆ 11 () () () iOR EsT t T t⇒≥ () 22 1 () ( ) () ( ) ( ,( ), ) iOR mov ACD ACD ACD ACDsT s t T t m M⇒∧≥ +∆ () 22 21 () () () () (, , ) iOR mov BE BE BEsT s t T t M M⇒∧≥+∆ () 33 2 () () () () (() ) iOR AB AB AB s Ts tTt m M⇒∧≥ = () 33 2 () ( ) () ( ) (( ) ) iOR CD CD CD s Ts tTt m M⇒∧≥ = ! 11 11 () () () iOR BsT t T t⇒≥ (3) 11 11 () () () iOR EsT t T t⇒≥ () 51 1 5 234 () () () () ( , , ) if cht s TsT tTtT MHH∧⇒≥+∆ () 64 4 6 121 () () () () ( , , ) if cht s TsT tTtT MHH∧⇒≥+∆ () 73 3 7 234 () () () () ( , , ) if cht s TsT tTtT MHH∧⇒≥+∆ (4) () 82 2 8 112 () () () () ( , , ) if cht s TsT tTtT MHH∧⇒≥+∆ () () 511 5 11 11 5 () () () () () () if i f s TsT tTtTtT tT∧⇒≥∨≥ (5) () ()() () 7 10 7 10 243 10 7 234 () () () () ( , , ) () () ( , , ) if cht i f cht sT sT t T t T M H H t T t T M H H∧⇒≥+∆ ∨≥+∆ () OR ABCDEminimizar t Tabla 2. Conjunto de restricciones para el grafo And/Or de la Figura 4. para las piezas individuales es más simple (igual a cero). El resto de restricciones también tienen forma de implicación, de manera que en el consecuente aparecen las expresiones del modelo anterior, y se usan como antecedentes las expresiones booleanas que expresan la selección de las tareas que aparecen en el consecuente. Las restricciones de tipo (3) relacionan además la selección de los submontajes con la de las tareas que los utilizan para formar otro mayor. Es necesario hacer notar que para formar las restricciones disyuntivas, del tipo (5), es preciso tener en cuenta, que sólo deben contemplarse entre tareas que puedan formar parte de una misma solución, es decir, pertenecientes a un mismo árbol de ensamblaje, además de usar la misma máquina. Ello puede realizarse fácilmente tratando de emparejar, para cada nodo And del grafo And/Or, cada tarea por debajo de uno de los nodos Or hijos con cada una de las que están por debajo del otro nodo Or hijo. Puede observarse cómo el carácter combinatorio del problema viene dado por las restricciones de los tipos (1) y (5), correspondientes a la selección de tareas alternativas y al uso exclusivo de recursos compartidos por tareas no relacionadas mediante precedencia. 5. Modelo CSP para la sustitución de una pieza defectuosa El modelo construido en la sección anterior puede ser extendido con facilidad para abordar el problema de la sustitución o reparación de piezas defectuosas. En este trabajo se supone que a partir de un proceso de diagnosis basada en modelos se detecta un fallo en una de las piezas del producto. La reparación del sistema se realiza a partir de una secuencia de tareas, las primeras de desmontaje para extraer la pieza defectuosa, a continuación la reparación o sustitución de la misma y por último las tareas necesarias para volver a ensamblar el producto completo. El grafo And/Or puede utilizarse para representar tanto el proceso de montaje como el opuesto, el desensamblado. Para ello, puede suponerse en primer lugar que para cada tarea de ensamblaje T, existe su correspondiente de desmontaje, a la que denotaremos mediante T', sin que la incluyamos explícitamente en el grafo And/Or, por motivos de claridad. Hay que tener en cuenta que no siempre tiene por qué ser cierta esa suposición, de manera que pueda ser factible la tarea de unir dos submontajes dados para obtener el resultante mientras que la opuesta no sea posible realizarla, o viceversa. Sin embargo, basta con asignar una duración muy elevada a la tarea no factible para que la suposición realizada pueda ser considerada como válida. Para cada tarea de desmontaje T', se tendrán como datos los recursos a utilizar, máquina y herramienta, y su duración estimada. Téngase en cuenta que no tienen por qué coincidir las máquinas y herramientas para las tareas de ensamblaje y desmontaje correspondientes al mismo nodo And, aunque lo normal es que así sea, al menos para la máquina de ensamblaje. Otra suposición que aquí se hará es que si para extraer la pieza defectuosa se realiza a través de una secuencia dada de tareas de desmontaje, obteniendo unos submontajes intermedios determinados, el proceso de montaje usará las tareas equivalentes de ensamblaje, es decir, se usarán los mismos submontajes obtenidos, sin que aparezcan otros submontajes distintos. Además, todo submontaje que no contenga a la pieza defectuosa se mantendrá completo, es decir, sin desensamblar. De lo anterior se desprende que la solución buscada es una secuencia lineal de tareas, es decir, no se ejecutarán tareas en paralelo. De esta forma, no aparecerán en el modelo las restricciones disyuntivas correspondientes al uso de recursos compartidos –del tipo (5) en el modelo de la sección anterior–. Aparte de las nuevas tareas a considerar respecto al modelo de la sección anterior, hay otras variables que aparecen en el problema CSP. Para un submontaje dado SA, por un lado hay que distinguir entre la máquina donde se construye, a la que seguiremos denotando mediante m(SA), y la máquina donde queda tras el desmontaje procedente de uno mayor, a la que denotaremos mediante m'(SA). A su vez, también habrá que distinguir para cada submontaje entre el tiempo en que es construido, tras la ejecución de la tarea de ensamblaje correspondiente, al que seguiremos denotando mediante tOR(SA), y el tiempo en que se obtiene tras la ejecución de una tarea de desmontaje, al que denotaremos mediante t'OR(SA). Con las suposiciones anteriores, las variables booleanas correspondientes a la selección de planes alternativos pueden seguir siendo usadas las mismas, de manera que para los nodos And, s(T) indicará que la solución contiene tanto a la tarea de ensamblaje T como a su correspondiente de desmontaje T'. Para el caso de los nodos Or, el sentido de la variable s(SA) es más obvio, ya que supone la aparición del submontaje SA en el proceso completo, no habiendo modificación con respecto al modelo anterior. Un último factor interviene en el problema, el correspondiente al tiempo necesario para la sustitución o reparación de la pieza defectuosa, que será denotado mediante ∆sust(P), siendo P la pieza en cuestión, y que supondremos independiente de la máquina en donde se extraiga. Para la obtención de la solución puede realizarse una simplificación del grafo And/Or, en el sentido de que no intervendrán aquellos nodos And situados por debajo de nodos Or correspondientes a submontajes que no contengan a la pieza defectuosa. Esto puede realizarse mediante un recorrido en profundidad del grafo. Ahora los nodos Or hojas pueden corresponderse tanto con piezas individuales como con submontajes que no contienen a la pieza defectuosa. Todos esos nodos tendrán el mismo tratamiento, a excepción del correspondiente a la pieza defectuosa. La Figura 5 muestra la simplificación del grafo And/Or resultante para el producto ABCDE utilizado en los ejemplos anteriores, cuando la pieza a sustituir es la D. En dicha simplificación puede observarse cómo no aparecen algunos de los nodos And, concretamente los que estaban situados por debajo de los nodos Or que no contienen a D. El hecho de que no haya desaparecido ningún nodo Or en el ejemplo se debe a la casuística del mismo: todos los submontajes que no contienen a D tienen a lo sumo dos piezas, y todas las piezas distintas a D se pueden separar de algún submontaje que contiene a D, por lo que todas las hojas del grafo original (piezas individuales) permanecen en el grafo simplificado. La Tabla 3 muestra las restricciones resultantes para el ejemplo de la Figura 5. Por simplicidad se ha supuesto en el mismo que las tareas de ensamblaje y de desmontaje correspondientes a un mismo nodo And utilizan la misma máquina y la misma herramienta. De esta manera, los submontajes correspondientes a nodos Or hojas permanecen en la máquina correspondiente (o su entorno) hasta ser utilizados de nuevo en las tareas de montaje. Puede observarse por un lado, así como en la Figura 5, que no aparecen restricciones del tipo (5) correspondientes al modelo de la sección anterior, como se indicó previamente. Por otro lado, las restricciones son algo más complicadas en general al involucrar también las tareas de desmontaje. Así, las restricciones del tipo (1) entre un submontaje genérico SA y una tarea T (y su equivalente T') incluyen, aparte de lo ya indicado en la sección anterior, las relaciones entre t'OR y el tiempo de inicio de T', en donde se considera el posible transporte del submontaje desde la máquina en que fue obtenido tras el desmontaje hacia la máquina en donde se ejecuta T'. Un caso particular lo constituyen los nodos Or hojas, para los cuales se establece la igualdad entre t'OR y tOR, excepto para la pieza defectuosa, para la que se considera el posible retardo asociado a su reparación o sustitución. El origen del tiempo se establece para t'OR del producto completo, siendo el objetivo a minimizar su correspondiente tOR. 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 Figura 5. Extensión del grafo And/Or para la sustitución de la pieza D en el producto ABCDE. Las restricciones del tipo (2) incluyen obviamente las relaciones entre el tiempo de comienzo y finalización de las tareas de desmontaje. Las restricciones del tipo (3) incluyen las relaciones entre t'OR y el tiempo de finalización de las tareas de desmontaje, y permite obtener la variable correspondiente a la máquina m' a través de la tarea de desmontaje. Debido a las suposiciones realizadas en cuanto al uso de la misma máquina y herramienta por las tareas de ensamblaje y desmontaje correspondientes al mismo nodo And, no aparecen nuevas restricciones del tipo (4) que involucren a otros nodos en el grafo And/Or. Eso sí, las restricciones ahora también tienen en cuenta el retardo correspondiente en las tareas de desmontaje. Tipo Restricciones ()() ()0 OR ABCDE D ABCDEsstruet ′ == ∧ = () 12 ()() ()ABCDE s sT XORsT⇒ () 1211 () () ()()()() OR f i OR ABCDE ABCDE ABCDEsT m M t t T t T t ′′ ⇒=∧ = ∧ ≥ () 2122 () ( ) ( ) () () ( ) OR f i OR ABCDE ABCDE ABCDEsT m M t t T t T t ′′ ⇒=∧ = ∧ ≥ () () 34 34 ( ) () () ( ) () ()ABCD ABCDssTXORsTs sTsT⇒∧¬ ⇒¬∧¬ () ( ) 3233 2 () ( ) ( ) () () ( ) , ( ), ) OR f i OR mov ABCD ABCD ABCD ABCD ABCDsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () ( ) 4144 1 () () ()()() () ,(),) OR f i OR mov ABCD ABCD ABCD ABCD ABCDsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () () 56 56 () () () () () ()ACD ACD s sT XORsT s sT sT⇒∧¬ ⇒¬∧¬ () () 5255 2 () () () ()() () ,(),) OR f i OR mov ACD ACD ACD ACD ACDsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () () 6166 1 () ( ) ( ) () () ( ) , ( ), ) OR f i OR mov ACD ACD ACD ACD ACDsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ 9 () ()AD s sT= () () 9199 1 () ( ) ( ) () () ( ) , ( ), OR f i OR mov AD AD AD AD ADsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ 10 () ()CD s sT= () () 10 2 10 10 2 () () () () () () ,(), OR f i OR mov CD CD CD CD CDsT m M t t T t T t m M ′′ ′ ⇒=∧ = ∧ ≥ +∆ () { } () () () () (), ,,,,,, OR OR AB AC BE A B C Es SA m SA m SA t SA t SA SA ′′ ⇒=∧ = ∈ (1) () () () () () () () OR OR sust DDDDDDsmmtt ′′ ⇒=∧ =+∆ ( ) 1111111 () () () () () () () f i f i s T t T t T dur T t T t T dur T ′′ ′ ⇒=+ ∧ =+ ! (2) () 10 10 10 10 10 10 10 () () () () () () () fi fi s T t T t T dur T t T t T dur T ′′ ′ ⇒=+ ∧ =+ ( ( 1211 2 () ()() ()()() () ,(), OR f i OR mov ABCD ABCD ABCD ABCD ABCD ABCD s Ts m Mt tTtTt m M ′′′ ⇒∧=∧=∧≥+∆ () 1211 () () () () () () () OR f i OR E EE EsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () ( ) 2122 1 () ( ) ( ) ( ) () () ( ) ,( ), OR f i OR mov ACD ACD ACD ACD ACD ACDsT s m M t t T t T t m M ′′′ ⇒∧=∧ =∧≥ +∆ () 2122 () () () () () () () OR f i OR BE BE BE BEsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 3233 () () () () () () () OR f i OR AB AB AB ABsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 3233 () () () () () () () OR f i OR CD CD CD CDsT s m M t t T t T t ′′′ ⇒∧=∧=∧≥ (m(CD)=M2) ( ) 4144 ( ) () () () ( ) ( ) () OR f i OR BB B BsT s m M t t T t T t ′′′ ⇒∧=∧ = ∧≥ () ( ) 4144 1 () ( ) ( ) ( ) () () ( ) ,( ), OR f i OR mov ACD ACD ACD ACD ACD ACDsT s m M t t T t T t m M ′′′ ⇒∧=∧ =∧≥ +∆ () 5255 () () () () () () () OR f i OR AC AC AC ACsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 5255 ( ) () () () ( ) ( ) () OR f i OR DD D DsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 6166 () () () () () () () OR f i OR CC C CsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 6166 () () () () () () () OR f i OR AD AD AD ADsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ (m(AD)=M1) () 9199 ( ) () () () ( ) ( ) () OR f i OR AA A AsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 9199 () () () () () () () OR f i OR DD D DsT s m M t t T t T t ′′′ ⇒∧=∧ =∧≥ () 10 2 10 10 () () () () () () () OR f i OR CC C CsT s m M t t T t T t ′′′ ⇒∧=∧= ∧≥ (3) () 10 2 10 10 () () () () () () () OR f i OR DD D DsT s m M t t T t T t ′′′ ⇒∧=∧= ∧≥ () () 51 5 1 243 1 5 234 () () () () ( , , ) () () ( , , ) if cht if cht sT sT t T t T M H H t T t T M H H ′′ ∧⇒≥+∆ ∧≥+∆ (4) () () 64 6 4 112 4 6 121 () () () () ( , , ) () () ( , , ) if cht if cht sT sT t T t T M H H t T t T M H H ′′ ∧⇒≥+∆ ∧≥+∆ () OR ABCDEminimizar t Tabla 3. Conjunto de restricciones para el grafo And/Or de la Figura 5.