Decision diagrams have recently emerged as a promising approach for difficult scheduling problems, along with other challenging discrete optimization problems. Decision diagrams can offer a compact representation of the solution space, and has the ability to capture complex constraints that are hard to model or express in other techniques. This thesis explores two standard construction methods for relaxed decision diagrams, top-down construction and incremental refinement. The techniques are compared on their ability to handle scheduling problems with multiple time windows and precedence constraints. The construction methods are evaluated on several metrics, including generated bound, execution time, and the size of the diagram, on instances of the problem with up to 200 tasks. The results show that incremental refinement generates smaller diagrams with good bounds when compared to the top-down compilation algorithm; the reduction in diagram size and increase in bounds for incremental refinement comes at the expense of execution time compared to top-down compilation.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / A descoberta de correspondÃncias semÃnticas entre esquemas à uma importante tarefa para diversos domÃnios de aplicaÃÃes, tais como integraÃÃo de dados, data warehouse e mashup de dados. Na maioria dos casos, as fontes de dados envolvidas sÃo heterogÃneas e dinÃmicas, dificultando ainda mais a realizaÃÃo dessa tarefa. Ontologias vÃm sendo utilizadas no intuito de definir vocabulÃrios comuns usados para descrever os elementos dos esquemas envolvidos em uma determinada aplicaÃÃo. O problema de matching entre ontologias, ou ontology matching, consiste na descoberta de correspondÃncias entre os termos dos vocabulÃrios (representados por ontologias) usados entre as diversas aplicaÃÃes. As soluÃÃes propostas na literatura, apesar de serem totalmente automÃticas possuem natureza heurÃstica, podendo produzir resultados nÃo-satisfatÃrios. O problema se intensifica quando se lida com grandes fontes de dados. O objetivo deste trabalho à propor um mÃtodo para geraÃÃo e refinamento incremental de correspondÃncias entre ontologias. A abordagem proposta faz uso de tÃcnicas de filtragem de ontologias, bem como do feedback do usuÃrio para dar suporte à geraÃÃo e ao refinamento dessas correspondÃncias. Para fins de validaÃÃo, uma ferramenta foi desenvolvida e experimentos foram realizados. / The discovery of semantic correspondences between schemas is an important task for different fields of applications such as data integration, data warehousing and data mashup. In most cases, the data sources involved are heterogeneous and dynamic, making it even harder the performance of that task. Ontologies are being used in order to define common vocabulary used to describe the elements of the schemas involved in a particular application. The problem of matching between ontologies, or ontology matching, consists in the discovery of correspondences between terms of vocabularies (represented by ontologies) used between the various applications. The solutions proposed in the literature, despite being fully automatic have heuristic nature, and may produce non-satisfactory results. The problem intensifies when dealing with large data sources. The purpose of this paper is to propose a method for generation and incremental refinement of correspondences between ontologies. The proposed approach makes use of filtering techniques of ontologies, as well as user feedback to support the generation and refining these matches. For validation purposes, a tool was developed and experiments were conducted

HORTÊNCIO FILHO, Fernando Wagner Brito. Uma Abordagem Semi-automática para Geração Incremental de Correspondências entre Ontologias. 2011. 81 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-27T19:11:59Z No. of bitstreams: 1 2011_dis_fwbhortênciofilho.pdf: 2807164 bytes, checksum: f2d22503112321ee69d172f0ac56d4c8 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-27T19:14:07Z (GMT) No. of bitstreams: 1 2011_dis_fwbhortênciofilho.pdf: 2807164 bytes, checksum: f2d22503112321ee69d172f0ac56d4c8 (MD5) / Made available in DSpace on 2016-06-27T19:14:07Z (GMT). No. of bitstreams: 1 2011_dis_fwbhortênciofilho.pdf: 2807164 bytes, checksum: f2d22503112321ee69d172f0ac56d4c8 (MD5) Previous issue date: 2011 / The discovery of semantic correspondences between schemas is an important task for different fields of applications such as data integration, data warehousing and data mashup. In most cases, the data sources involved are heterogeneous and dynamic, making it even harder the performance of that task. Ontologies are being used in order to define common vocabulary used to describe the elements of the schemas involved in a particular application. The problem of matching between ontologies, or ontology matching, consists in the discovery of correspondences between terms of vocabularies (represented by ontologies) used between the various applications. The solutions proposed in the literature, despite being fully automatic have heuristic nature, and may produce non-satisfactory results. The problem intensifies when dealing with large data sources. The purpose of this paper is to propose a method for generation and incremental refinement of correspondences between ontologies. The proposed approach makes use of filtering techniques of ontologies, as well as user feedback to support the generation and refining these matches. For validation purposes, a tool was developed and experiments were conducted / A descoberta de correspondências semânticas entre esquemas é uma importante tarefa para diversos domínios de aplicações, tais como integração de dados, data warehouse e mashup de dados. Na maioria dos casos, as fontes de dados envolvidas são heterogêneas e dinâmicas, dificultando ainda mais a realização dessa tarefa. Ontologias vêm sendo utilizadas no intuito de definir vocabulários comuns usados para descrever os elementos dos esquemas envolvidos em uma determinada aplicação. O problema de matching entre ontologias, ou ontology matching, consiste na descoberta de correspondências entre os termos dos vocabulários (representados por ontologias) usados entre as diversas aplicações. As soluções propostas na literatura, apesar de serem totalmente automáticas possuem natureza heurística, podendo produzir resultados não-satisfatórios. O problema se intensifica quando se lida com grandes fontes de dados. O objetivo deste trabalho é propor um método para geração e refinamento incremental de correspondências entre ontologias. A abordagem proposta faz uso de técnicas de filtragem de ontologias, bem como do feedback do usuário para dar suporte à geração e ao refinamento dessas correspondências. Para fins de validação, uma ferramenta foi desenvolvida e experimentos foram realizados.