Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T14:25:03Z (GMT). No. of bitstreams: 1 Nascimento_JulianaMartinsdo_M.pdf: 4967741 bytes, checksum: 20ceacaab689704941f1f9d3ec41695a (MD5) Previous issue date: 2002 / Resumo: Problemas de otimização combinatória são classificados na grande maioria das vezes como NP-difíceis. Para estes problemas, não são conhecidos algoritmos polinomiais capazes de resolvê-los. Logo, é necessário o desenvolvimento de estratégias eficientes para tratá-los. O desenvolvimento de técnicas híbridas para a resolução destes problemas tem por objetivo valorizar os pontos fortes dos métodos que estão sendo empregados, para, desta forma, compensar os pontos mais fracos, criando um procedimento de qualidade superior. Este trabalho propõe um método híbrido que integra técnicas de Programação por Restrições com metaheurísticas de Busca Tabu para atacar o problema de escalonamento de atividades na produção de um campo petrolífero. Como não há resultados anteriores para serem comparados com os resultados obtidos para as instâncias consideradas neste trabalho, modelos de programação matemática foram utilizados para a obtenção de limitantes duais para a solução do problema. Além disso, para determinar quão robusta é a técnica proposta, uma análise de sensibilidade foi realizada sobre as instâncias consideradas / Abstract: Combinatorial optimization problems are generally NP-hard. As it is not known polinomial time algorithms to solve them, it is necessary to develop efficient strategies to treat them. The aim in developing hybrid techniques to solve combinatorial optimization problems is to strength the good features of the methods that are being combined to compensate for their weakness. In this paper, we propose a hybrid method that combines Constraint Programming techniques and Tabu Search metaheuristics to schedule the activities involved in the production process of an oil field. As there are no previous results to estabilish a comparision with the results obtained with the instances considered in this work, bounds were determined using mathematical programming models. Finally, to estabilish the robusteness of proposed method, a sensibility analysis was performed over the considered instances / Mestrado / Mestre em Ciência da Computação

Orientadores: Paulo Morelato França, Mauricio Guilherme de Carvalho Resende / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T19:16:40Z (GMT). No. of bitstreams: 1 Buriol_LucianaSalete_D.pdf: 1278955 bytes, checksum: 81c4d001b9fa79d3045253176b03bfbd (MD5) Previous issue date: 2003 / Doutorado

Orientador: Maria Teresa Moreira Rodrigues / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Quimica / Made available in DSpace on 2018-07-25T04:10:12Z (GMT). No. of bitstreams: 1 Conselheiro_FabioRibeiro_M.pdf: 2779291 bytes, checksum: 1e7615a7157c1c4788995eb0e8f52e48 (MD5) Previous issue date: 1999 / Resumo: O crescimento recente de indústrias de especialidades como farmacêutica, de alimentos e materiais para indústria eletrônica tem despertado o interesse na programação de produção de plantas de produção em batelada. O problema de Programação de Produção em tais plantas aumenta devido à necessidade de compartilhamento de recursos e tempo disponível para processamento de potencialmente um grande número de produtos, obedecendo à um conjunto de restrições, tais como prazos de entrega e oferta de materiais. São propostos diversos métodos para a solução desses problemas, tais como Programação Matemática, Branch and Bound e métodos heurísticos. Devido à complexidade dos problemas de Programação de Produção em plantas Multiproduto e Multipropósito em batelada. São também apresentadas diferentes versões do algoritmo, baseados nos algoritmos de Metropolis e Glauber, além de métodos de recozimento e construção de novas soluções / Abstract: Recent growth of specialty industries such as pharmaceutical, food products and material for electronic industries has increased the interest in the scheduling of batch production plants. The scheduling problem arises due the shared resources and available time processing of a potentially large number of products within certain constraints, like as due dates and available materials. A several methods are proposed to solve this problem, such as Mathematics Programming, Branch and Bound and heuristics methods. Due the complexity of scheduling problems, the use exacts methods are restricted due the large computational time demanded, while heuristics methods such a Simulated Annealing can offer sub optimal solutions in a short time. In this work the application of the Simulated Annealing method for scheduling problems for Flowshops and Jobshops batch plants was studied. A several versions of the Simulated Annealing algorithm based on Metropolis¿s and Glauber¿s algorithm are presented, together with annealing schedules and types of random moves for new solutions / Mestrado / Mestre em Engenharia Química

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas. Instituto de Computação / Made available in DSpace on 2018-08-04T04:16:19Z (GMT). No. of bitstreams: 1 Ganhoto_MarcoAlves_M.pdf: 1370660 bytes, checksum: 851eb09fb46a8ed3bfb7990592eb9a41 (MD5) Previous issue date: 2004 / Resumo: Neste trabalho, investigamos abordagens para problemas de roteamento, que têm como finalidade encontrar um melhor conjunto de rotas para que veículos possam transportar mercadorias a clientes geograficamente dispersos, respeitando certas restrições, como por exemplo, a de capacidade de carga dos veículos. Para isto, além de pesquisas em diversas fontes de informações, desenvolvemos um aplicativo para auxiliar no entendimento dos algoritmos, na ilustração do texto e na realização de experimentos. A partir de observações feitas durante as execuções do aplicativo, experimentamos combinações de critérios de seleção de localidades, utilizando tais combinações durante a realização dos movimentos de intercâmbio de vértices entre rotas de uma conhecida estratégia, a Metaheurística Busca Tabu. Foram combinados critérios baseados em distâncias com critérios baseados em ângulos, para compor algoritmos que foram testados com instâncias clássicas utilizadas por diversos pesquisadores. Os resultados obtidos foram apresentados juntamente com os de outras estratégias, fornecendo valores iguais ao melhor valor conhecido para duas instâncias, e valores intermediários para as outras cinco instâncias utilizadas nos testes / In this work, we examine some approaches for vehicle routing problems, to find a best set of routes to enable companies for delivery goods or commodities to customers, respecting some constraints, such as vehicles loading capacity. To this purpose, besides researching available information sources, we have developed a software to help us to understand the algorithms issues, for enriching the text with illustrations, and for effectiving some experiments concerning to previously selected approaches. From the analysis made during running software process, we decided to arrange chosen vertices criterias, using these arrangements in the vertices interchanging movements between routes of an already know method, the Tabu Search Metaheuristic. More precisely, we have combined distances and angles criteria, to implement algorithms on which it were tested using some classical instances considered by several researchers. The obtained results are presented with those selected approaches, and it provided us two equals values to the best known solution, and five intermediate values amoung to the others used on these experiments / Mestrado / Engenharia de Software / Mestre Profissional em Computação

El presente trabajo de título tuvo como objetivo el diseño, desarrollo y evaluación de una herramienta que permitiera apoyar la toma de decisiones respecto de la programación de operaciones en cada una de las dos plantas con que actualmente cuenta una compañía siderúrgica. Se buscó de esta forma encontrar la secuencia en que debieran ejecutarse los distintos trabajos mensuales, minimizando los tiempos de producción así como los tiempos de retrasos en las fechas de entrega. La investigación se centró, por razones de tiempo, únicamente en el proceso de laminación de la compañía, que es aquel en donde se le da la forma final a los productos siderúrgicos mediante deformación termomecánica. Esta elección no fue al azar y se tomó considerando el hecho de que dicho proceso es hasta el día de hoy el principal “cuello de botella” y por lo tanto representaba las mayores oportunidades de ganancia. Ahora bien, fue posible demostrar que el problema pertenece a la clase NP-Hard por lo que no se conocen algoritmos capaces de resolverlo en un tiempo polinomial. Como consecuencia, y dado que el tamaño de la instancia es relativamente grande, se hizo necesario incorporar enfoques heurísticos que permitieran obtener resultados suficientemente buenos en un tiempo de computación razonable. Es así como se optó por un algortimo de Búsqueda Tabú. La elección se basó principalmente en los buenos resultados reportados en la literatura para otros problemas de programación de operaciones (Lin y Ying, 2006; Gupta y Smith, 2007 y Valente y Alves, 2008). Gran parte del desempeño de este tipo de heurística depende de dos elementos: la solución inicial y la metodología de generación de vecindades. Es por ello que la estrategia seguida consistió en evaluar un amplio espectro de las técnicas más utilizadas para tales fines, escogiendo finalmente aquella combinación que presentó un mejor desempeño. Los resultados obtenidos muestran que la aplicación de la heurística propuesta a instancias reales permite obtener reducciones importantes en comparación a la situación actual: un 7% promedio en los tiempos de producción y disminuciones promedio del 35% en lo que se refiere a los tiempos de retraso. Por otra parte, se observa una dramática caída del 82% promedio en lo que al tiempo necesario para determinar la programación respecta. Finalmente, cabe destacar que la investigación realizada sugiere también que aún hay espacio para futuras mejoras, por lo que se recomienda dar continuidad al estudio y en lo posible ampliarlo a otros procesos de la cadena productiva.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Los problemas de ruteo de vehículos, tienen la particularidad de ser simples de expresar, pero complejos de resolver; lo anterior es por las restricciones de integralidad y el crecimiento exponencial de sus posibilidades, a medida que el tamaño del problema aumenta. Es por esto, que es necesario utilizar técnicas de optimización para enfrentar este tipo de problemas, al no poder resolverlo de una manera simple. En este estudio, se resuelve un problema de asignación de cartera de vendedores y ruteo de vehículos periódico, presentado por la empresa ECOLAB S.A. El modelo planteado, incorpora el concepto de equidad en la construcción de las rutas y las carteras, buscando equiparar los tiempos de recorrido, los tiempos ociosos y los beneficios percibidos por cada cartera. La metodología de solución es heurística, la que se compone de una etapa de asignación con conceptos de equidad, la construcción de las rutas y el mejoramiento de estas. El modelo obtenido es testeado frente a instancias generadas aleatoriamente. Además, se resuelve el problema de la empresa, contrastando los datos reales con los de la solución heurística. Se evidencia que, al hacer pequeñas mejoras en cuanto a la asignación de recorridos a los vendedores, es posible disminuir el tiempo de recorrido y el tiempo ocioso. También, disminuyen las desviaciones en los beneficios percibidos por las carteras de clientes. Se obtiene un incremento en el tiempo ocioso (holgura), el cual se produce por una optimización de la planificación de visitas. Todos estos resultados se obtienen en tiempos pequeños, pues la ejecución del programa es rápida. Se obtienen beneficios económicos y cuantificables, a la hora de aplicar lo desarrollado en esta tesis. Se resuelve el problema exacto para instancias menores, mostrando lo costoso en tiempo y recursos que es resolver el problema de esta manera, para aplicaciones que necesitan de numerosas ejecuciones y análisis de sensibilidad. Para las instancias analizadas, los tiempos de resolución van entre los 12 y los 35,000 segundos. Al resolver estas instancias con la heurística propuesta, los gap obtenidos van desde el 0.8 al 7.41 por ciento, con respecto a la solución exacta. Se realiza un caso de estudio con datos de la empresa. La aplicación de la heurística aumenta un 8% el potencial de ventas y un 4% la rentabilidad por día trabajado neto. La contribución de este estudio, es mostrar un enfoque de equidad en la asignación de clientes y construcción de rutas para un área comercial, con el fin de obtener carteras de clientes balanceadas en dinero y tiempos. También contribuye a la empresa a generar soluciones del tipo matemáticas, con el objetivo de prestar un soporte distinto al que se viene utilizando.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2015-11-12T10:42:09Z No. of bitstreams: 1 texto completo.pdf: 1645681 bytes, checksum: eede2be161a471450d5d998d3d3f3ffe (MD5) / Made available in DSpace on 2015-11-12T10:42:09Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1645681 bytes, checksum: eede2be161a471450d5d998d3d3f3ffe (MD5) Previous issue date: 2015-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A otimização de percursos é de grande interesse para empresas que fornecem serviços relacionados com transporte, seja de pessoas ou de mercadorias, visto que podem levar a uma diminuição do tempo e do custo necessário para prestar um serviço e, consequentemente, elevar a lucratividade. Neste trabalho é abordado o Problema do Caixeiro Viajante com Seleção de Hotéis (PCVSH), uma variante do clássico Pro- blema do Caixeiro Viajante (PCV). No PCVSH, existe um limite de tempo imposto a uma jornada diária de trabalho. Desta forma, considerando que há um conjunto de clientes que precisam ser atendidos, há casos em que não é possível atender a todos em um mesmo dia. Levando em consideração esta restrição, é necessário es- colher hotéis, dentre um conjunto previamente fornecido, para que seja realizada a parada entre duas jornadas diárias consecutivas. O objetivo desta dissertação é apresentar, discutir e tratar o Problema do Caixeiro Viajante com Seleção de Hotéis aplicando heurísticas e comparando os resultados obtidos com aqueles disponíveis na literatura. Foram propostas três heurísticas, sendo duas baseadas em Algoritmo Memético (AM) e outra baseada na metaheurística Iterated Greedy (IG), além de um modelo de Programação Linear Inteira alternativo ao existente na literatura. / The optimization of routes is of great interest to companies that provide services related to transportation, being of peoples or goods, as they can lead to a decrease in the time and cost required to provide a service, and consequently to a raise in profitability. In this work we deal with the Travelling Salesperson Problem with Hotel Selection (PCVSH), a variant of the classic Travelling Salesperson Problem (TSP). In PCVSH there is a limit of time imposed to a daily journey of work. Thus, considering that there is a set of customers that need to be visit, there are cases in which one cannot visit all in one day. Considering this restriction, one you must choose hotels, among a previously given set, where a break will take place between two working daily journey. The aim of this work is to present, discuss and solve the Travelling Salesperson Problem with Hotel Selection applying heuristics and comparing the results with those available in the literature. Three heuristics, two based on memetic algorithm (AM) and another based on the metaheuristic Iterated Greedy (IG), and an alternative Integer Linear Programming model to the existing on the literature were proposed.

Orientador: Fernando Antônio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-18T11:42:14Z (GMT). No. of bitstreams: 1 Marques_VitorHugoAlmeida_M.pdf: 2517224 bytes, checksum: e0259e1018ac57ec9a5cb95e0d65284b (MD5) Previous issue date: 2011 / Resumo: Esta dissertação introduz um sistema nebuloso genético (SNG) para adaptação de parâmetros em meta-heurísticas. Duas meta-heurísticas entre as mais usadas foram consideradas como exemplos, algoritmo genético e busca tabu. Os parâmetros trabalhados na busca tabu são relacionados às memórias, de curto prazo e de longo prazo. Já os parâmetros do algoritmo genético a sofrer adaptação são as taxas de reprodução e mutação. Sistemas baseados em regras nebulosas oferecem um mecanismo natural para descrever comportamentos globais como combinação de regras de controle. Eles também herdam um meio de gradualmente alternar entre regras que conjuntamente definem uma estratégia de controle. Dessa forma, esses sistemas são candidatos naturais para construir estratégias de controle de parâmetro porque eles proveem um maneira de desenvolver mecanismos baseados na natureza específica de uma região de busca e as transições entre suas fronteiras. Uma aplicação usando o problema clássico de roteamento de veículos com janela de tempo foi incluído para avaliar o desempenho do sistema nebuloso genético. Resultados experimentais mostram que meta-heurísticas com o mecanismo de adaptação com SNG melhoram o comportamento da busca e a qualidade das soluções quando comparado à versões padrões ( sem SNG ) e com parâmetros constantes dos algoritmos genético e busca tabu. Eles também geram boas soluções sub-ótimas mais rápidas que métodos exatos desenvolvidos para o problema e que são reportados na literatura / Abstract: This dissertation introduces a genetic fuzzy system for parameter adaptation of metaheuristics. Two metaheuristics, among the most used ones, have been considered as examples, genetic algorithm and tabu search. The considered parameters of the tabu search are related to the short and long term memories. Parameters of the genetic algorithm under adaptation are the mutation and reproduction rates. Fuzzy rule-based models offer a natural mechanism to describe global behavior as a combination of control rules. They also inherit a means to gradually shift between control rules which jointly defines a control strategy. They are a natural candidate to construct parameter control strategies because they provide a way to develop decision mechanisms based on the specific nature of search regions and transitions between their boundaries. An application using the classic vehicle routing problem with time windows is included to evaluate the genetic fuzzy system performance. Experimental results show that metaheuristics with GFS improve search behavior and solution quality when compared against standard, constant parameters genetic and tabu search approaches. It also provides reasonably good suboptimal solutions faster than specially tailored exact methods reported in the literature / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T03:16:15Z (GMT). No. of bitstreams: 1 Toledo_FranklinaMariaBragionde_D.pdf: 4584915 bytes, checksum: ea92b2261f5b4ac807705153d2d8ab21 (MD5) Previous issue date: 1998 / Resumo: O problema de dimensionamento de lotes abordado neste trabalho envolve o planejamento da produção de múltiplos itens em períodos de um horizonte finito. O ambiente de produção contém máquinas paralelas distintas com restrições de capacidade. Cada item pode ser produzido em qualquer máquina e para iniciar a produção incorre-se em um tempo de preparação da máquina utilizada. O objetivo é encontrar um plano de produção que minimize a soma dos custos de preparação, produção e estoque e que seja capaz de atender a demanda dos itens sem exceder a capacidade das máquinas. Inicialmente, são apresentados algoritmos de programação dinâmica para o problema sem restrições de capacidade. A seguir, são propostos dois algoritmos branch-andbound que consideram a capacidade limitada das máquinas. O primeiro algoritmo baseia-se numa formulação de programação inteira mista com relaxação lagrangiana das restrições de capacidade do problema. O segundo foi desenvolvido a partir da representação do problema como uma rede generalizada e relaxação linear. Os dois algoritmos ótimos são utilizados para resolver instâncias pequenas e para tratar instâncias maiores foi desenvolvida uma heurística lagrangiana / Abstract: The lotsizing problem addressed in this work involves the production planning of multiple items in periods of finite horizon. The production setting consists of distinct parallel machines with capacity constraints. Each item can be produced on any machine and a setup time is incurred to start production. The objective is to find a production plan which minimizes the sum of setup, production and inventory costs and that is able to satisfy forecast demand for the items without exceeding the capacity of the machines. Initially, dynamic programming algorithms are presented for the problem without capacity constraints. Next, two branch-and-bound algorithms are proposed for the capacitated problem. The first algorithm is based on a mixed integer programming model with lagrangean relaxation of the capacity constraints. The second algorithm was developed from a network representation of the problem and linear relaxation. Both algorithms are used to solve small instances and a lagrangian heuristic is proposed to solve large instances / Doutorado / Doutor em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-24T03:31:34Z (GMT). No. of bitstreams: 1 Cavalcante_CristinaCeliaBarros_M.pdf: 2965474 bytes, checksum: 985e21c3520bb2270df4c0dda2caeaf9 (MD5) Previous issue date: 1998 / Resumo: Esta dissertação estuda o problema de escalonamento com restrição de mão-de-obra (SPLC) e apresenta algumas estratégias para obtenção de limitantes inferiores e de limitantes superiores para este problema NP-difícil. No que diz respeito à obtenção de limitantes inferiores para o SPLC, são apresentadas duas formulações de programação inteira e discutidos os limitantes inferiores obtidos com a relaxação linear de cada uma delas. Um algoritmo de branch-and-bound específico para o SPLC é também implementado na tentativa de se obter soluções exatas para este problema. Finalmente, é introduzida uma extensão, baseada em uma formulação de programação inteira, para um método existente na literatura para o cálculo de limitantes inferiores para problemas de escalonamento com restrição de recursos. Com relação à obtenção de limitantes superiores para o SPLC, são propostas e implementadas quatro estratégias heurísticas seqüenciais (heurística baseada em regras de prioridade, heurística baseada em classes de escalonamento, heurística baseada em programação linear e um algoritmo seqüencial de busca tabu) e duas estratégias paralelas e assíncronas (A-Team e um algoritmo paralelo de busca tabu). Um conjunto de instâncias de teste para o SPLC é gerado e disponibilizado como benchmark para ser usado na avaliação da qualidade dos limitantes inferiores e superiores obtidos neste trabalho e em outros disponíveis na literatura. Embora pouco sucesso tenha sido obtido com as estratégias propostas para obtenção de limitantes inferiores, no caso dos limitantes superiores, as estratégias paralelas e assíncronas propostas e implementadas neste trabalho mostraram-se altamente adequadas à obtenção de soluções de boa qualidade para o SPLC e são, atualmente, responsáveis pelas melhores soluções conhecidas para este problema. / Abstract: This dissertation studies the scheduling problem under labour constraints (SPLC) and presents some strategies to obtain lower and upper bounds for this NP-hard problem. Concerning the lower bounds, two integer programming formulations are presented and the lower bounds associated with their linear relaxations are discussed. A branch-and-bound algorithm is also implemented as an essay to provide exact solutions for this problem. Finally, integer programming is used as a basis to extend a procedure reported in the literature to compute lower bounds for the resourte constrained project scheduling problem. In order to get upper bounds for SPLC, four heuristic approaches (priority rule based heuristic, schedule set based heuristic, linear programming based heuristic and sequential tabu search algorithm) and two parallel strategies (A - Team and parallel tabu search algorithm) are proposed and implemented. A benchmark instance data set for SPLC is generated to be used in the evaluation of the lower and upper bounds obtained in this dissertation and in other works available in the SPLC literature. Although little success has been achieved with respect to the lower bounds, in the case of upper bounds, the parallel strategies proposed in this work have shown the applicability of such techniques in providing high quality solutions for SPLC, and are, presently, responsible for the best known solutions for this problem. / Mestrado / Mestre em Ciência da Computação