Un modelo para el tratamiento de sistemas dinámicos basado en la satisfacción de restricciones

Abstract

En numerosas aplicaciones industriales complejas de plaificación y scheduling, resulta frecuente encontrar casos donde un problema ya resuelto debe ser reconsiderado a causa de una ligera modificación en la instancia de dicho problema. Estas modificaciones se originan generalmente a partir de sucesos externos que implican un cambio de creencias y en consecuencia el conjunto de soluciones obtenido para el problema resuelto ha de modificarse. Estos casos son referidos generalmente como problemas dinámicos, frente a los problemas estáticos. En los primeros, el conjunto de soluciones puede ser ligeramente modificado, mientras que en los segundos, el conjunto de soluciones es fijo e inalterable. El tipo de problemas que nos preocupa se refieren a problemas modelados a través de restricciones, concretamente, restricciones lineales sobre variables de dominio finito. Estos tipos de problemas son estáticos, cuando las soluciones obtenidas no son reconsideradas ante el cambio de la instancia del -problema. Los casos dinámicos antes expuestos son resueltos iniciando de nuevo el proceso de resolución con la instancia modificada como si fuese un problema diferente. Un resolvedor de problemas que reconsidere las soluciones obtenidas en un problema anterior ante un cambio ligero de su instancia lo denominaremos dinámico, frente a la denominación de estático antes utilizada. Así pues, un Sistema Dinámico de Restricciones (SDR) será aquel que considere las soluciones obtenidas para resolver la instancia modificada. Al contrario de los sistemas estáticos, un SDR plantea las modificaciones de las instancias como un único problema. En este trabajo definiremos un modelo de SDR e identificaremos el tipo de transiciones permitidas en el mismo, y discutiremos como abordar la resolución dinámica del SDR desde diferentes aproximaciones. Además, se propondrán varios métodos para el manejo dinámico de un sistema de restricciones. Finalmente, discutiremos brevemente que opción de las analizadas es la más adecuada para los problemas que estamos abordando.