Esta tese estuda a implementação de heurísticas e da metaheurística scatter search (SS) em um problema de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas (Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries – HFVRPTWSD). O HFVRPTWSD é uma combinação do problema de roteirização com frota heterogênea (HFVRP), problema de roteirização de veículos com janelas de tempo (VRPTW) e problema de roteirização com entregas fracionadas (VRPSD). O problema é baseado em um único depósito, a demanda dos clientes pode ser maior que a capacidade dos veículos e, além das restrições de janelas de tempo, há também restrições de capacidade dos veículos e restrições quanto ao tipo de veículo. O VRPSD foi introduzido na literatura por Dror e Trudeau em 1989. No problema de roteirização de veículos com entregas fracionadas, cada cliente pode ser abastecido por mais de um veículo, enquanto no problema clássico de roteirização de veículos (VRP), cada cliente é atendido por um único veículo. Desta forma, para o VRPSD, além dos roteiros de entrega, deve-se determinar a quantidade entregue a cada cliente em cada veículo. Todos os problemas de roteirização com entregas fracionadas encontrados na literatura (VRPSD e suas extensões) têm como característica frota homogênea. O problema estudado neste trabalho difere, portanto, de todos os problemas de roteirização com entregas fracionadas da literatura, pois tem, como característica, frota heterogênea. O mesmo raciocínio vale para problemas de roteirização de veículos com frota heterogênea. Os modelos são aplicados em uma rede de varejo no Brasil que é abastecida a partir de um centro de distribuição. A rede compõe um total de 519 lojas distribuídas em 12 estados do país. As heurísticas e a metaheurística scatter search também são aplicadas em três conjuntos de problemas encontrados na literatura (SOLOMON, 1987; HO E HAUGLAND, 2004; LIU E SHEN, 1999), com o objetivo de avaliar o desempenho dos algoritmos para cada problema. O problema consiste em determinar, a cada dia, como alocar os caminhões às lojas, a quantidade de carga em cada caminhão a ser entregue em cada uma das lojas, qual o melhor roteiro e o tempo de início de atendimento do primeiro cliente da rota, de forma a minimizar o custo total de distribuição, garantindo que a demanda das lojas seja atendida e as demais restrições do problema sejam respeitadas. Para a resolução do VRPSD e suas extensões, a única metaheurística encontrada na literatura foi busca tabu. Para o problema de roteirização com frota heterogênea e suas extensões, foram implementadas apenas as metaheurísticas busca tabu e BATA (Back-Tracking Adaptative Threshold Accepting). As estratégias de solução propostas no presente trabalho consistem na implementação de heurísticas construtivas e da metaheurística scatter search. As soluções iniciais de SS são obtidas através da implementação de quatro heurísticas construtivas: heurística de economias, heurística de inserção seqüencial baseada nas idéias de Solomon (1987), heurística de inserção seqüencial baseada nas idéias de Ho e Haugland (2004) e adaptação da heurística de inserção seqüencial de Dullaert et al. (2002). Para o caso real, foi possível uma redução no custo total da frota comparado com a solução atual da empresa. Para algumas instâncias dos três conjuntos de problemas da literatura, os algoritmos apresentaram resultados similares ou superiores às melhores soluções encontradas. / This thesis studies the implementation of heuristics and scatter search (SS) metaheuristic in a Heterogeneous Fleet Vehicle Routing Problem with Time Windows and Split Deliveries (HFVRPTWSD). The HFVRPTWSD is a combination of Heterogeneous Fleet Vehicle Routing Problem (HFVRP), Vehicle Routing Problem with Time Windows (VRPTW) and Vehicle Routing Problem with Split Deliveries (VRPSD). The problem is based in a single depot, the demand of each client can be greater than the vehicle’s capacity and beyond the time windows constraints, and there are also constraints on the vehicle capacity and vehicles type. The VRPSD was introduced in the literature by Dror e Trudeau in 1989. In the split deliveries vehicle routing problem, each client can be supplied by more than one vehicle; while in a classic vehicle routing problem (VRP) each client is supplied by only one vehicle. Thus, for the VRPSD, besides the delivery routes, the amount to be delivered to each client in each vehicle must also be determined. All the split delivery vehicle routing problems researched in the literature (VRPSD and its extensions) have as a characteristic the homogeneous fleet. Therefore, the problem studied differs from the split deliveries vehicle routing problems of the literature because it has a heterogeneous fleet. The same reasoning can be applied in heterogeneous fleet vehicle routing problem. The models will be applied in a retail market in Brazil that is supplied by a distribution center. The market has 519 stores distributed in 12 Brazilian states. The heuristics and the scatter search metaheuristic will also be applied in three benchmark problems (SOLOMON, 1987; HO AND HAUGLAND, 2004; LIU AND SHEN, 1999), aiming to evaluate the design of the algorithms for each problem. The problem consists in determining, each day, how to allocate the trucks to the stores, the amount to be delivered in each truck to each client, which one is the best route and the initial time for attending the first client, with the aim of minimizing the total distribution cost, attending the clients’ demand and respecting all the problem’s constraints. For the VRPSD and its extensions, the only metaheuristic implemented in the literature was tabu search. For the heterogeneous fleet vehicle routing problem and its extensions, only the tabu search and BATA (Back-Tracking Adaptative Threshold Accepting) metaheuristics have been implemented. The strategies proposed here consist in the implementation of constructive heuristics and the scatter search metaheuristic. The initial solutions of SS are obtained with the implementation of four constructive heuristics: saving heuristics, sequential insertion heuristic based on the ideas of Solomon (1987), sequential insertion heuristic based on the ideas of Ho e Haugland (2004) and adaptation of the sequential insertion heuristic of Dullaert et al. (2002). For the real case, it was possible to reduce the total fleet cost, when comparing to the actual solution. At some instances of the three benchmark problems, the algorithms presented similar or better results when compared to the best solutions in the literature.

A localização de instalações está entre as mais importantes decisões logísticas. A questão é tratada, em geral, por técnicas de Pesquisa Operacional, principalmente a programação linear inteira mista, cuja modelagem tem aspectos que podem ser aprimorados. Esta tese apresenta uma proposta metodológica subdividindo o problema em duas fases, visando localizar centros de distribuição de carga (CDs). A Fase 1 define as localizações ótimas dos CDs, iniciando com uma agregação de nós de demanda em clusters através de uma heurística, complementada pela metaheurística simulated annealing (SA). Em seguida, buscam-se, em cada cluster, os melhores locais candidatos. Entre estes candidatos definem-se as localizações ótimas, através de um modelo de programação linear inteira mista ou por SA. Foi conduzido um experimento controlado, com solução ótima conhecida, tendo coincidido em vários casos com a solução obtida através da metodologia proposta. A Fase 2 define a quantidade ótima de CDs, modelando os custos de estoque, armazenagem e vendas perdidas, não considerados na primeira fase. Estes modelos exógenos ao modelo de otimização da primeira fase podem trabalhar sem a restrição de linearidade, trazendo assim, maior realismo a modelagem. Ao final consolida-se o conjunto de custos logísticos (Fases 1 e 2) de forma a se identificar a quantidade de CDs que conduz ao mínimo custo total. A metodologia foi aplicada a um caso real com mais de duzentos pontos de demanda distribuídos sobre os três estados da região sul do país. Os resultados mostraram a aplicabilidade da abordagem proposta. / The facility location is one of the most important logistic decisions. The problem is usually handled through the use of operations research techniques, mainly with the use of mixed integer linear programming (MILP), which modeling process can be improved in some of its aspects. This thesis presents a methodological proposal subdividing the problem in two stages, in order to locate distribution centers (DCs). Stage 1 identifies the optimal DC locations, starting with a heuristics, complemented by the metaheuristic simulated annealing (SA), to cluster the demand nodes. Next, the heuristics searches for best DCs candidates in each cluster. Among these best candidates are defined the optimal locations, with the use of a MILP model or through the use of SA. In order to validate the methodology, it was conducted a controlled experiment, with a known optimal solution, having matched in many cases with the solutions obtained through the proposed approach. Stage 2 defines the optimal DC number, modeling the costs of inventory, storage and lost sales, which were not considered in the first stage. These models, exogenous to the Stage 1 optimization model, could represent the costs behavior without the linear restriction, bringing more realism to the modeling process. Finally, the whole set of logistic costs (Stages 1 and 2) is combined in order to identify the DC quantity with minimal total cost. The methodology was applied to a real world problem encompassing more than two hundred demand points spread over the three states of the southern Brazilian region. The results have shown the applicability of the proposed approach.

Este trabalho detalha o problema de programação de atividades de desenvolvimento de poços marítimos (PPADPM), cujo objetivo é definir o uso de sondas e navios, de forma a otimizar a produção de óleo dos poços marítimos. São apresentados cinco modelos baseados em programação linear-inteira mista (MILP) e um modelo gerado via programação por restrições (PR) para este problema. Concluiu-se que, dentre os modelos MILP, aquele baseado em variáveis que definem a ordem de execução das atividades apresenta os melhores resultados, tanto em termos de qualidade de soluções quanto em termos de tamanho do modelo. O aumento do tamanho da instância (em número de poços e/ou em número de recursos) traz como consequência um menor número de nós analisados dentro de um tempo limite de execução do modelo, ao mesmo tempo em que se observa que as estratégias de escolha de variáveis, de escolha de nós e de uso de solução inicial nos modelos MILP tornam-se ineficientes. Na comparação entre modelos MILP e o modelo baseado em PR, constatou-se que este último obteve as melhores soluções em mais de 90% dos casos analisados e, consistentemente, obteve mais soluções viáveis para cada instância. Entretanto, por não fornecer informações sobre a qualidade da solução, o modelo baseado em PR somente obtém a solução ótima ao analisar todo o espaço de busca do modelo; desta forma, este apenas chegou à solução ótima em instâncias com até quatro poços, enquanto alguns dos modelos MILP obtiveram a solução ótima para instâncias com até treze poços. / This work details the offshore wells activities on specialized resources scheduling problem, focusing on the optimization of the total oil production. A Constraint Programming (CP) model and five Mixed-Integer Linear Programming (MILP) models were studied. Among the linear models, those based on activities order variables are smaller, and led to the better solutions for almost all of the instances analyzed. As far as the size of the instances (number of wells and/or number of resources) increases, the number of branched nodes in a limited time decreases and, consequently, the influence of B&B nodes and variable selection strategies and of the initial guesses on the MILP model solution gets less efficient. Comparing best solutions for each instance, the CP model outperformed MILP models in 90% of the studied cases. In addition, the CP based model consistently found more solutions per instance than the MILP based models did. However, because the CP model does not give information on the quality of a solution (gap), it was only able to obtain optimal solutions for instances with up to four wells, while MILP based models found optimal solutions for instances up to thirteen wells.

A busca pelo crescimento econÃmico exacerbado gera consequÃncias que comprometem a qualidade de vida das pessoas no Planeta. Nas Ãltimas dÃcadas, o agronegÃcio tem se destacado como mais um elemento que acentuou os desequilÃbrios nas esferas ambiental e social. Nesse cenÃrio, os latifundiÃrios tradicionais expandiram as suas fronteiras agrÃcolas para regiÃes antes nÃo exploradas nessa dimensÃo: o Cerrado Piauiense, que teve como carro chefe de exploraÃÃo o cultivo da soja em grande escala. Assim, a pesquisa teve como objetivo estudar determinados impactos sociais e econÃmicos da cadeia primaria de produÃÃo da soja em uma amostra representativa de Unidades Produtoras do Distrito Nova Santa Rosa do municÃpio de UruÃuÃ-PI. A metodologia do estudo deu-se atravÃs de pesquisas bibliogrÃficas especializadas na temÃtica, associadas à coleta de dados e informaÃÃes de natureza primÃria obtidos junto a 55 Unidades representativas Produtoras de Soja do Distrito Nova Santa Rosa, em UruÃuÃ-PI. Essas foram divididas em dois estratos de dimensÃo. Os dados coletados foram submetidos inicialmente à anÃlise estatÃstica descritiva, por meio do cÃlculo de medidas de valor central e de dispersÃo para as variÃveis quantitativas e foi identificado o espectro dominante das variÃveis qualitativas separadamente para cada substrato de dimensÃo. Em seguida, realizou-se a AnÃlise de Componentes Principais para conhecer a importÃncia de cada variÃvel estudada sobre a variÃncia total disponÃvel atravÃs da definiÃÃo dos fatores. Verificou-se que hà uma grande heterogeneidade entre as Unidades Produtoras, a qual concentrou 78,71% da variaÃÃo total, com destaque para a SuperfÃcie AgrÃria Ãtil, e a proporÃÃo de cereais cultivados, acarretando em uma variaÃÃo dos gastos variÃveis. Genericamente, pode-se constatar que hà uma variedade de diferenciaÃÃo entre os LatifundiÃrios e MesofundiÃrios, centrando-se, sobretudo, nas vantagens com as quais aqueles operam, relativamente a estes. A pesquisa caracterizou-se por indicativos de crescimento econÃmico exÃgeno. Identificou-se a atuaÃÃo de uma empresa multinacional, que monopoliza a comercializaÃÃo de grÃos no Distrito. / The search for the exacerbated economic growth generates consequences that compromise the quality of life on the planet. In recent decades, agribusiness has emerged as one more element which accentuated the imbalances in the environmental and social spheres. In this scenario, traditional landowners expanded their agricultural frontiers to areas not previously explored in this dimension: Piauiense Cerrado, which had the flagship exploration soy cultivation on a large scale. Thus, the research aimed to study certain social and economic impacts of the primary chain of soybean production in a representative sample service units in New District of the city of Santa Rosa UruÃuÃ-IP. The study methodology was given through specialized bibliographic research on the issue, associated with data collection and primary nature of information obtained from 55 Units District Soybean Producers New Santa Rosa, in UruÃuÃ-IP. The study methodology was given through specialized bibliographic research on the issue, associated with data collection and primary nature of information obtained from representative 55 Units District Soybean Producers New Santa Rosa, in UruÃuÃ-PI. These dimensions were divided into two strata. The data collected were subjected to descriptive statistics, through the central measures of value calculation and dispersion for quantitative variables was identified and the dominant spectrum of qualitative variables separately for each dimension of the substrate. Then took place the Principal Component Analysis to know the importance of each variable studied on the total variance available by defining factors. It was found that there is great heterogeneity among the service units, which concentrated 78,71% of the total variation, especially for Land Surface Net, and the proportion of cultivated cereals, resulting in a variation of the variable expenses. Generally, it can be seen that there are a variety of differentiation between Lend Lords and Meium owners, focusing mainly on the advantages with which those operating in respect of these. The research was characterized by indicative of exogenous economic growth. Identified the role of a multinational company that monopolizes the marketing of grain in the District.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / The study deals with the problems of Production Scheduling in Flow Shop environment with multiple machines in the production stages, where the setup time is not inserted in the processing time of the operations. May be a production system in which the setup depends on whether or not the sequence of tasks, where tasks are performed without interruption between successive operations, also called production system no-wait. Being proposed in this work, twenty methods of heuristic solutions defined by Priority Rules, which provide an ordering of the tasks to be followed in its programming, which is done each task, successively. Twenty of these proposed heuristics, seven were implemented for the case of set operations independent of the sequence of tasks, and thirteen dependent heuristics tested for setup. To perform the computational experience we developed a specific software. For evaluation of the software generated a set of thirty-six thousand test-problems that are differentiated according to the number of tasks (n), number of production stages (g), levels of flexibility (f) and time intervals of setup (s). Following the result of these problems-tests are evaluated by some statistical measures. / O estudo trata dos problemas de ProgramaÃÃo da ProduÃÃo em ambiente Flow Shop com mÃquinas mÃltiplas nos estÃgios de produÃÃo, nos quais o tempo de setup nÃo està inserido no tempo de processamento das operaÃÃes. Podendo ser um sistema produtivo em que o setup depende ou nÃo da sequÃncia das tarefas, nos quais as tarefas sÃo realizadas sem interrupÃÃo entre operaÃÃes sucessivas, tambÃm chamado sistema de produÃÃo no-wait. Sendo proposto neste trabalho, vinte mÃtodos de soluÃÃes heurÃsticas definidos por Regras de Prioridade, as quais fornecem uma ordenaÃÃo das tarefas a ser seguida na sua programaÃÃo, que à feita tarefa por tarefa, sucessivamente. Destas vinte heurÃsticas propostas, sete foram implementadas para o caso de setupindependente da sequÃncia de operaÃÃes das tarefas, e treze heurÃsticas testadas para setup dependente. Para a realizaÃÃo da experimentaÃÃo computacional foi desenvolvido um software especÃfico. Para avaliaÃÃo do software foi gerado um conjunto de trinta e dois mil problemas-teste que sÃo diferenciados em funÃÃo do nÃmero de tarefas (n), nÃmero de estÃgios de produÃÃo (g), nÃveis de flexibilidade (f) e intervalos de tempo de setup (s). Na sequÃncia o resultado destes problemas-testes sÃo avaliados por algumas medidas estatÃsticas.

O problema de escalonamento num flow shop (ou flow shop scheduling problem, FSSP) é um modelo de sistemas de produção muito comum que é bem estudado na literatura. No entanto, quase toda a literatura foca-se em escalonamentos permutacionais, desconsiderando soluções ótimas e quase ótimas que são escalonamentos não-permutacionais. Além disso, a prática comum padroniza os tempos de processamento de cada operação, mesmo que estes tempos variem dependendo das diferentes capacidades dos operadores das máquinas, cuja diversidade deve ser considerada no processo de escalonamento quando seja significativa, e.g., em centros de emprego para deficientes (CEDs). Nesta tese, propomos métodos para resolver o FSSP não-permutacional, usando o mesmo tempo e esforço que os métodos do estado da arte usam para o FSSP permutacional, e produzindo escalonamentos não-permutacionais com melhor qualidade do que escalonamentos permutacionais e não-permutacionais produzidos por métodos do estado da arte. Também propomos métodos para resolver o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num flow shop (ou heterogeneous workforce assignment and flow shop scheduling problem, Het-FSSP), produzindo soluções que compensam as diferentes capacidades e deficiências dos trabalhadores com pequenas perdas nos objetivos da produção. Além do mais, a designação de trabalhadores heterogêneos pode ser integrada em outros problemas de escalonamento, como fizemos com o problema combinado de designação de trabalhadores heterogêneos e escalonamento de tarefas num job shop (ou heterogeneous workforce assignment and job shop scheduling problem, Het-JSSP). / The flow shop scheduling problem (or FSSP) is a very common model of production systems that is well studied in the literature. However, almost all the literature focuses on the permutation FSSP, disregarding optimal and near optimal solutions that are non-permutation schedules. Besides, common practice standardizes the processing times of each operation, even when those times may vary depending on different capabilities of the machine operators, whose diversity must be considered in the scheduling process when it is significant, e.g., in Sheltered Work centers for Disabled (SWDs). In this thesis, we propose methods to solve the non-permutation FSSP, using the same time and effort as state-of-the-art methods for the permutation FSSP, and producing non-permutation schedules with better quality than permutation and non-permutation schedules produced by state-of-the-art methods. We also propose methods to solve the combined heterogeneous workforce assignment and flow shop scheduling problem (or Het-FSSP), producing solutions that compensate the different capabilities and disabilities of the workers with minor or null losses in the productivity objectives. Moreover, the heterogeneous workforce assignment may be integrated into other shop scheduling models, as we did with the heterogeneous workforce assignment and job shop scheduling problem (or Het-JSSP) with similar results.

Made available in DSpace on 2018-08-01T22:35:47Z (GMT). No. of bitstreams: 1 tese_11146_Dissertação CATHERINE 2017-Final.pdf: 10661508 bytes, checksum: 799380277e437119df5bc171a20e96bf (MD5) Previous issue date: 2017-07-17 / O presente estudo abordou o manejo florestal sustentável (MFS) na Amazônia brasileira. O primeiro capítulo teve como objetivo quantificar o custo de produção de madeira em tora, posta em serraria, no estado do Acre. Foram coletados dados relacionados ao preço da terra florestal, da matéria-prima, da elaboração e execução de planos de manejo, das atividades inerentes à exploração florestal e do transporte da madeira em tora até a serraria. Os dados foram obtidos por meio de entrevistas e aplicação de formulário. O custo de produção foi calculado para florestas manejadas a 50 km, 100 km e 150 km da cidade de Rio Branco, áreas estas incluindo ou não a instalação e medição de parcelas permanentes (PP), como também, a aplicação ou não de tratos silviculturais pós-exploratórios. Calculou-se o custo de produção para um ciclo de corte de 25 anos. Quantificou-se o valor presente líquido (VPL) das atividades do MFS, nas taxas de juros de 6% a.a., 8% a.a., 10% a.a. e 12% a.a. Identificou-se a margem de comercialização da madeira em tora, posta em serraria. Concluiu-se que, para uma área de manejo localizada a 50 km de Rio Branco, com ou sem PP, a atividade é viável em termos econômicos. Com o acréscimo de tratos pós-exploratórios, a produção de madeira em tora a 50 km é viável apenas a uma taxa de 6%. Na situação em que a floresta localiza-se a 100 km, a margem de comercialização se mantém positiva a uma taxa de 6%, apenas para cenários com e sem parcelas permanentes. Para maiores distâncias (150 km), tem-se prejuízo no processo de produção. O segundo capítulo teve como objetivo propor modelos matemáticos para otimizar a definição de Unidades de Produção Anual (UPAs) em áreas de manejo sustentável na Amazônia, regulando a produção de volume. A área de estudo localiza-se no município de Bujari, Acre, em que foram selecionadas duas UPAs. A formulação dos modelos teve como base o problema de p-medianas capacitado (PPMC). A primeira proposta visou otimizar a subdivisão de uma UPA, de modo a obter uma produção regular durante dois anos de exploração, considerando o prazo para explorar a área. Nessa abordagem, foram alocados pátios de forma otimizada, com restrições de distância máxima de arraste e capacidade máxima dos pátios. A segunda proposta visou otimizar a formação de UPAs a nível de árvores, de modo a agrupar as árvores acima do diâmetro mínimo de corte (DMC), regulando a produção florestal. Em ambas as propostas foram executados dois cenários de regulação do volume: ± 10% e ± 20%. No cenário 1 da proposta 1, a produção variou em ± 9,6%. Para o cenário 1 da proposta 2, o volume total acima do DMC variou em ± 0,14%. Após a formação das UPAs e posterior aplicação dos critérios da legislação, a produção total explorável das UPAs teve uma variação de aproximadamente ± 1,9%. As propostas são aplicáveis à realidade na Amazônia e podem ser utilizadas para regular a produção de madeira em áreas de MFS na região.

Submitted by MARCOS LEANDRO TEIXEIRA DE OLIVEIRA (marcosteixeira@ufv.br) on 2018-09-04T13:38:28Z No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) / Made available in DSpace on 2018-09-04T13:38:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) Previous issue date: 2018-01-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos para Coleta de Lixo com Janelas de Tempo (WCVRPTW), cujo objetivo é encontrar as rotas para os veículos coletores de lixo de modo que todos os clientes sejam plenamente atendidos e a distância total percorrida pelos veículos seja a menor possível, minimizando assim os custos de transporte. Para alcançar este objetivo é necessário que algumas restrições sejam atendidas: os clientes devem ser atendidos dentro de um período de tempo; existe horário de saída e retorno dos veículos ao depósito; os veículos possuem restrições de capacidade; as rotas possuem restrições de volume de carregamento e número de clientes atendidos; os veículos devem sair e retornar vazios ao depósito, e, quando cheios, devem ir para o aterro sanitário mais próximo para descarga do lixo. Além disso, os motoristas dos veículos devem realizar uma parada de almoço. O WCVRPTW é um problema real que pertence à classe NP-difícil. Para resolvê-lo, são desenvolvidos quatro algoritmos heurísticos: Simulated Annealing (SA), Tabu Search (TS), e dois algoritmos híbridos baseados nas metaheurísticas Iterated Local Search (ILS) e Variable Neighborhood Descent (VND), denominados ILS-VND e ILS-RVND. Os desempenhos dos algoritmos propostos são analisados em instâncias de pequeno e médio porte geradas para este trabalho, e também em instâncias de grande porte disponíveis na literatura. Os experimentos computacionais mostram que os algoritmos propostos são eficientes, competitivos e rápidos. / In this work we address The Waste Collection Vehicle Routing Problem with Time Windows (WCVRPTW), whose objective is to find the routes for garbage collection vehicles so that all customers are fully served and the total distance traveled by the vehicles is the smallest possible, thus minimizing transportation costs. In order to achieve this objective, some constraints must be satisfied: customers must be ser- ved within a period of time; there are departing and return times of the vehicles to the warehouse; vehicles have capacity constraints; the routes have loading volume constraints and number of customers served; the vehicles should leave and return empty to the depot, and when full should go to the nearest landfill for garbage disposal. In addition, drivers of the vehicles must have a lunch break. WCVRPTW is a real problem that belongs to the NP-hard class. In this work, to solve it, four heuristic algorithms are developed: Simulated Annealing (SA), Tabu Search (TS), and two hybrid methods based on the Iterated Local Search (ILS) and Varia- ble Neighborhood Descent (VND) metaheuristics, called ILS-VND and ILS-RVND. The performances of the proposed methods are analyzed in small and medium-sized instances generated in this work, and also in large instances available in the lite- rature. Computational experiments show that the proposed methods are efficient, competitive and fast.

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-07-21T18:54:37Z (GMT). No. of bitstreams: 1 Coelho_MarcoAntonioFreitasdoEgito_D.pdf: 7042998 bytes, checksum: 9bebcee2dc4b60902fd40a01d09293f9 (MD5) Previous issue date: 1996 / Resumo: Nesta tese novos métodos e procedimentos para resolver o problema de programação de tarefas em múltiplas máquinas paralelas com custos de atraso e adiantamento são propostos. As máquinas são não-relacionadas, a divisão de tarefas é permitida, as tarefas podem ter datas previstas de entrega diferentes e os tempos de preparação de máquina para executar uma tarefa depende da tarefa anterior processada na mesma máquina. Este é um problema novo, de dificil resolução e não foram encontradas referências na literatura especializada. Apesar disso, tem muitas possíveis aplicações na manufatura. O problema é formulado através de um modelo linear de programação inteira mista para o caso sem divisão de tarefas e, posteriormente,dois outros modelos lineares são propostos para o caso onde a divisão de tarefas é permitida. Como o problema de minimização foi mostrado ser NP-completo, os modelos podem apenas ser utilizados para resolver pequenos problemas de teste. A partir do modelo de programação inteira mista, um método de busca em árvore é desenvolvido para uso com procedimentos Branch & Bound e Busca em Feixe Filtrada. Dois limitantes inferiores são desenvolvidos para o Branch & Bound e quatro limitantes para a Busca em Feixe Filtrada. Algumas propriedades e teoremas do problema original e um método de decomposição eficiente para resolver o modelo linear derivado do modelo de programação inteira mista, também são apresentados. Muitos problemas de teste com até 120 tarefas e 6 máquinas são utilizados para mostrar o desempenho dos métodos desenvolvidos aqui / Abstract: In this thesis new methods and procedures to solve the multimachine scheduling problem with early and tardy costs are proposed. The machines are unrelated, job splitting is allowed, the jobs may have different due dates and the changeover time to process a new job on a machine depends on the job previously processed on the same machine. This problem is new, hard to solve and no references have been found in respecialized literature. However, it has many applications in the manufacturing. Two linear mixed-integer programming models one stated when job splitting is allowed, as well as similarmodel is proposed for the case without job splitting. Since the problem is NP-hard, the models can oniy be used to solve small test problems. Based on the mixed-integer formulation, a tree search method is developed to be used in a Branch & Bound and in a Filtered Beam Search procedures. Two lower bounds are developed for the Branch & Bound and four bounds for the Filtered Beam Search. Some properties of the original problem and an efficient decomposition method to solve the LP model derived from the mixed-integer problem are presented. Many test problems with up to 120 jobs and 6 machines has been used to show the performance of the proposed methods / Doutorado / Doutor em Engenharia Elétrica

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica e Computação Cientifica / Made available in DSpace on 2018-07-22T10:43:05Z (GMT). No. of bitstreams: 1 Nobrega_MarcosdeAguiar_M.pdf: 2392664 bytes, checksum: da731a38ecbd5c16ec969bc8a7bc29d5 (MD5) Previous issue date: 1997 / Resumo: Um sistema de produção e transporte de minério de ferro é constituído por um conjunto de minas, por um porto e por uma ferrovia que liga as minas ao porto. Em cada mina são produzidos diversos tipos de minério, diferenciados por suas especificações físico-químicas. O minério transportado para o porto é misturado em pilhas, e as especificações dessas misturas são limitadas de acordo com os tipos de minério que serão embarcados nos navios. Cada pilha deve ser construída até a data de chegada do navio que vai embarcá-la. Neste trabalho são desenvolvidos modelos de programação matemática que orientam o planejamento de curto prazo de um sistema de produção e transporte de minério de ferro. A modelagem contém restrições de produção e estocagem nas minas, de capacidades de transporte na ferrovia, de capacidades de descarga e estocagem no porto e de especificações das pilhas no porto. O objetivo é, primeiramente, minimizar o atraso na construção das pilhas, e, em seguida, minimizar os custos variáveis de produção e transporte no sistema / Abstract: A production and transportation iron ore system is composed by a set of mines, a port and railroad links from the mines to the port. Many types of ore are produced in each mine, and they differ in their physical and chemical specifications. The ore that is transported to the port is blended in piles. Blend specifications are set according to the ship loads. Each pile must be built until the arrival of the ship that will carry it. Mathematical programming models for the short term planning of a production and transportation iron ore system have been developed in this work. The modeling has production and inventory constraints at the mines, transportation capacity constraints at the railroad, rail ear unloading and inventory capacity constraints at the port, as well as pile specification constraints also at the port. The objective is, firstly, to minimize the pile construction delay, and secondly, to minimize the system's production and transportation variable costs / Mestrado / Mestre em Matemática Aplicada