• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 131
  • 6
  • 5
  • 1
  • Tagged with
  • 145
  • 98
  • 30
  • 29
  • 28
  • 27
  • 25
  • 22
  • 19
  • 19
  • 18
  • 16
  • 16
  • 16
  • 16
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
91

O Problema do agendamento semanal de aulas / Teacher Assignment and Course Scheduling

MARTINS, Jean Paulo 16 August 2010 (has links)
Made available in DSpace on 2014-07-29T14:57:46Z (GMT). No. of bitstreams: 1 dissertacao_jean.pdf: 321149 bytes, checksum: 11c9f94be02284e8412d026b60b596d0 (MD5) Previous issue date: 2010-08-16 / The Course Scheduling is a hard resolution problem, found in most of the learning institutions. Just like the others timetabling problems, the Course Scheduling have a strong associative characteristic, that means that its resolution is made of associations between events and resources. In the educational case, the lectures are events, while the teachers workload are resources. Techniques and methods have being used on the solution of these kind of problems, however is small the number of universities using software based solutions. This work is a starting point to software based solutions applied to the Federal University of Goiás. / O Agendamento Semanal de Aulas é um problema de difícil resolução enfrentado em grande maioria das instituições de ensino. Assim como os demais problemas de timetabling, possui como característica principal a sua natureza associativa, ou seja, sua resolução envolve a associação entre uma certa quantidade de recursos e eventos que utilizarão tais recursos. Especificamente em relação ao problema em questão, as aulas a serem ministradas podem ser caracterizadas como eventos, enquanto que a carga horária dos professores envolvidos podem ser vistas como recursos disponíveis (Programação de Horários de Aulas). Técnicas e métodos de grande relevância na ciência da computação estão relacionados na pesquisa e na solução destes tipos de problemas, contudo, a utilização de tais tecnologias no cotidiano de escolas e universidades ainda é pequena. Neste contexto, propõe-se uma abordagem para a resolução de Problemas de Programação de Horários, incluindo o Problema de Alocação de Professores a Disciplinas, e utiliza-se o Instituto de Informática da Universidade Federal de Goiás como um estudo de caso para tal.
92

Construção de Ontologias de Domínio a Partir de Mapas Conceituais / Construction of domain ontologies from conceptual maps.

Macedo, Gretchen Torres de 14 May 2007 (has links)
Made available in DSpace on 2015-04-11T14:03:22Z (GMT). No. of bitstreams: 1 Gretchen Torres de Macedo.pdf: 2254096 bytes, checksum: a92696f086cab0a30ffe0ff73682aa0f (MD5) Previous issue date: 2007-05-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Ontologies have been built and used in a variety of applications as a form of knowledge representation that is meant for software systems, or agents, as well as for human users. In relation to ontologies, conceptual maps are a more informal, simple and, thus, accessible form of knowledge representation. However, the freedom enjoyed in defining concepts and their links makes it dificult to directly draw formal representations from conceptual maps. This work presents a transcription process that is able to transform conceptual maps into ontologies specified in OWL (Web Ontology Language). In this way, the ease of construction of conceptual maps can be taken advantage of to alleviate the knowledge acquisition bottleneck that is inherent in ontology engineering. The translation process consists of two main stages: translation and merging. In the translation stage a group of conceptual maps about the same knowledge domain is transformed into a set of preliminary ontologies by mens of a translator module software. In the merging stage, ontology merging techniques are applied to the set of preliminary ontologies so as to yield a single unified ontology. This phase has been achieved by means of an available merging tool. Experiments for building conceptual maps have also been done and submited to the two phases of the translation process, in order to evaluate it. / Ontologias têm sido construídas e utilizadas em diversas aplicações como um modelo de representação de conhecimento compartilhável entre agentes de software e usuários. Mapas conceituais, por sua vez, são um modelo de representação do conhecimento que, em relação às ontologias, é informal, menos complexo e, portanto, de fácil elaboração. Entretanto, a liberdade permitida na definição de conceitos e relações nos mapas dificulta a transcrição direta desses modelos em representações formais que possam ser utilizadas em aplicações baseadas em conhecimento. Este trabalho apresenta um processo de transcrição de mapas conceituais em ontologias especificadas em OWL (Web Ontology Language), tornando possível o aproveitamento da facilidade de elaboração oferecida por mapas conceituais no processo de construção de ontologias de domínio. O processo de transcrição consiste de duas etapas principais: tradução e mesclagem. A etapa de tradução consiste na obtenção de ontologias intermediárias a partir de um conjunto de mapas conceituais tendo sido realizada mediante o desenvolvimento de uma ferramenta de software. A etapa de mesclagem, responsável por unificar as ontologias intermediárias obtidas na primeira etapa, foi realizada através da utilização de uma ferramenta de mesclagem existente. Foram ainda realizadas experiências de produção de mapas conceituais, os quais foram submetidos às ferramentas mencionadas, de forma a avaliar o processo apresentado.
93

Aplicação de meta heurísticas na otimização multiobjetivo de sistemas hidrotérmicos / Application of metaheuristics in the multiobjective optimization of hidrothermal systems

Camargo, Fernando Henrique Fernandes de 20 March 2017 (has links)
Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-06-19T13:06:19Z No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-07-10T12:28:25Z (GMT) No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-07-10T12:28:25Z (GMT). No. of bitstreams: 2 Dissertação - Fernando Henrique Fernandes de Camargo - 2017.pdf: 1478139 bytes, checksum: 1a8dae23d70a76b9e72b96aae929d85e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-20 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / For countries like Brazil, which has hybrid resources as the major source of electricity, the optimization of the operation of the hydroelectric plants is extremely important and it’s being studied recurrently. Adopting a known temporal decomposition model of this optimization problem, this dissertation is proposed to compare the best multiobjective algorithms of the current literature, applying them to the medium term planning of hydroelectric plants. After several experiments, two algorithms are selected as the best options. / Para um país como o Brasil, que tem seus recursos hídricos como maior fonte de geração de energia elétrica, a otimização da operação das usinas hidrelétricas é extremamente importante e vem sendo estudada de maneira recorrente. Adotando um conhecido modelo de decomposição temporal desse problema de otimização, esta dissertação propôe-se a realizar uma comparação entre os melhores algoritmos de otimização multiobjetivo da literatura atual, aplicado-os ao planejamento de médio prazo de usinas hidrelétricas. Após diversos experimentos realizados, dois algoritmos são selecionados como as melhores opções.
94

Integração dos problemas de carregamento e roteamento de veículos com janela de tempo e frota heterogênea. / Integration of loading and vehicle routing problems with time windows and heterogeneous fleet.

Danilo da Silva Campos 24 March 2008 (has links)
Este trabalho aborda um problema ainda não explorado na literatura denominado 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), que compreende resolver simultaneamente o roteamento e carregamento tridimensional de veículos considerando frota heterogênea e janela de tempo. Foi desenvolvido um algoritmo específico para resolver o problema, denominado 3DC. Neste algoritmo foram introduzidas algumas inovações, entre elas, um novo operador de busca local (k-IntensiveSwap) e uma nova heurística de carregamento de contêiner. O algoritmo foi comparado aos melhores resultados disponíveis na literatura para problemas particulares ao apresentado. Houve bom desempenho no caso do CLP (container loading problem), bom resultado na redução do tamanho de frota no caso do 3L-VRP (threedimensional loading vehicle routing problem) e desempenho superior ao problema mais complexo estudado, o 3L-VRPTW (three-dimensional loading vehicle routing problem with time windows). Finalmente, apresentou-se um conjunto de avaliação, instâncias e soluções, para o problema completo com frota heterogênea e janela de tempo. / This work presents a problem not treated yet on the literature referenced as 3L-FSMVRPTW (three-dimensional loading fleet sizing and mix vehicle routing problem with time windows), which deals simultaneously with vehicle routing and its three-dimensional loading considering heterogeneous fleet and time windows. The algorithm developed for the specific problem is called 3DC. This algorithm introduces a new local search operator called k-IntensiveSwap and a new container loading heuristic. The results are compared with the best-known results from literature for particular problems embeeded on the general problem presented. The quality of solution was good in comparison other methods for CLP (container loading problem), it has good results in terms of reduction fleet sizing in the case of 3L-VRP (three-dimensional loading vehicle routing problem) and as for 3L-VRPTW (threedimensional loading vehicle routing problem with time windows) the performance was very superior. Finally, it is presented a solution set as benchmark for future comparison with the general problem, with heterogeneous fleet.
95

Conhecimentos contábeis e gerenciais e a ocorrência de heurísticas: um estudo com estudantes de Ciências Contábeis / Accounting and management knowledge and the occurrence of heuristics: a study with students of Accounting Sciences

Franceschini, Rafaella Maranhão Kawata 30 August 2017 (has links)
Submitted by Neusa Fagundes (neusa.fagundes@unioeste.br) on 2018-02-27T19:27:15Z No. of bitstreams: 2 Rafaella_Franceschini2017.pdf: 1204392 bytes, checksum: 6149bee27a726b8f4afaabdf42ee8e5b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-27T19:27:15Z (GMT). No. of bitstreams: 2 Rafaella_Franceschini2017.pdf: 1204392 bytes, checksum: 6149bee27a726b8f4afaabdf42ee8e5b (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-30 / Decisions affect people's lives, just as they do in organizations. Managers make decisions based on intuition for business several times without being guided by management controls. Kahneman and Tversky (1979) created the Prospect Theory, also known as Perspective Theory, in the quest to explain the cognitive and heuristic biases of the decision-making process. The Prospect Theory is based on the fact that decision-making is not a strictly rational process, especially when the time for decision-making is limited. The managerial accountant by the very nature of the functions that are required to perform will require training very different from that required for the professional that acts in the formal accounting. This present study aimed to analyze whether the academic profile and the accounting and management knowledge influence the occurrence of heuristics. The theoretical reference presents the Decision Theory, Prospects Theory, availability heuristics, representativeness and anchoring, and accounting and management knowledge. For that, a field research was carried out with undergraduate students of the course of Accounting Sciences in the three campuses of a Public University of Paraná. The study sample consisted of 133 students, of which 78 were students in the first year and 55 in the fifth year. The research method used was a survey and the data were collected through questionnaires. Three research blocks were constructed, the first one on heuristics, the second on accounting and managerial knowledge, and the third on academic profile. To analyze the results, a descriptive data analysis, heuristic counting, factorial analysis and logistic regression were developed. The results show that the variables of the academic profile and the low managerial knowledge influence the presence of heuristics and that the undergraduate students presented low averages among the students of the first and fifth year, being that the students' lack of knowledge about aspects related to managerial accounting may be explaining the presence of heuristics among these students. As conclusion of the study in the academic profile the variables gender, age, professional experience and accounting performance presented a significant relation with the occurrence of heuristics, corroborating with the findings of the Prospects Theory. / Entende-se que decisões afetam a vida das pessoas, assim como acontece nas organizações. Os gestores tomam decisões pautadas na intuição ou no “faro” para os negócios, diversas vezes sem se pautar nos controles gerenciais. Kahneman e Tversky (1979) criaram a Teoria do Prospecto, também conhecida como a Teoria da Perspectiva, na busca de explicar os vieses cognitivos e heurísticos do processo de tomada de decisão. A Teoria do Prospecto está fundamenta em que a tomada de decisão não é um processo estritamente racional, em especial, quando o tempo para a tomada de decisão é limitado. O contador gerencial, pela própria natureza das funções que lhe são solicitadas a desempenhar, necessitará de formação bem diferente daquela exigida para o profissional que atua na contabilidade formal. O presente estudo teve por objetivo analisar se o perfil acadêmico e os conhecimentos contábeis e gerenciais influenciam a ocorrência de heurística. Quanto ao referencial teórico, apresenta a Teoria da Decisão, Teoria dos Prospectos, heurísticas da disponibilidade, representatividade e ancoragem e os conhecimentos contábeis e gerenciais. Para isso, foi realizada uma pesquisa de campo junto aos alunos de graduação do curso de Ciências Contábeis em três campi de uma Universidade Pública do Paraná. A amostra do estudo foi composta por 133 acadêmicos, sendo 78 estudantes do primeiro ano e 55 do quinto ano. O método de pesquisa utilizado foi o survey e os dados foram coletados por meio de questionários. Foram construídos três blocos de pesquisa, sendo o primeiro sobre heurística, o segundo sobre conhecimentos contábeis e gerenciais e o terceiro sobre perfil acadêmico. Para análise dos resultados desenvolveu-se a análise descritiva dos dados, contagem de heurísticas, análise fatorial e regressão logística. Os resultados apontam que variáveis do perfil acadêmico e o baixo conhecimento gerencial influenciam a presença de heurística e que os alunos de graduação apresentaram médias baixas entre os alunos do primeiro e quinto ano, sendo que, o pouco conhecimento dos alunos sobre aspectos relacionados à contabilidade gerencial podem estar explicando a presença de heurística entre esses alunos. Como conclusão do estudo do perfil acadêmico as variáveis gênero, idade, experiência profissional e atuação contábil apresentaram relação significativa com a ocorrência de heurística, corroborando com os achados da Teoria dos Prospectos.
96

Planejamento estático da expansão de sistemas de transmissão de energia elétrica utilizando otimização por enxame de partículas

Mendonça, Isabela Miranda de 02 August 2012 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-06-09T11:41:20Z No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-13T13:30:43Z (GMT) No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) / Made available in DSpace on 2016-07-13T13:30:43Z (GMT). No. of bitstreams: 1 isabelamirandademendonca.pdf: 1432328 bytes, checksum: 68aebf134272c7d3ee8daad48baf21cd (MD5) Previous issue date: 2012-08-02 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esta dissertação tem por objetivo a realização do planejamento estático da expansão de sistemas de transmissão de energia elétrica via otimização por Enxame de Partículas (EP). A metodologia proposta faz uso de um Algoritmo Heurístico Construtivo (AHC) que tem a finalidade de pré-selecionar as linhas candidatas à expansão mais relevantes, de modo a reduzir o espaço de busca e consequentemente, aumentar a eficiência do processo de otimização bioinspirado. Desta forma, a metodologia proposta pode ser dividida em duas etapas: (i) Obtenção do conjunto reduzido de rotas através do AHC, com o objetivo de identificar os caminhos relevantes à expansão e, assim, diminuir o espaço de busca; (ii) Utilização da otimização por enxame de partículas e das informações heurísticas advindas da primeira etapa, com o objetivo de encontrar o custo mínimo de expansão através de um número reduzidos de partículas. Em ambas as etapas a rede de transmissão é representada pelo modelo linearizado de fluxo de carga, onde as decisões de expansão são incorporadas ao problema através das equações originais do modelo CC. O critério de seleção da expansão é realizado através de heurística, de modo a evitar a explosão combinatória referente às alternativas de investimento. A metodologia proposta é aplicada ao sistema Garver e a dois sistemas reais equivalentes a região Sul e Sudeste do Brasil. / This dissertation aims at the realization of the static transmission network expansion planning (STNEP) of electric power systems using the Particle Swarm Optimization (PSO) method. The proposed methodology uses a Constructive Heuristic Algorithm (CHA) in order to pre-select the most relevant candidates lines for expansion, so as to reduce the search space and thereby increasing efficiency of the bioinspired optimization process. Thus, the proposed methodology can be divided into two steps: (i) Obtaining the reduced set of routes through the CHA, in order to identify relevant routes for expansion and thus reduce the search space; (ii) Using the Particle Swarm Optimization and heuristic information provided by the first stage, in order to find the minimum expansion cost using a reduced number of particles. In both stages the transmission network is represented by a linearized load flow model, where the expansion decisions are incorporated into the optimization problem using the original equations of the model DC. The selection of expansion criterion is done through heuristic in order to avoid combinatorial explosion associated with expansion alternatives. The proposed methodology is applied to the Garver system and two real equivalent South and Southeastern Brazilian systems.
97

Identificação de rotas relevantes para o planejamento estático da expansão de sistemas de transmissão de energia elétrica

Mendonça, Isabela Miranda de 19 August 2016 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-01-06T14:13:40Z No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) / Approved for entry into archive by Diamantino Mayra (mayra.diamantino@ufjf.edu.br) on 2017-01-31T11:27:02Z (GMT) No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) / Made available in DSpace on 2017-01-31T11:27:02Z (GMT). No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) Previous issue date: 2016-08-19 / Este trabalho apresenta uma nova estratégia visando à redução do espaço de busca e à inicialização do processo de otimização multimodal para resolução do problema de planejamento estático da expansão de sistemas de transmissão de energia elétrica. Para tanto, a metodologia proposta faz uso de um algoritmo heurístico construtivo baseado em índices de sensibilidade, no qual as decisões de expansão são relaxadas e representadas através da função tangente hiperbólica. Através da consideração de diferentes inclinações da função tangente hiperbólica, dentro de um intervalo previamente determinado, associadas aos principais índices de sensibilidade existentes na literatura é possível extrair um conjunto reduzido de alternativas de expansão. Sendo assim, com base nas informações heurísticas obtidas, é utilizado um algoritmo bioinspirado visando obter de um plano final de expansão para sistemas de transmissão de energia elétrica. A rede de transmissão de energia elétrica é representada por um modelo linearizado de fluxo de carga. Os planos finais de expansão obtidos pela metodologia proposta foram satisfatórios, mostrando que a utilização da função tangente hiperbólica agregada às heurísticas adotadas resultaram em uma estratégia eficiente de decisão. Foram analisados os sistemas Garver, IEEE 24 barras, Sul Brasileiro de 46 barras, e o Colombiano de 93 barras. Os resultados obtidos pela a metodologia proposta foram satisfatórios e de excelente qualidade. / This thesis presents a new strategy aimed at the search space reduction and initialization of the multimodal optimization process to solve the problem of static expansion planning of electric power transmission systems. The proposed methodology uses a constructive heuristic algorithm based on sensitivity indices, in which the expansion decisions are relaxed and represented through the hyperbolic tangent function. By considering different slopes of the hyperbolic tangent function, within a predetermined range, associated with the main existing sensitivity indices in the literature, it is possible to extract a reduced set of expansion alternatives. Thus, based on the heuristic information obtained, a bio-inspired algorithm is used to obtain a final expansion plan for electric power transmission systems. The electric power transmission network is represented by a linear load flow. The final expansion plans obtained by the proposed methodology were satisfactory, showing that the use of the hyperbolic tangent function added to the adopted heuristics yielded an effective decision strategy. The Garver system, IEEE 24 bus system, real equivalent system in southern Brazil 46 bus and real Colombian system 93 bus were analyzed. The results obtained by the proposed method were satisfactory with excellent quality.
98

Análise, proposição e solução de modelos para o problema integrado de dimensionamento de lotes e sequenciamento da produção / Analysis, proposition and solution of models for the simultaneous lot sizing and scheduling problem

Willy Alves de Oliveira Soler 21 November 2017 (has links)
Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.
99

Problemas de Corte e Empacotamento: Uma abordagem em Grafo E/OU / Cutting and packing problems: an AND/OR-Graph approach

Andréa Carla Gonçalves Vianna 19 December 2000 (has links)
O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.
100

Otimização do problema de roteamento de veículos capacitado usando algoritmos genéticos com heurísticas e representações cromossômicas alternativas

Lima, Stanley Jefferson De Araujo 27 January 2015 (has links)
Submitted by Nadir Basilio (nadirsb@uninove.br) on 2015-07-17T16:00:19Z No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) / Made available in DSpace on 2015-07-17T16:00:19Z (GMT). No. of bitstreams: 1 Stanley Jefferson de Araujo Lima.pdf: 1500605 bytes, checksum: 2aec7d5c11c9781ce7f70eb2019c01f4 (MD5) Previous issue date: 2015-01-27 / In recent years, the Vehicle Routing Problem (VRP) has attracted an increasing attention from researchers due to the great difficulty of its solution and its presence in various practical situations. As consequence, there has been great effort to develop more robust, agile and flexible algorithms that can be modeled according to the scenario that describes the problem. The Capacitated Vehicle Routing Problem (CVRP) is a version of VRP and consists in determining a set of routes to be followed by a fleet of homogeneous vehicles, which must serve a set of customers. The objective is to minimize the total cost of the routes subject to the following restrictions: i) routes must start and end in the same distribution center; ii) each customer must be visited once and its demand must be met in full by only one vehicle and iii) the sum of customers' demands included in a route cannot exceed the vehicle capacity. The CVRP belongs to the class of NP-hard problems, that is, problems whose the solution usually requires non-polynomial complexity time algorithms and because of this are usually resolved with the use of heuristic and metaheuristics algorithms. In this work, it was investigated the optimization of CVRP using Genetic Algorithm (GA) with alternative chromosome representations and heuristics. To this end, three strategies, each one employing a different model of chromosome representation for encoding solution in AG were proposed. In addition, the heuristics of Gillett and Miller to generate solutions that are included in the initial population of GA and Hill-climbing for refinement of GA solutions, after a number of generations without improvement, were adopted. In the performed experiments, the results obtained by the proposed strategies were compared with each other and also with the best results found in the literature for a set of known instances. These experiments showed that the proposed strategies provided good results with respect to quality of solutions well as the computational cost. In addition, it was possible to evaluate the viability of each employed chromosome representation and the contribution of the heuristics in the convergence process of GA. / Nos últimos anos o Problema de Roteamento de Veículos (PRV) tem atraído cada vez mais a atenção de pesquisadores devido à grande dificuldade de solução e sua presença em várias situações do cotidiano. Em decorrência disso, tem havido um grande esforço para desenvolver algoritmos cada vez mais robustos, ágeis e flexíveis e que possam ser modelados com base no cenário que descreve o problema. O Problema de Roteamento de Veículos Capacitado (PRVC) é uma versão do PRV e consiste em encontrar um conjunto de rotas a serem seguidas por uma frota de veículos homogêneos, os quais devem atender a um conjunto de clientes. O objetivo é minimizar o custo total das rotas respeitando as seguintes restrições: i) as rotas devem iniciar e terminar no mesmo centro de distribuição; ii) cada cliente deve ser visitado uma única vez e sua demanda deve ser atendida integralmente por apenas um veículo e iii) a soma das demandas dos clientes incluídos em uma rota não pode exceder a capacidade do veículo. Problemas desta natureza podem ser classificados como NP-Hard, ou seja, possuem ordem de complexidade não polinomial e normalmente são resolvidos com uso de algoritmos heurísticos e meta-heurísticos. Neste trabalho investigou-se a otimização do PRVC usando Algoritmo Genético (AG) com representações cromossômicas e heurísticas alternativas. Para tanto, foram propostas três estratégias, cada uma delas empregando um modelo diferente de representação cromossômica para codificação da solução no AG. Além disso, foram empregadas as heurísticas de Gillett e Miller para gerar soluções que são incluídas na população inicial do AG e Subida/Descida de Encosta para refinamento das soluções, após um certo número de gerações sem melhoria. Nos experimentos realizados, os resultados obtidos pelas estratégias propostas foram comparados entre si e também com os melhores resultados encontrados na literatura para um conjunto de instâncias conhecidas. Pode-se constatar, a partir desses experimentos, que as estratégias apresentaram bons resultados tanto no que tange a qualidade das soluções quanto ao tempo computacional dispendido. Em adição, foi possível avaliar a viabilidade de cada uma das representações cromossômicas empregadas, além da contribuição das heurísticas no processo de convergência do ag.

Page generated in 0.0797 seconds