Cadeias de suprimentos podem ter operações seguindo diferentes estratégias de distribuição e a utilização de cada uma dessas estratégias pode resultar em diferentes operações e custos. A estratégia de cross-docking auxilia na redução dos custos de distribuição de produtos, consolidando cargas, e a redução de tempo e custos de armazenamento, uma vez que o tempo máximo de estoque permitido pela estratégia é de cerca de 24 horas. O objetivo deste trabalho é apresentar um modelo para o problema de cross-docking, em que cargas são entregues e reorganizadas de forma a atender a outras cargas que são coletadas e garantir que as janelas de tempo para início das operações sejam atendidas. Devido à falta de instâncias para o problema disponíveis na literatura, buscou-se gerar um benchmark e disponibilizá-las à comunidade científica. Uma vez que o problema é de difícil solução exata, um método heurístico para a resolução do problema foi desenvolvido. Os resultados mostraram que o modelo proposto resulta em boas soluções quando comparado ao modelo da literatura. O estudo de calibração do software IBM CPLEX mostrou que a calibração dos parâmetros pode resultar em melhores soluções e, por fim, a matheurística se mostrou competitiva com o CPLEX, principalmente para cenários em que a proporção de entregas e coletas diverge. / Supply chains may have operations which follow different distribution strategies and each one of these strategies may result in different operations and costs. The Cross-docking strategy helps to reduce the products distribution costs by consolidating loads and reducing storage costs as the maximum inventory time is approximately 24 hours. The aim of this research is to present a model for the cross-docking problem where loads are delivered and reorganized so as to cater for other loads that are collected and ensure that time windows are respected. Due to the lack of instances available in the literature, a benchmark was generated and was made available to the scientific community. As the problem is difficult to obtain the exact solution, a heuristic method was developed. The results showed that the proposed model has good solutions when compared to the literature model. A study of the IBM CPLEX software showed that tuning can result in better solutions and the matheuristcs was competitive with the software, mainly in scenarios where deliveries and pickups are very different.

Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching). / This study focuses a job scheduling problem in a flow shop with some specific features, which, all together, make it different from the usual flow shop scheduling problems. There are N jobs to be processed in M different machines and each job has a particular route, skipping, eventually, one or more machines; each job should be finished within a time interval, called time window, and there are penalties for earliness and tardiness. This is a combinatorial problem for which, in the extreme case, there are (N!)^M solutions, belonging to NP-Hard class. In this study, a mathematical model is proposed for representing the problem; the CPLEX solver is used for solving the mixed integer linear problem obtained. Given the computational complexity of the model, heuristic procedures are proposed in order to solve large- scale instances of this problem. Combined procedures, using an initial solution obtained by a proposed heuristic and the mathematical model, either using the general branching procedure of CPLEX or a specific local branching procedure, are also shown.

Esta dissertação trata do planejamento do abastecimento de última milha em centros urbanos, propondo métodos para agrupar pedidos de clientes em programação de entregas. Neste estudo, é considerado que o frete pago ao transportador em uma rota é definido pela distância direta do ponto de entrega mais distante do depósito em contraposição à distância total da rota que é usual na literatura sobre problemas de roteirização de veículos. Além disso, também são consideradas categorias, conjunto de produtos similares, que não podem ser transportadas juntas por não serem compatíveis entre si. O objetivo do problema proposto é determinar o agrupamento e sequenciamento de pedidos em roteiros de veículos de acordo com as características operacionais descritas acima, utilizando uma frota homogênea de veículos capacitados que parte de um depósito, de tal forma que toda a demanda seja atendida com o menor frete possível. Para resolução desse problema são propostas uma formulação matemática para obtenção de soluções exatas e a implementação da heurística \"Multi Start Perturbation Tabu\" (MSPT) que é composta das metaheurísticas \"Greedy Randomized Adaptive Search Procedure\" (GRASP), \"Tabu Search\" (TS) e \"Iterated Local Search\" (ILS) para obtenção de soluções heurísticas. Os resultados experimentais indicam que a MSPT é competitiva com os resultados do método exato com até 5 horas de processamento utilizando os recursos computacionais de alto desempenho do Laboratório de Computação Científica Avançada (LCCA) da Universidade de São Paulo. / This dissertation addresses the planning of the last mile supply in urban centers and proposes methods to group customer orders into shipments. In this study, freight paid to the carrier on a route is defined as the direct distance from the point of delivery that is furthest from the depot as opposed to be defined as the total distance of the route which is commonly found in the literature on vehicle routing problems. In addition, it is also considered categories, a set of similar products, which cannot be transported together because they are not compatible with each other. The objective of the proposed problem is to determine the grouping and sequencing of orders into vehicle shipments according to the operational characteristics described above, using a homogeneous fleet of capacitated vehicles that is located in a depot, in such a way that all the demand is delivered with the lowest freight possible. To solve this problem, it is proposed a mathematical formulation to obtain exact solutions and the implementation of the Multi Start Perturbation Tabu (MSPT) heuristic that is composed of the Greedy Randomized Adaptive Search Procedure (GRASP), Tabu Search (TS) and \"Iterated Local Search\" (ILS) for heuristic solutions. Finally, the experimental results indicate that the MSPT is competitive with the outcomes of the exact method with up to 5 hours of processing using the high performance computational resources of the Advanced Scientific Computation Laboratory (LCCA) of the University of São Paulo (USP).

O setor de fundições é importante para a economia, pois produz componentes básicos para muitos outros setores, de modo que seu bom desempenho tem repercussão nos demais. Um modelo de programação inteira mista para uma fundição de mercado de pequeno porte, que visa principalmente minimizar atrasos na entrega dos pedidos, foi proposto na literatura. Neste trabalho é feito um estudo do modelo e é proposta uma nova abordagem, independente de qualquer software comercial, baseada na decomposição do problema em dois subproblemas: o planejamento da produção das ligas e o planejamento da produção dos itens. Ambos foram resolvidos por uma heurística lagrangiana baseada em transferêrencias. Testes computacionais mostraram que a abordagem proposta é capaz de gerar soluções de boa qualidade, em tempo computacional aceitável / The foundry sector is important to the economy as it produces basic components for many other sectors, to such an extent that its performance has a repercussion in other sectors. A recently published mixed integer-programming model for small market-driven foundries, which aims to minimize delays when delivering orders, was proposed in the literature. In this work, a study of this model was undertaken and a new approach is put forward, regardless of any commercial software, based on dealing with the problem in two sub problems: production planning of alloys and production planning of items. Both sub problems were solved by a Lagrangian heuristic based on transfers. Computational tests show that the approach proposed is able to generate solutions of good quality in acceptable computational time

A programação concorrente é cada vez mais utilizada nos sistemas atuais com o objetivo de reduzir custos e obter maior eficiência no processamento. Com a importância da programação concorrente é imprescindível que programas que implementam esse paradigma apresentem boa qualidade e estejam livres de defeitos. Assim,diferentes técnicas e critérios de teste vêm sendo definidos para apoiar a validação de aplicações desenvolvidas nesse paradigma. Nesse contexto, a geração automática de dados de teste é importante, pois permite reduzir o custo na geração e seleção de dados relevantes. O uso de técnicas meta-heurísticas tem sido uma área de grande interesse entre os pesquisadores para geração de dados, pois essas técnicas apresentam abordagens aplicáveis a problemas complexos e de difícil solução. Considerando esse aspecto, este trabalho apresenta uma abordagem de geração automática de dados para o teste estrutural de programas concorrentes em MPI (Message Passing Interface). A meta-heurística usada foi Algoritmo Genético em que a busca é guiada por critérios de teste que consideram características implícitas de programas concorrentes. O desempenho da abordagem foi avaliado por meio da cobertura dos dados detestes, da eficácia em revelar defeitos e do custo de execução. Para comparação, a geração aleatória foi considerada. Os resultados indicaram que é promissor usar geração de dados de teste no contexto de programas concorrentes, com resultados interessantes em relação à eficácia e cobertura dos requisitos de teste. / Concurrent programming has been increasingly used in current systems in order to reduce costs and obtain higher processing efficiency and, consequently, it is expected that these systems have high quallity. Therefore, different techniques and testing criteria have been proposed aiming to support the verification and validation of the concurrent applications. In this context, the automated data test generation allows to reduce the testing costs during the generation and selection of data tests. Metaheuristic technique has been widely investigated to support the data test generation because this technique has presented good results to complex and costly problems. In this work, we present an approach to the automated data test generation for message passing concurrent programs in MPI (Message Passing Interface). The generation of data test is performed using the genetic algorithm metaheuristic technique, guiding by structural testing criteria. An experimental study was conducted to evaluate the proposed approach, analyzing the effectiveness and application cost. The results indicate that the genetic algorithm is a promising approach to automated test data generation for concurrent programs, presenting good results in relation to effectiveness and data test coverage.

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.

Este trabalho trata do problema de roteirização de veículos para o abastecimento de linhas de produção, o qual pode ser entendido como uma particularização do problema clássico de roteirização de veículos (VRP Vehicle Routing Problem). Neste problema, peças estão armazenadas em um estoque central, chamado de supermercado, de onde são transferidas para pontos de uso localizados ao longo da linha de produção. O ritmo de fabricação na linha de produção é suposto constante, o que torna periódica a necessidade de reposição das embalagens com peças. Uma frota de rebocadores transporta as embalagens, dispostas sobre plataformas com rodas puxadas pelo mesmo e configurando um comboio. O objetivo do problema é roteirizar a frota de rebocadores, maximizando sua utilização e garantindo o atendimento da demanda gerada pela linha de produção. O problema é comum a muitas empresas de manufatura de bens de consumo e possui impacto direto nos custos operacionais. A literatura sobre o tema é escassa e as soluções empregadas na indústria habitualmente se baseiam na experiência prática de operadores ou responsáveis pela movimentação de materiais. Este trabalho propõe uma heurística para obtenção de uma solução para o problema, baseada em métodos de inserção. A heurística proposta foi aplicada a um caso na indústria automobilística e a comparação entre a solução obtida e aquela formulada por operadores demonstrou ganho no número de rotas. / This work studies the routing of vehicles for material delivery to assembly lines, which consists of a generalization of the classic Vehicle Routing Problem (VRP). In this problem, parts are stored in central depot called supermarket and from where they are distributed to points of use placed along the production line. Production rate in the assembly line is considered constant, which means that parts are delivered to points of use periodically. A fleet of tow cars transfers the boxes or containers of parts using wheeled towed carts. The objective of this problem is to route the fleet of the tow cars maximizing their utilization and fulfilling the assembly line demand for parts. This problem is common to several companies and has direct impacts in material handling costs. The theme is poorly explored in routing studies and many companies use operator experience to configure tow cars routes. This work proposes a heuristic based on insertion methods to find a solution for the problem. The heuristic was applied to a real problem and resulted in the reduction of the number of routes when compared to former operator solution.

O problema de roteirização periódica de veículos pode ser considerado como uma generalização do problema clássico de roteirização devido a duas características próprias: um período de planejamento maior que um dia, em que os veículos fazem diversas viagens, e freqüências de visitas associadas a pontos a serem servidos. Esse tipo de problema pode ter muitas aplicações práticas. Atualmente, algumas indústrias automobilísticas brasileiras já utilizam um sistema de coleta que se baseia na idéia de roteirização periódica, com a finalidade de reduzir o estoque de peças. Assim como os problemas originais de roteirização de veículos, o problema aqui tratado é também difícil de ser resolvido, sendo impossível o uso de algoritmos exatos para a obtenção de uma solução ótima para o tamanho de problemas encontrados na prática. Isso motivou o estudo, que direcionou seus esforços na exploração de novas estratégias de solução para esse problema através de novas abordagens, de modo que houvesse um aumento na qualidade de soluções e uma diminuição do tempo de processamento computacional. Dois procedimentos diferentes foram propostos para a alocação dos clientes aos dias de visitas: uma heurística de inserção seqüencial que visa equilibrar os esforços dos diferentes dias do período de planejamento, e uma heurística baseada em algoritmos genéticos. As rotas diárias são construídas através da utilização do algoritmo de economias de Clarke e Wright, que permite a obtenção de boas soluções em tempos de processamento curtos. Experimentos computacionais são realizados para a avaliação da eficiência de cada uma das heurísticas propostas através da utilização de benchmarks retirados da literatura e problemas-teste gerados aleatoriamente, e os resultados são também comparados aos anteriormente mostrados na literatura. / The period vehicle routing problem can be viewed as a generalization of the classic vehicle routing problem due to two singular features: a planning period longer than one day in which vehicles make several trips and frequencies of visit associated to points to be serviced. This type of problem may arise in different practical applications. Nowadays, some Brazilian automaker industries are already utilizing a collect system based on the idea of the period routing in order to reduce parts inventory. Similarly to the original vehicle routing problem, the period vehicle routing problem is also hard to solve, making it impossible to use exact in order to obtain an optimal solution for problem sizes found in practice. This motivated this research study, which directed its efforts to the exploration of new strategies of solution through new reasoning, leading to an increase in the quality of the solution and a decrease in the computational processing time. The proposed heuristics are composed of three consecutive stages: (i) assigning customers to days of visit while respecting their given frequencies, (ii) building routes that serve all customers assigned to each day of the planning horizon, and (iii) improving the obtained solution. Despite the distinction between the stages, we managed to take into consideration the integration among the three decisions. Two different procedures were proposed to the assignment of customers to days of visit: a sequential insertion heuristic that aims to balance the workload among different days in the time horizon, and a heuristic based on genetic algorithms. The daily routes are then constructed by using the Clarke and Wright\'s savings algorithm, which allows good solutions to be obtained in short processing times. Computational experiments are made in order to evaluate the efficiency of each proposed heuristic using both benchmark problem sets from the literature and randomly generated problems as well, and the results are compared to the previously reported in the literature.