Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T17:30:49Z (GMT). No. of bitstreams: 1 Yamashita_DeniseSato_D.pdf: 2970003 bytes, checksum: 72c1667962da475bb3a8d324efecf62b (MD5) Previous issue date: 2003 / Doutorado

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade. / Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality. / Doutorado / Doutor em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-20T15:03:57Z (GMT). No. of bitstreams: 1 Mazzini_Renata_M.pdf: 7362215 bytes, checksum: dfbf069e9e5adbb89d7e472205a48ba8 (MD5) Previous issue date: 1995 / Resumo: Com a popularização do conceito de produção "Just in Time", surgiu um interesse generalizado pelo controle de geração de estoques, por parte dos pesquisadores da área de programação da produção, pois foi introduzida a noção de que esse controle é tão importante quanto cumprir compromissos relativos a datas de entrega contratadas. Entretanto, desde o início do século, altos níveis de estoques de produto acabado, ou em processamento, já representavam uma situação de risco financeiro. Neste trabalho estuda-se o problema de programação da produção que considera custos internos (estoques) e externos (clientes) envolvidos no processamento de tarefas por uma máquina. Esse problema consiste na minimização do avanço e atraso ponderados, com relação a datas de entrega. A resolução desse problema envolvenão somente a determinação de uma seqüência de processamento, mas também dos instantes de início de todas as tarefas, inserindo-se, eventualmente, intervalos ociosos entre elas. Propõe-se um procedimento heurístico para a determinação do programa de produção desejado. São apresentados e analisados resultados computacionais de testes em instâncias com até 80 tarefas / Abstract: With the increasing popularity of the Just in Time production concept, researchers in the scheduling area became more interested in stock controI, due to the notion that this control is as important as meeting the agreed delivery dates. However, since the beginning of this century, high stock Ievels of finished goods or work in process, have represented great financial risks. The scheduling problem, which considers internal (stocks) and external (costumers) costs involved in the processing of jobs in one machine, is studied in this work. This problem consists of minimizing weighted earliness and tardiness with respect to due dates. SoIvingthis problem involves not only the search for a sequence of jobs to be processed, but the determination of all starting times and the insertion of idIetimes, when necessary. A heuristic procedure is proposed to give the aimed schedule. ComputationaI results are presented and analyzed. The tests were made in instances with up to 80 jobs / Mestrado / Mestre em Engenharia Elétrica

Orientador: Paulo Morelato França, Michel Gendreau / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T19:58:07Z (GMT). No. of bitstreams: 1 Muller_FelipeMartins_D.pdf: 8020755 bytes, checksum: 031f8c626f59dd5d71d81ea4412194fb (MD5) Previous issue date: 1993 / Resumo: Não informado / Abstract: This thesis deals with the problem of scheduling n jobs on m identical parallel machines with the objective of minimizingthe total execution time (makespan).Two cases are considered: in the first one the jobs are independent and the processing times are positive integers; in the second case we have sequence dependent times. For the first case we propose a 3-PHASE heuristic: initial assignment, job reassignment and job interchange. The 3-PHASE algorithm is compared with three other heuristics chosen from the literature by its good known average performance. The new heuristic is also compared with an exact method in order to evaluate the quality of the solutions obtained by the heuristic. Extensive computational tests were performed for randomly generated problems and they exhibited that the 3-PHASE heuristic yields average solution values at least as good as (with only one exception) those obtained with any of the three alternative heuristics used for comparison. The 3-PHASE algorithm found the optimal solution in around 70% of the problems for wich the optimal solution were known. In the second case we also propose a three phase heuristic: initial assignment, tabu phase and post-optimization phase. This algorithm rruUcesuse of tabu search techniques and general insertion procedure called GENIUS, originally designed for the Traveling Salesman Problem and properly adapted for the scheduling problem. A nearest neighbour procedures was also adapted for the scheduling problem and was used in comparisons with the proposed method. An exact method was developed for the problem in question. Tests were performed in randomly generated problems in a structured fashion and in a non-structured fashion. Results for both cases are presented and commented. / Doutorado / Doutor em Engenharia Elétrica

Este trabalho apresenta um estudo sobre a razão assintótica de pior caso para alguns algoritmos aproximados utilizados para solucionar o problema de Bin Packing unidimensional ( BPP). Este é um problema clássico de otimização combinatória que serve de modelo para uma série de problemas que ocorrem no mundo real. No BPP, dada uma lista com n itens de tamanhos no intervalo (0,

O objetivo deste trabalho é a implementação e análise de técnicas para aceleração do aprendizado por reforço em sistemas com múltiplos objetivos. Problemas com múltiplos objetivos, por sua vez, podem ser descritos de várias formas diferentes. O foco aqui é naqueles casos em que um único agente deve aprender simultaneamente e de modo online várias sub-tarefas independentes resultantes de uma decomposição a priori do problema em questão. O agente será responsável pelo aprendizado autônomo de um processo de seleção de ações em que pode ocorrer competição entre as várias sub-tarefas, cada uma das quais representada por um processo decisório distinto. O projeto envolve uma análise empírica baseada em resultados prévios da literatura, seguida de um estudo de variantes mistas de maximização de utilidade e minimização de custos associados às ações propostas pelos processos decisórios de Markov que compõem as sub-tarefas. Como resultado dessa análise são propostas as técnicas de aceleração do aprendizado baseadas em heurísticas testadas e estudadas no contexto de problemas de objetivos simples. Os resultados experimentais obtidos indicam que tais heurísticas adaptadas e aplicadas às políticas de ações dos MDPs são capazes de proporcionar aceleração da convergência dos algoritmos de aprendizado autônomo em problemas com múltiplos objetivos.

O aprendizado por reforço é uma técnica muito conhecida para a solução de problemas quando o agente precisa atuar com sucesso em um local desconhecido por meio de tentativa e erro. Porem, ela não é eficiente o bastante para ser usada em aplicações com exigências do mundo real devido ao tempo que o agente precisa para o aprendizado. Este trabalho propõe um mecanismo para a aceleração do aprendizado por reforço, utilizando transferência do aprendizado com a combinação de varias técnicas distintas, como, redes neurais artificiais, aprendizado por reforço, raciocínio baseado em casos e uso de heurística para aceleração do aprendizado, utilizando a semelhança entre domínios. Com o objetivo de avaliar o mecanismo proposto, implementou-se o algoritmo Q-Learning Acelerado por Transferência de Aprendizado (Q-Learning Accelerated by Transfer Learning - Q-LATL) que estende o conhecido algoritmo Q-Learning utilizando métodos de aproveitamento de casos para extração da função heurística, métodos estes que podem ser usados para a aceleração do aprendizado por reforço. Foram realizados experimentos utilizando a transferência de aprendizado para solucionar problemas em diversos domínios. Os resultados experimentais deste trabalho permitem concluir que a transferência do aprendizado, na forma como aplicada neste trabalho, melhora o desempenho do algoritmo de aprendizado por reforço utilizado.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-14T11:00:06Z No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) / Made available in DSpace on 2017-02-14T11:00:06Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1892866 bytes, checksum: 725886f14f97ae6598868af898629ce4 (MD5) Previous issue date: 2016-06-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Transporte reativo a demanda, na língua inglesa Demand Responsive Transport (DRT) é uma forma de prover transporte, seja para passageiros ou mercadorias, na qual o serviço é ativado sob demanda. Ao contrário dos serviços tradicionais de transporte público, os quais operam por meio de rotas, horários e pontos de atendimento fixos, os serviços DRT operam de formas flexíveis ou semi-flexíveis. Para utilização do serviço, passageiros devem enviar requisições, nas quais informam locais e horários desejados de embarque e desembarque. A partir das requisições, ocorre o processo de roteamento dos veículos e agendamento dos atendimentos. Usuários provenientes de requisições diferentes, mas com características em comum, seja área e/ou momento de atuação do serviço podem ser atendidos simultaneamente pelo mesmo veículo. Devido a esta forma de prover transporte, para alguns pesquisadores do tema, serviços DRT são conside- rados uma forma intermediária de transporte, situada entre os serviços de transporte público (caráter geral e compartilhado) e os táxis (personalizado e individual) e con- tribuem direta e indiretamente na redução de alguns dos principais problemas comuns em centros urbanos, tais como: excesso de veículos nas vias trafegando com baixa ocu- pação, poluição, congestionamentos, exclusão social relacionada ao acesso a meios de transporte público e etc. Neste trabalho, foram propostos modelos de programação linear mista, abordagens multiobjetivo e abordagens heurísticas para otimização de um serviço DRT introduzido na literatura, o qual foi explorado para os casos estático e dinâmico. As abordagens apresentadas foram avaliadas por meio de experimentos computacionais e testes estatísticos sobre conjuntos de instâncias com diferentes carac- terísticas, que indicaram as melhores abordagens para cada situação. / Heuristic approaches to optimizing a demand responsive transport. Ad- viser: André Gustavo dos Santos. Demand responsive transport is a way to provide transportation for passengers or go- ods, in which the service is activated on demand. Unlike traditional public transport services, which operate through fixed routes, schedules and service points, DRT ser- vices operate in flexible or semi-flexible way. In order to use the service, passengers must submit requests, in which they inform the desired local and times of departure and arrival. The routing of vehicles and the scheduling of calls are performed based on those requests. Users from different requests, but with common features like area and/or moment of the service can be served simultaneously by the same vehicle. Due to this way of providing transport, some researchers consider the DRT services an inter- mediate form of transport, situated between public transport services (general purpose and shared) and taxis (custom and individual) and contribute directly and indirectly in reducing some of the major common problems in urban centers, such as: too many vehicles traveling on the roads with low occupancy, pollution, congestion, social exclu- sion related to access to public transportation, etc. In this work, we proposed mixed linear programming models, multi-objective approaches and heuristics approaches for optimization of a DRT service from the literature, which was exploited for the static and dynamic case. The approaches presented were evaluated through computational experiments and statistical tests using sets of instances with different characteristics, showing the best approaches for each situation.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-08-31T12:45:53Z No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) / Made available in DSpace on 2017-08-31T12:45:53Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2856120 bytes, checksum: f1801ace46848b5b50cb84b2a9f19634 (MD5) Previous issue date: 2017-03-07 / Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas. / In this work we address two vehicle routing problems with pickup and delivery and loading constraints. Firstly, this work addresses the Double Vehicle Routing Pro- blem with Multiple Stacks (DVRPMS). Posteriorly we formulate and propose the Double Routing Vehicle Problem with Multiple Stacks and Heterogeneous Demand (DVRPMSHD), referring to a more realistic case of the DVRPMS in which custo- mers have multiple and heterogeneous demands and all demand of a same client must be transported by a single vehicle. In both problems, the objective is to de- termine routes for a fleet of vehicles to meet the demand of a set of customers so that the distance travelled by the vehicles is the minimum possible, respecting some loading constraints imposed by the vehicles’ storage stacks. All products located in a pickup region must be collected and then delivered to a delivery region by vehicles. The pickup and delivery regions are largely separated so that all products must be loaded before any unloading. The DVRPMS was approached mainly by four heuristic methods, which were tested in several instances and compared to the exact and heuristic methods already present in literature. The computational experiments showed the efficiency of the proposed algorithms, obtaining solutions of better quality than those presented in the literature for most of the instances and with low computational time. The DVRPMSHD was approached by an exact method and a heuristic method. Initially, the implemented branch-and-price exact method presented higher efficiency compared to the proposed mathematical formu- lation for the problem. The heuristic method overcame the results achieved by the branch-and-price for most of the created instances.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2016-05-17T20:09:39Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Approved for entry into archive by Morgana Andrade (morgana.andrade@ufes.br) on 2016-06-03T14:24:51Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / Made available in DSpace on 2016-06-03T14:24:51Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Tese Leandro Colombi.pdf: 1600437 bytes, checksum: d40bc605230b5d5995a431dc205d03a6 (MD5) / CNPQ / O Problema de Grooming de Tráfego (Traffic Grooming Problem - TGP) trata da combinação eficiente de demandas de baixa velocidade em canais de alta velocidade. Com o objetivo de melhorar a utilização da capacidade da rede, o TGP é frequentemente estudado com métodos de otimização usando como função objetivo a minimização do número de transceptores eletro-´ópticos. Por´em, como o TGP pertence á classe de problemas NP-Completo, soluções ótimas com um pequeno tempo computacional são possíveis apenas para redes pequenas (por exemplo, 6 nós). Neste trabalho são propostos novos modelos de Programação Linear Inteira (Integer Linear Programming - ILP), uma heurística e uma solução híbrida para o TGP em redes translúcidas de médio porte (aproximadamente 12 n´os). Inicialmente, são propostos dois modelos ILP para o TGP, um baseado em formulação nó-enlace e outro em enlace-caminho, de forma que seus resultados foram comparados e usados como base para modelos mais complexos. No método híbrido é usada uma heurística para selecionar os caminhos ópticos (i.e., a topologia virtual) e um modelo ILP para rotear de maneira eficiente as demandas de tráfego sobre as topologias física e virtual. A aplicação desse método permitiu, primeiramente, a quantificação dos benefícios dos caminhos ópticos transparentes, em termos da redução do número de transceptores. Além disso, a diminuição do processamento eletrônico do tráfego de trânsito também foi analisada. Para redes maiores, a fase ILP no método híbrido ainda continua sendo um gargalo para as soluções ótimas, sendo assim necessárias soluções totalmente heurísticas. Este trabalho mostra que soluções eficientes podem ser encontradas usando métodos heurísticos simples e rápidos, onde não foi necessário o aumento do custo computacional para o ajuste de parâmetros complexos relacionados a heurística. Finalmente é proposta uma integração do TGP com sobrevivência. Neste trabalho são propostos modelos ILP para formulação de um método iterativo capaz de oferecer uma proteção incremental em uma rede em malha com a minimização do número de transceptores. Além disso, são estudados dois métodos para a proteção da interconexão de redes multi-anel com dois nós de interconexão, Anel Virtual e Drop&Continue. Para essa investigação os resultados numéricos incluem o grooming de tráfego para diferentes cenários como, configurações opaca vs. translúcida e crescimentos de tráfego inter-anel vs. intra-anel. / The Traffic Grooming Problem (TGP) consists in how to arrange low-bandwidth connection requests into high-capacity lightpaths efficiently. TGP solution aims at improving network capacity utilization. The minimal number optoelectronic transceivers that enable accommodating traffic demands is often used as the objec- tive function for solving TGP. However, TGP belongs to a class of NP-hard problems and optimal solutions are only possible to be found within feasible processing time for small networks (e.g., 6 nodes). This work proposes novel Integer Linear Pro- gramming (ILP) models, heuristic and a hybrid solution to TGP for medium-sized (i.e., around 12 nodes) translucent networks. Initially, ILP models using node-link and link-path paradigms are proposed and their solutions are compared. These models lay the foundations for more complex models addressing issues on network design. A hybrid method is then proposed. It makes use of a heuristic for selecting lightpaths (i.e., the virtual topology) and an ILP model to route the traffic demands over both physical and virtual topologies efficiently. The practical implications of such approach is that it allows, for the first time, the quantification of benefits of transparent lightpaths in terms of transceiver count reduction. Moreover, the miti-gation of transit traffic processing in the electronic layer is also analyzed. For large networks the ILP phase in the hybrid approach again becomes the bottleneck for optimal network design and a fully heuristic solution is necessary. This work shows that efficient solutions can be found through a simple and fast tool for network design without the need of complex parameter tuning, as comparisons with results obtained from solving the hybrid model. Finally, the integration of TGP with survivability is proposed. This work puts forward ILP models for an iterative method using two ILP models to design networks with incremental protection with minimal num- ber of transceivers in mesh networks. Dual Node Interconnected (DNI) multi-ring topologies are studied under inter-ring traffic protection using Virtual Ring (VR) and Drop and Continue (D&C) strategies. Results compare optimal solutions that take into account traffic grooming for different network scenarios including opaque vs. translucent configurations and inter vs. intra traffic growth.