Source: http://docplayer.es/1260402-Un-modelo-de-integracion-de-tecnicas-de-clausura-y-csp-de-restricciones-temporales-aplicacion-a-problemas-de-scheduling.html
Timestamp: 2018-04-20 05:56:33+00:00

Document:
Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling - PDF
Download "Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling"
Sofia Bustamante Navarrete
1 UNIVERSIDAD DE ALICANTE Departamento de Ciencia de la Computación e Inteligencia Artificial Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling TESIS DOCTORAL Presentada por: María Isabel Alfonso Galipienso Dirigida por: Federico Barber Sanchís Alicante, Abril del
5 "Supongamos que tengo dos relojes: uno no funciona en absoluto, y el otro se retrasa un minuto al día: cuál preferirías? 'El que se retrasa', replicarías sin ninguna duda. Ahora observa: el que se retrasa un minuto al día tiene que emplear doce horas, o setecientos veinte minutos, hasta que de nuevo señale la hora correcta; por consiguiente, es puntual cada dos años, mientras que el otro es puntual evidentemente siempre que sea la hora por él indicada, lo que ocurre dos veces por día. De manera que ya te has contradicho..." ( LEWIS CARROLL, "The two clocks". ) 5
7 Agradecimientos Quiero dar las gracias en primer lugar a mi director de Tesis, Federico Barber, por su continuo apoyo. A pesar de la distancia que separa nuestros respectivos lugares de trabajo, ha sido como si prácticamente estuviesemos en despachos contiguos. Por supuesto, gracias Ramón, por haberme puesto en contacto con Fede, y tener paciencia, ya que esta tesis debería haber estado acabada hace tiempo. A mi querida amiga Paqui, que ya no tendrá que volverme a hacer la fatídica pregunta: " cuándo?", y a la que tendré que invitar dentro de poco..., gracias por animarme a terminar (de una vez). Aunque reconozco que la pregunta anterior también la he oído bastante de mis compañeros de trabajo (que además son amigos)...os agradezco el haber confiado en mí, pues la respuesta que llevo dando desde hace varios meses es: "no me queda nada, estoy a punto de terminar...". A mis padres. Y muy especialmente a mi madre. Ella me ha preguntado poco para no agobiarme, gracias por estar ahí, siempre. 7
8 8 Agradecimientos
9 RESUMEN En un problema de scheduling, existen un conjunto de restricciones (sobre las tareas, objetos del problema, uso de recursos compartidos, etc.), que deben satisfacerse para poder obtener una solución. En esta Tesis, plantearemos que un típico problema de scheduling puede especificarse como un problema de satisfacción de restricciones temporales métrico-disyuntivas entre puntos de tiempo. Así, los puntos de tiempo se configuran como las primitivas temporales de la especificación, y las restricciones temporales métrico-disyuntivas entre ellos permiten representar las restricciones existentes en el problema. En este marco, una primera aportación de la Tesis consiste en la extensión de especificaciones previas del problema de scheduling, proponiendo una especificación flexible y expresiva, así como las consecuentes restricciones temporales que subyacen entre puntos de tiempo. Con ello, se podrá especificar una amplia variedad de restricciones de scheduling que incluyen, por ejemplo, solapamientos en la ejecución de las actividades, deadlines, tiempos de descanso de las máquinas, tiempos de preparación, etc. Dado este marco de representación, una solución al problema de scheduling debe satisfacer todas las restricciones equivalentes entre los puntos de tiempo. Existen varias alternativas que permiten abordar la búsqueda de soluciones. Una de las aproximaciones más utilizadas es la de considerar el problema de scheduling como un Problema de Satisfacción de Restricciones (CSP: Constraint Satisfaction Problem). Así, los problemas de scheduling se representan en términos de un conjunto de variables (en este caso puntos temporales) y restricciones sobre sus valores (relaciones métrico-disuntivas). Una solución del problema consiste entonces en una asignación consistente de todas las variables, tal que se satisfacen todas sus restricciones. Durante el proceso de búsqueda de la solución es a menudo necesario realizar procesos de backtracking o vuelta atrás, cuando las asignaciones parciales realizadas violan alguna restricción. De esta forma, la eficiencia del proceso de búsqueda depende fundamentalmente de la ordenación en la elección de variables y valores a instanciar, para lo cual se utilizan distintas heurísticas de elección. Sin embargo, en un problema real de scheduling, puede ser frecuente la adición de nuevos conjuntos de restricciones, debido a un conocimiento parcial de las mismas al principio del 9
10 proceso, incidencias en los recursos a utilizar, cambios de la especificación, etc. Un inconveniente que presentan las aproximaciones CSP, es que en cada estado del proceso de búsqueda, se mantiene una única solución parcial (correspondiente a las asignaciones parciales realizadas a las variables), de forma que, frente a un cambio en el conjunto de restricciones se debe comenzar la búsqueda desde el principio, reasignando nuevos valores a las variables que satisfagan las nuevas restricciones introducidas. Es decir, el proceso CSP no tiene un carácter incremental respecto a las restricciones existentes en el problema. Por otro lado, los procesos de clausura de restricciones constituyen una alternativa para acotar soluciones en un problema de restricciones temporales. La clausura es un proceso deductivo, por el que se infieren nuevas restricciones a partir de las ya existentes. Con ello, permite detectar valores inconsistentes (es decir, que no forman parte de una solución) que pueden ser eliminados, manteniendo así un conjunto de soluciones activas. Particularmente, si el proceso de clausura utilizado es completo y correcto, se obtiene una red de restricciones mínima que contiene el conjunto de todas las soluciones posibles al problema. Un inconveniente de esta aproximación es que su coste es exponencial debido a la tipología de las restricciones (disyuntivas) correspondientes a un problema de scheduling. Existen propuestas híbridas, que alternan ambas técnicas. Típicamente, se utiliza un proceso de clausura parcial (generalmente, algoritmos de consistencia de senda o path-consistency) como preproceso para limitar el dominio de las variables, seguido de un proceso CSP. Por una parte, estas alternativas mantienen el carácter no incremental del proceso CSP ante modificaciones del conjunto de restricciones, al seguir manteniendo el proceso CSP una única solución. Por otra, las heurísticas aplicadas en un proceso CSP básico están basadas en la información disponible del problema en cada momento, de tal forma que ante una mayor información del conjunto actual de restricciones (por ejemplo, mediante procesos de clausura totales), podrían obtenerse heurísticas nuevas y más fundamentadas que permitieran una mayor eficiencia del proceso. Teniendo en cuenta el marco previo expuesto, las principales propuestas contenidas en esta Tesis consisten en: Un marco de representación flexible y expresivo para especificar problemas de scheduling mediante un conjunto de restricciones temporales métrico-disyuntivas basadas en puntos de tiempo. De esta forma se extienden especificaciones previas que no permiten captar diversas restricciones típicas existentes en problemas de scheduling reales. Un nuevo modelo de integración de los procesos de CSP y clausura para la resolución de problemas de restricciones temporales. Esta integración extiende y es más efectiva que la colaboración típica previa (separada y meramente secuencial) de estos procesos. Adicionalmente, se introduce un proceso de clausura total (completo y correcto), de forma alternativa y más potente que el proceso de clausura parcial. Este modelo de integración se aplica para la resolución de problemas de scheduling. Nuevas heurísticas orientadas para su aplicación en el modelo de resolución propuesto, en base a la nueva información disponible debido a la integración obtenida de los procesos de clausura y CSP. Adicionalmente, se han adaptado diversas heurísticas previas para su utilización de forma combinada con estas nuevas heurísticas propuestas en esta Tesis. 10 Resumen
11 Las ventajas fundamentales de la propuesta realizada son las siguientes: El marco de representación utilizado permite la especificación de problemas de scheduling con una gran variedad de restricciones, como por ejemplo solapamientos en la ejecución de las actividades, tiempos de descanso de las máquinas, costes de uso de las máquinas, fabricación de lotes, asignación de recursos, etc.. De esta forma, podemos tratar con problemas reales y no simples, sin tener que cambiar de método de resolución. La integración de los procesos de clasura y CSP permite un modelo de resolución incremental, de forma que se permite mantener múltiples soluciones cada vez que se añade una nueva restricción. Así, se puede aplicar a problemas de scheduling en los que no se conocen a priori todas las restricciones del problema (por ejemplo, cuando se utiliza de forma integrada con un planificador), o bien se producen cambios no previstos (por ejempo, cuando se utiliza en entornos dinámicos), o pueden producirse incidencias en la ejecución (scheduling dinámico), etc. La integración realizada permite la construcción de un modelo eficiente, en el que se puede variar el carácter incremental del mismo. Dependiendo de las características del problema, el modelo puede comportarse tanto como un CSP puro, o únicamente como un método de clausura. De esta forma se permite encontrar un equilibrio entre la bondad de las soluciones encontradas y el tiempo requerido para obtenerlas. La integración realizada permite el uso de heurísticas mejor informadas, que contribuyen a mejorar la eficiencia del modelo propuesto. El modelo propuesto ha sido evaluado empíricamente, mostrando su capacidad para especificar distintos tipos de problemas de scheduling, así como el carácter incremental y eficiencia del mismo. Asímismo, también se ha experimentado con las heurísticas propuestas, comprobando sus efectos en los resultados obtenidos. Estas evaluaciones permiten finalmente concluir la novedad y aplicabilidad de los métodos y procesos desarrollados en amplios dominios de aplicación correspondientes a la tipología de problemas analizada. Resumen 11
12 12 Resumen
13 INDICE Agradecimientos RESUMEN Lista de Figuras Indice de Términos Lista de acrónimos utilizados PRESENTACIÓN CAPITULO 1 Introducción Razonamiento temporal Representación Razonamiento El problema de scheduling Conceptos básicos sobre scheduling Conceptos avanzados sobre scheduling Tipología de problemas de scheduling Scheduling y planificación El problema de planificación Planificación temporal Integración planificación-scheduling Motivación y objetivos del trabajo...47 CAPITULO 2 Técnicas de resolución para problemas de scheduling Consideraciones previas Algunas representaciones utilizadas Complejidad de un problema de scheduling Técnicas de scheduling: clasificación general Técnicas de optimización Técnicas de aproximación Reglas de despacho de prioridad...59 Tesis 13
14 2.3.5 Heurísticas basadas en cuellos de botella Métodos de búsqueda local Técnicas basadas en Inteligencia Artificial Conceptos sobre redes de restricciones Satisfacción de restricciones: CSP Algoritmos CSP Principales aportaciones Clausura:deducción y propagación Conclusiones...80 CAPITULO 3 Un nuevo modelo: elementos Algebra temporal Algoritmo de clausura Ejemplo Ventajas e inconvenientes. Propuestas de mejora Conclusiones...97 CAPITULO 4 Representación: Restricciones temporales del sistema Elementos temporales en scheduling Representación de las operaciones Restricciones no disyuntivas Periodos de mantenimiento Tiempos de preparación de las máquinas Restricciones disyuntivas Patrón de flujo Fabricación por lotes Costes Lenguaje de especificación Especificaciones básicas Especificaciones de alto nivel Ejemplos Instancia job-shop (lectores de periódicos) Instancia flow-shop (lectores de periódicos) Instancia de fabricación con lotes Conclusiones CAPITULO 5 Modelo de resolución Características generales Algoritmo "ClausuraCSP" Parámetros del proceso Caracterización detallada del proceso ClausuraCSP Detección de no disyunciones Indice
15 5.3.3 Reglas de no inconsistencia Mantenimiento de indecisiones Revisión de indecisiones Backtracking Conclusiones CAPITULO 6 Medidas de textura y Heurísticas Conceptos básicos y terminología utilizada Obtención de nuevas cotas superiores Obtención de restricciones redundantes Heurísticas basadas en "slack" Heurísticas basadas en "edge-finding" Heurísticas basadas en información global Definición de "lateness". Heurísticas Heurísticas combinadas Conclusiones CAPITULO 7 Evaluación del modelo Generación de experimentos Análisis de Indecisiones vs. Backtracking Conclusiones Análisis del carácter incremental Conclusiones Análisis de eficiencia vs. heurísticas e indecisiones Conclusiones Proceso "auto-regulativo" Conclusiones Expresividad del modelo Tiempos de mantenimiento y preparación Costes y tiempos de mantenimiento Fabricación de lotes Conclusiones CAPITULO 8 Conclusiones y líneas futuras Líneas futuras Bibliografia Indice 15
16 16 Indice
17 Lista de Figuras Figura 1-1 Arquitectura de planificación y scheduling no integrada Figura 1-2 Arquitectura que integra los procesos de planificación y scheduling Figura 2-1 Representación de un grafo disyuntivo para una instancia Figura 2-2 Esquema básico de un algoritmo CSP Figura 2-3 Árbol de búsqueda generado por un proceso CSP Figura 3-1 Operación composición temporal Tlc Figura 3-2 Operación interseccción temporal Tlc Figura 3-3 Operación inclusión temporal Tlc Figura 3-4 Operación unión temporal Tlc Figura 3-5 Red de restricciones temporales métrico-disyuntivas Figura 3-6 Red temporal mínima asociada a la red de la Figura Figura 3-7 Paso 2) del algoritmo de clausura: propagación Figura 3-9 Red mínima G obtenida a partir de las restricciónes Q Figura 3-8 Red de restriciones temporales etiquetadas (LTCN) mínima Figura 3-10 Propagación de la relación lc Figura 3-11 Grafo Q resultante de añadir la relación rel Figura 4-1 Representación gráfica de una actividad o, con duración d Figura 4-2 Restricciones termporales asociadas a un trabajo J i Figura 4-3 Representación de las operaciones mediante un único punto temporal Figura 4-4 Representación de periodos de mantenimiento para una máquina Figura 4-5 Grafo de restricciones para máquinas con tiempos de preparación Figura 4-6 Restricción disyuntiva entre las operaciones o i y o j Figura 4-7 Representacion de patrón de flujo para una instancia flow-shop Figura 4-8 Representacion de patrón de flujo para una instancia job-shop Figura 4-9 Fabricación por lotes con solapamientos Figura 4-10 Grafo de restricciones asociado a un lote sin solapamiento Figura 4-11 Grafo de restricciones asociado a un lote con solapamientos Figura 4-12 Operaciones e intervalos de tiempo con costes particulares Figura 4-13 Intervalos etiquetados con el coste de una operación Figura 4-14 Representación de costes de uso de una máquina Figura 4-15 Ejemplo job-shop scheduling: lectores de periódicos Figura 4-16 Ejemplo flow-shop scheduling: lectores de periódicos Figura 5-1 Elementos del modelo de resolución propuesto Figura 5-2 Algoritmo del proceso de satisfacción de restricciones
18 Figura 5-3. Árbol de búsqueda generado con el algoritmo ClausuraCSP propuesto Figura 5-4 Algoritmo para detectar no-disyunciones Figura 5-5 Algoritmo para detectar inconsistencias Figura 5-6 Algoritmo para revisar disyunciones pendientes Figura 5-7 Arbol de decisiones generado durante el proceso de scheduling Figura 6-1 Slack temporal resultante de secuenciar dos operaciones o i y o j Figura 6-2 Incremento sufrido por el trabajo J j dada la ordenación (o i o j ) Figura 6-3 Ejemplo en el que las reglas de exclusión infieren nuevas restricciones Figura 6-4 Arbol de búsqueda en el que se generan "conjuntos" de soluciones parciales Figura 6-5 Operaciones pendientes de secuenciar Figura 6-6 Lateness resultante de secuenciar o B o A Figura 6-7 Heurística combinada de ordenación de variables edge_slack Figura 6-8 Heurística combinada de ordenación de variables makespan_slack Figura 7-2 Tiempo consumido en obtener una solución Figura 7-1 Número de backtrackings realizados según las indecisiones mantenidas Figura 7-3 Número de backtrackings realizados con dos recursos cuellos de botella Figura 7-4 Restricciones procesadas con disyunciones aleatorias: 0 indecisiones Figura 7-5 Restricciones procesadas con disyunciones aleatorias: 2 indecisiones Figura 7-6 Restricciones procesadas con disyunciones aleatorias: 4 indecisiones Figura 7-7 Restricciones procesadas considerando 1 instancia sin indecisiones Figura 7-8 Restricciones procesadas considerando 1 instancia con 2 indecisiones Figura 7-9 Restricciones procesadas considerando 1 instancia con 4 indecisiones Figura 7-10 Tiempo consumido para procesar restricciones disyuntivas al azar Figura 7-11 Tiempos para procesar restricciones aleatorias para una instancia Figura 7-12 Número de backtrackings y solución obtenida para instancias no aleatorias Figura 7-13 Efecto del uso de heurísticas locales y globales Figura 7-14 Efecto de distintas combinaciones de heurísticas Figura 7-15 Variación en la cardinalidad de las restricciones Figura 7-16 Ejemplo flow-shop scheduling: lectores de periódicos Figura 7-17 Ejemplo job-shop scheduling: lectores de periódicos Figura 7-18 Ejemplo fabricación por lotes Figura 8-1 Elementos de la interacción planificación-scheduling Lista de Figuras
19 Indice de Términos actividad asignación de recursos backtracking CInd coste(o ij ) deadline due time dur(o i ) dur_l l (o ij ) est_next(o p,o q ) est_nextd(o p,o q ) estd(o i) fabricación de lotes factibilidad first(j i ) first(loti) flow-shop fragmentación job-shop last(j i ) last(lot i ) latenes_nextdmin lateness_next(o p,o q ) lateness_nextd(o p,o q ) lftd(oi) L-set makespan makespand medidas de textura multi-level scheduling new_est_next(o p,o q )
20 new_est_nextd(o p,o q ) non-preemptive scheduling...36 off(o) on(o) open-shop optimalidad...33 patrón de flujo...33 permutation Flow-Shop...36 preemptive scheduling ready time...32 restricciones de precedencia restricciones disyuntivas o de capacidad...32 scheduling dinámico...37 slackd(o i,o j ) tp(o i ) trabajo Indice de Términos
21 Lista de acrónimos utilizados AI IA IA-TCN BB BC BJ BM BT CBA CS CLP CSP DCE DCSP DSR FC IBH KBS LOFF LPC Artificial Intelligence Interval Algebra Interval Algebra based Temporal Constraint Network Branch and Bound Brackchecking Backjumping Backmarking Cronological Backtracking Constraint-Based Analysis Constraint Satisfaction Constraint Logic Programming Constraint Satisfaction Problem Dynamic Consistency Enforcement Dynamic Constraint Satisfaction Problem Dynamic Search Rearrangement Forward Checking Incomplete Backjumping Heuristic Knowledge Based System Learning Ordering From Failure Loose-Path-Consistency 21
22 MPCP PA PA-TCN PCP PDR PLA POP SBP STP TCA TCN TCSP ULT Multi Precedence Constraint Posting Point Algebra Point Algebra based based Temporal Constraint Network Precedence Constraint Posting Proirity Dispatch Rules Partial look ahead Partial Order Planification Shifting Bottleneck Procedure Simple Temporal Problem Transitive Closure Algorithm Temporal Constraint Network Temporal Constraint Satisfaction Problem Upper-Lower-Tightening 22 Lista de acrónimos utilizados
23 PRESENTACIÓN En esta tesis se aborda la resolución de problemas que pueden plantearse como un conjunto de restricciones temporales. Concretamente se propone un nuevo modelo que integra técnicas de clasura y satisfacción de restricciones (CSP) aplicado a resolución de problemas de scheduling. La exposición se ha estrucutrado en ocho capítulos con los contenidos que se detallan a continuación. Los dos primeros capítulos pretenden introducir de forma general los conceptos fundamentales en los que se basa el trabajo realizado. Concretamente en la introducción se presenta el problema de razonamiento temporal, centrándose en la importancia del marco de representación utilizado, así como en los mecanismos de razonamiento empleados en algunos de los modelos de restricciones temporales planteados. Además, se describen algunos de los conceptos principales sobre scheduling y su relación con el problema de planificación, más concretamente con la integración de ambos procesos, ya que el método que se va a proponer plantea como aplicación futura la de su uso en dicho marco integrado. Finalmente se plantea la motivación y objetivos de la tesis. El capítulo 2 está dedicado al estudio de las principales técnicas existentes para resolver problemas de scheduling, bajo su planteamiento de un problema de satisfacción de restricciones, incluyendo algunas de las representaciones utilizadas. Se analizan algunas de las aportaciones más relevantes centrando la atención en la representación de red temporal, y en dos técnicas de resolución: satisfacción de restricciones y clausura, poniendo de manifiesto las ventajas e inconvenientes de cada una de ellas. El capítulo 3 supone el inicio de la propia aportación contenida en esta tesis. En el se presentan los elementos fundamentales en los que se basa el nuevo modelo: el álgebra temporal subyacente, y el algoritmo de clausura utilizado. Se analizan las ventajas e inconvenientes de dicho algoritmo, y se exponen las propuestas de mejora, que constituyen la base de las aportaciones realizadas en la tesis, y que se tratan en los capítulos posteriores. Los siguientes tres capítulos se dedican a la presentación del nuevo modelo, detallando cada uno de los elementos principales que lo forman. Así, en el capítulo 4 se establecen las restricciones temporales del sistema que permiten representar un problema genérico de scheduling. Dichas 23
24 restricciones están basadas en el modelo temporal descrito en el capítulo 3 y amplían la expresividad de los modelos previos de representación. Mediante estas restricciones se pueden representar por ejemplo solapamientos de ejecución entre las actividades, tiempos de descanso y periodos de mantenimiento de las máquinas, inclusión de costes de uso de los recursos y fabricación por lotes, además de las restricciones "típicas" asociadas a problemas de scheduling. El capítulo 5 se dedica a exponer el método de resolución, utilizando como datos de entrada el conjunto de restricciones temporales detalladas en el capítulo anterior. El nuevo modelo es capaz de encontrar una solución (o conjunto de soluciones) óptima o cercana a la óptima (si existe) de forma eficiente e incremental, es decir, sin necesidad de conocer previamente el conjunto completo de restricciones del problema. Dicho método permite además, la parametrización de ciertos elementos, como son el número máximo de indecisiones mantenidas en la red, así como las heurísticas de ordenación de variables y valores a utilizar. Esto nos va a permitir dos cosas: Variando el parámetro de indecisiones mantenidas se puede regular el comportamiento del algoritmo de forma que se invierta más esfuerzo en la propagación (clausura), o en la búsqueda de soluciones (CSP). Si el número máximo de indecisiones mantenidas en la red es cero, entonces el algoritmo se asemeja a un CSP. Variando las heurísticas a utilizar se pueden resolver problemas con características particulares que se beneficien del uso de dichas heurísticas sin tener que cambiar el método de resolución. En el capítulo 6 se presentan las heurísticas utilizadas por el modelo. Podemos distinguir dos tipos de heurísticas: Heurísticas existentes que tienen que ser adaptadas para su aplicación en el nuevo modelo. Heurísticas nuevas, tanto de carácter local como global. Estas últimas aprovechan la información propagada durante la clausura. Además se propone el uso de heurísticas combinadas con la finalidad de tomar mejores decisiones durante el proceso de búsqueda de soluciones. En el capítulo 7 se lleva a cabo una evaluación del modelo de resolución de restricciones propuesto mediante su aplicación a problemas de scheduling. Para ello se contará con muestras generadas aleatoriamente, así como con instancias obtenidas de uno de los bancos de prueba más conocidos y utilizados por la comunidad de investigadores en scheduling. En los experimentos se pretende contrastar la expresividad del modelo, así como la eficiencia y el carácter incremental del mismo. Una característica adicional interesante es la capacidad de "autoregulación" del método, de forma que durante el proceso de búsqueda de soluciones el número de indecisiones mantenidas varía con el tiempo, así como su número, en función de la capacidad de decisión de las heurísticas utilizadas, redundando en una mayor eficiencia. Finalmente, en el capítulo 8 se presentan las conclusiones de esta tesis, así como propuestas de modificaciones del método y posibles líneas futuras de aplicación. En este sentido se comenta la posible integracíon del modelo planteado con un modelo de planificación, lo cual está siendo objeto 24 Presentación
25 de estudio a través un proyecto de investigación en estos momentos, siendo esta tesis uno de los resultados de dicho proyecto en curso. Presentación
26 26 Presentación
27 CAPITULO 1 Introducción Scheduling 1 es el proceso de asignar recursos a tareas lo largo del tiempo [Baker74]. Los problemas de scheduling se presentan en áreas tan diversas como planificación de la producción, planificación de personal, diseño de computadores, confección de horarios, etc. A lo largo de los años, la teoría y aplicaciones de scheduling se han convertido en un importante campo de investigación. Un problema de scheduling puede caracterizarse como un conjunto de restricciones temporales, y por lo tanto, las técnicas desarrolladas en áreas como Razonamiento Temporal y Satisfacción de Restricciones, se vienen aplicando para resolver problemas de scheduling. Principalmente se han utilizado dos procesos: clausura (Razonamiento Temporal), [Dechter94], [Dechter96], [Stergiou00], [Barber00], y CSP (Constraint Satisfaction Problem), [Dechter98], [Nuijten98], [Beck00]. La clausura es un proceso deductivo, mediante el cual se infieren nuevas restricciones, a partir de las ya existentes. También permite detectar posibles inconsistencias (valores de las variables que no conducen a ninguna solución), que pueden eliminarse. La principal ventaja de las técnicas de clausura consiste en la reducción del espacio de búsqueda. Por lo tanto se utilizan fundamentalmente como un paso previo a un proceso de búsqueda de soluciones. Las técnicas de satisfacción de restricciones CSP, constituyen un proceso de búsqueda de soluciones mediante la sucesiva asignación de valores a las variables que forman parte de las restricciones del problema. En un proceso CSP, es importante el uso de distintas heurísiticas que hagan más eficiente dicho proceso de búsqueda [Wallace96], [Sadeh95a], [Sadeh95b], [Beck97], [Beck00]. Para resolver problemas de scheduling se han venido usando aproximaciones que alternan los procesos de clausura y CSP. Nuestra propuesta consiste en un nuevo modelo de resolución de restricciones temporales que integre ambas técnicas. De esta forma se obtienen ventajas, como 1. A lo largo de este trabajo utilizaremos la palabra inglesa "scheduling", ya que no es posible expresar dicho concepto en castellano con una única palabra 27
28 Introducción por ejemplo su aplicabilidad a problemas de planificación-scheduling y problemas de scheduling dinámico. Teniendo en cuenta que un problema de scheduling puede considerarse como un problema de restricciones temporales, en este capítulo se abordan las cuestiones fundamentales de cualquier modelo de Razonamiento Temporal: la representación de las restricciones temporales del problema a resolver, y los mecanismos de razonamiento utilizados. Con respecto a esto último, se centra la atención en las técnicas de clasura y CSP como dos de las aproximaciones utilizadas para razonar acerca de las restricciones de un problema (y por lo tanto, para resolver un problema de scheduling). A continuación se presenta una descripción general del problema de scheduling, y se analizan algunos de los conceptos más relevantes relacionados. Posteriormente, se hace referencia a la consideración de esta tesis para ser utilizada en un marco de planificación y scheduling integrados [Garrido00]. Dicha integración fue el marco inicial de este trabajo, pero no es tratado en la tesis. Finalmente se detallan los objetivos de la tesis, y que sirven de motivación para el resto del trabajo. 1.1 Razonamiento temporal El razonamiento temporal constituye un campo activo de investigación en varias áreas de la Inteligencia Artificial, tales como planificación, scheduling, sistemas basados en el conocimiento, y comprensión del lenguaje natural. En estas áreas, y concretamente en scheduling, el tiempo juega un papel fundamental: los problemas tienen un comportamiento dinámico y es necesario poder representar y razonar acerca de la dimensión temporal de la información, tanto métrica como cualitativa que impone restricciones sobre los elementos del problema. El razonamiento temporal puede ser visto, por tanto, como el razonamiento sobre las restricciones (conocimiento) temporales de un problema, para lo cual se requiere un modelo de razonamiento temporal, formado por: Un lenguaje (representación) lo suficientemente expresivo para representar el conocimiento sobre los aspectos temporales del mundo (base de conocimiento temporal). Un mecanismo que permita razonar sobre el conocimiento temporal (razonamiento). A la hora de definir un modelo temporal siempre hay que buscar un equilibrio entre la expresividad que nos proporciona el lenguaje y la eficiencia de los métodos de razonamiento. Por ejemplo, la lógica de primer permite aprovechar las ventajas de su demostrador de teoremas, pero es poco expresiva. Por otro lado la lógica temporal es muy expresiva, pero realizar inferencias es un proceso bastante lento [Vila94]. 28 CAPITULO 1

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución