Orientador: Maria do Socorro Nogueira Rangel / Banca: Deisemara Ferreira / Banca: Silvio Alexandre Araujo / Resumo: Neste trabalho, propomos um modelo integrado de dimensionamento de lotes e programação da produção para uma fábrica de refrigerantes de pequeno porte denominado P1S1MTS. Neste modelo, as decisões de dimensionamento foram baseadas no modelo P1S1M encontrado na literatura, formulado com base no modelo GLSP. As decisões de sequenciamento foram modeladas utilizando restrições do problema do caixeiro viajante assimétrico. Para validação do modelo proposto e comparação entre os modelos P1S1MTS e P1S1M foram feitos testes computacionais com exemplares ilustrativos. Foram realizados também testes com exemplares baseados em dados reais da fábrica de refrigerantes e exemplares gerados aleatoriamente. Os testes foram resolvidos pelo método Branch-and-Cut incluído no pacote computacional CPLEX 10.0. Notamos que com algumas modificações, é possível que ambos os modelos retratem a mesma situação. A partir destas modificações e com os resultados obtidos, concluímos que a resolução de exempalres do modelo P1S1MTS apresentou um tempo de execução computacioanl menor que a resolução de exemplares do modelo P1S1M gerados com os mesmos dados. / Abstract: In this work we propose a lot sizing and scheduling model, P1S1MTS, for a smallscale soft drink plant. In this model, the lot sising decisions were based on the P1s!m model found in the literaure. To model the scheduling decisions constraints of the asynmetric traveling salesman problem are used. For the validation of the proposed model and a comparison between the P1S1MTS and the P1S1M models computational tests were executed with illustratuve examples. Tests were also executed with examples based on real data and randomly generated instances. Tests were also executed with examples based on real data and randomly in the software CPLEX 10.0. The results showed taht, with some minor modifications, it is possible that both models depict same situation. From the results obtained we concluded that the P1s!MTS model presented a computational time performance better than the P1S1M model. / Mestre

Orientador: Maria do Socorro Nogueira Rangel / Banca: Horácio Hideki Yanasse / Banca: Silvio Alexandre de Araújo / Resumo: Neste trabalho, analisamos os padrões de corte adotados por uma Indústria de Móveis, e identificamos suas características básicas. Definimos, a partir dessas características, os padrões tabuleiros compostos, que pertencem a classe dos padrões de corte n-grupos, apresentada por Gilmore e Gomory (1965). Os padrões tabuleiros compostos preservam as facilidades de corte dos padrões tabuleiros, apresentando melhores índices de sobra de matéria-prima. Propomos uma heurística para a geração de um pool de padrões tabuleiros compostos, usados para resolver o problema de corte de estoque na indústria de móveis. / Abstract: In this work, we analyze the cutting patterns used by a furniture Industry, and we determine some of its basic characteristics. We defined a composed checkerboard pattern, that belongs to the class of n-groups cutting patterns, presented by Gilmore and Gomory (1965). The composed checkerboard patterns preserve the easiness of the cutting process and have better indexes of waste. We propose a heuristic to generate a pool of composed checkerboard patterns to solve the cutting stock problem in the furniture Industry. / Mestre

Made available in DSpace on 2014-06-11T19:30:10Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-08-14Bitstream added on 2014-06-13T20:20:28Z : No. of bitstreams: 1 rodriguez_lao_me_guara.pdf: 898092 bytes, checksum: 45f1b8e53bd80272f863dee05c614945 (MD5) / Para enfrentar os problemas do atual mundo globalizado e para se manter em atividade, as empresas vêm sendo obrigadas a empregar, em seu dia-a-dia, novos instrumentos de trabalho. A Teoria das Restrições, a Programação Linear Inteira e a Simulação de Sistemas surgem como potenciais ferramentas no auxílio à identificação e à solução dos problemas enfrentados pelas empresas nos dias de hoje. Este trabalho teve por objetivo principal desenvolver um método de planejamento e gerenciamento da produção, integrando essas três ferramentas. O método foi aplicado na linha de produção da Unidade de Cilindros para Laminação da empresa Aços Villares S/A com o intuito de melhorar o fluxo de produção e o cumprimento do prazo de liberação do produto entre as suas diversas áreas. Ao final do trabalho, concluiu-se que o referido método, além de facilitar e simplificar o processo de modelagem permite realizar análises mais aprofundadas do sistema real, em relação às que seriam conseguidas com a utilização das técnicas citadas, isoladamente. / In order to face the issues of the current globalized world and in order to keep working, companies have been pushed to put in practice new working tools. The Theory of Constraints, the Integer Linear Programming and the Systems Simulation appear as potential tools to support problem identification and solution which are faced by companies nowadays. This work aims to develop a planning and management method of production integrating these three tools. The method was applied to the production line at Aços Villares S/A Rolling Mill Roll Unit aiming at improving the production flow and the accomplishment of product liberation deadline among its many areas. At the end of this work, it has been concluded that the referred method, besides facilitating and simplifying the modeling process, it allows to achieve deeper analyses of the real system in relation to those which would be reached with the isolated mentioned techniques.

A localização de fábricas, fornecedores e/ou CDs é um problema de grande complexidade, principalmente em empresas com operações internacionais. Na literatura mundial são poucos os modelos desenvolvidos que tratam da localização de instalações em escala global. Este trabalho propõe um modelo de Programação Linear Inteira Mista que soluciona o problema minimizando os custos logísticos (custos fixos, custos de transferência, custos de distribuição, impostos não recuperáveis, estoques, take-or-pay, matéria-prima e custos de agregação de valor e transbordo) levando em consideração vários elos da cadeia de suprimentos. Como principais contribuições do modelo citam-se a inclusão de benefícios fiscais em transações internacionais, tais como o drawback, o cálculo pioneiro para custo no carregamento dos estoques e o tratamento dado aos custos tipo take-or-pay. São sugeridas adaptações do modelo para utilização em quaisquer segmentos de indústria. O modelo foi aplicado com sucesso em um caso real de uma indústria do segmento químico. / The location of factories, suppliers and distribution centers has always been a problem of great complexity, mainly for companies with global operations. In the literature, there are a few models developed for facilities location in a global scale. This work proposes a Mixed Integer Linear Programming model that solves the problem minimizing the total logistic cost (fixed, transfer and distribution costs, non recoverable duties, carrying, take-or-pay, raw material, added value and handling costs) taking into consideration several echelons in the supply chain network. The main contributions of the proposed model are the considerations regarding fiscal benefits in international trade such as drawback, the pioneer carrying cost calculation and the treatment given to the take-or-pay costs. Some adaptations of the model have been suggested for use in any type of industry. The model was successfully applied in a real case of a chemical industry.

A seleção de fornecedores é um problema complexo e que vem ganhando importância estratégica nas organizações, principalmente devido à inclusão de diversos atributos que podem ser especificados de acordo com as necessidades da situação, pois o fator custo não é mais o único responsável pela decisão. A relevância da sustentabilidade, em termos econômicos, ambientais e sociais, traz ao tema ainda mais atributos que devem ser mapeados como parte da decisão. Neste trabalho é proposta uma abordagem baseada em otimização combinatória (programação linear inteira) aliada à análise de valor multicriterial que estabelece prioridades e compensações entre os atributos definidos, para seleção de fornecedores de um conjunto de embalagens de cosméticos para uma nova linha de produtos. A solução encontrada é comparada aos métodos de otimização tradicionais (monocriteriais) e à otimização multicriterial sem leilão combinatório. Também são realizadas análises de sensibilidade com o modelo, permitindo que sejam feitas validações de forma a justificar a decisão. / Supplier selection is a complex issue that has gained strategic importance in organizations, mainly due to the consideration of several criteria that can be specified according to the situation, since cost is no longer solely responsible for the decision. The sustainability relevance, in economical, environmental and social terms, brings to the theme even more criteria that should be included as part of the decision. This work proposes an approach based on combinatorial optimization (integer linear programming) combined with multi-criteria value analysis that establishes priorities and trade-offs among the defined criteria, to the supplier selection of a cosmetics packaging set for a new product line. The obtained solution is compared to traditional optimization methods (mono-criteria) and to the multi-criteria optimization without combinatorial auction. Sensitivity analyses are also performed with the model, allowing assessments to be made in order to justify the decision.

Esta pesquisa aborda o problema de alocação de jatos executivos compartilhados para casos em que a demanda diária é variável. É proposta uma ferramenta auxiliar de planejamento de uma empresa de operação de jatos compartilhados. São apresentadas as características principais do tipo de negócio que formam o problema estudado neste trabalho. Consideram-se os aspectos de uma empresa que administra jatos de propriedade compartilhada. O cliente adquire uma cota de uma aeronave e quando solicita uma viagem, com poucas horas de antecedência, a empresa deve garantir a realização do voo em uma aeronave da categoria adquirida. Também é de responsabilidade da empresa a gestão da tripulação, o reposicionamento da frota e a manutenção das aeronaves Este trabalho apresenta o desenvolvimento de uma ferramenta para auxiliar na tomada de decisões estratégicas que envolvem a escolha dos locais de base de operação e o dimensionamento da frota. A metodologia de solução é composta de um modelo de simulação e um de otimização. O modelo de simulação utiliza o método de Monte Carlo para obtenção da demanda de voos dia a dia que gera uma programação de clientes a atender. Os dados da simulação são então estruturados como um problema de fluxo em rede de mínimo custo e é realizada a alocação ótima das aeronaves. A ferramenta foi construída em ambiente de planilha eletrônica Microsoft Excel e aplicada em um caso prático de jatos executivos compartilhados com múltiplas bases. Foram testadas diversas configurações de bases e políticas operacionais como frota homogênea, frota heterogênea e frota alugada. Os resultados da ferramenta permitem determinar o impacto que a escolha das bases de operação tem no tamanho da frota e no reposicionamento de aeronaves. A metodologia mostrou-se robusta e, em tempo adequado, a ferramenta encontrou a solução ótima para cada configuração testada. / This research deals with the problem of scheduling jets with fractional ownership in cases where the demand varies daily. It has been devised a tool to support the planning phase of a company that operates shared jets. The main characteristics of the fractional shared market are presented in this manuscript and the research was developed under the point of view of a provider of fractional ownership. A client becomes a partial owner of an aircraft of a specific model and is entitled to a certain amount of flight hours. When the client requests a flight, usually only a few hours ahead, the fractional provider must guarantee that an aircraft of the requested model is available to the owner at the requested time and place. The provider is responsible for all the operational considerations, including managing the crew and having a well-maintained fleet. This work presents the development of a tool to help making decisions involving the choice of the operational bases and the size of the fleet. The solution methodology is composed of a simulation and a optimization model. Monte Carlo simulation is the method used to obtain the daily flight demand. The results of the simulation are structured as a minimum cost network flow problem to solve optimally the fleet allocation. This tool has been built in a Microsoft Excel spreadsheet environment and applied to a case of fractional jets with multiple bases. Several configurations and operational policies have been tested, such as operations with homogenous fleet, with heterogeneous fleet and with rented fleet. The results provided by the tool allow the user to evaluate the impact that the choice of the operational bases has on the size of the fleet and on the redeployment of the aircrafts. The methodology presented itself as adequate and the developed tool was able to solve optimally, in acceptable time, the problem for each case.

A presente pesquisa aborda um problema de roteirização e programação de veículos incorporando uma nova restrição operacional: a requisição simultânea de múltiplos veículos para atendimento da demanda. Trata-se de uma característica encontrada em operações de apoio à exploração de petróleo \"offshore\", em que mais de uma embarcação é requerida para executar tarefas de reboque e lançamento de linhas de ancoragem. Esta imposição, somada às restrições de janela de tempo, precedência entre tarefas, autonomia das embarcações e atendimento integral da demanda, configuram este problema. A programação é orientada pela minimização dos custos variáveis da operação e dos custos associados ao nível de serviço no atendimento. Este problema é uma variação do problema clássico de roteirização e programação de veículos com janela de tempo, de classe NP-Difícil. Nesta pesquisa, propõe-se modelar e resolver o problema em escala real por meio do algoritmo \"branch and cut\" acoplado às heurísticas de busca em vizinhança \"local branching\" e \"variable neighborhood search\". Para gerar as soluções iniciais será empregado o método \"feasibility pump\" e uma heurística construtiva. / This research focuses a fleet scheduling problem with new operational constraints: each task requiring multiple types of vehicles simultaneously. This kind of operation occurs in offshore exploitation and production sites, when more than one vessel is needed to accomplish the tugging and mooring of oil platforms. Other constraints are maintained such as time windows, precedence between tasks, route duration and the demand attendance. The solution schedules are cost oriented, which encompasses the routing variable costs and the customer service costs. This is a variation of the classical fleet routing and scheduling, which is an NP-Hard problem. This research aims to solve the real scale problem through a combined use of branch and cut strategy with local search algorithms such as local branching and variable neighborhood search. An efficient heuristic rule will be used in order to generate initial solutions using the feasibility pump method.

Orientador: Vinícius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T07:40:14Z (GMT). No. of bitstreams: 1 Sacchi_LuisHenrique_D.pdf: 1448719 bytes, checksum: f89915d271683e250283d8ec86b25839 (MD5) Previous issue date: 2010 / Resumo: Este trabalho apresenta um estudo computacional da busca tabu paramétrica para resolver problemas de programação inteira mista (PIM) com variáveis binárias. Trata-se de uma heurística genérica para problemas PIM gerais que resolve uma série de problemas de programação linear ao incorporar inequações de ramificação de variáveis inteiras como termos ponderados na função objetivo. O procedimento central do método é baseado em memória de curto prazo da busca tabu, enquanto fases de intensificação e diversificação são induzidas pela memória de longo prazo baseada em freqüência e idéias derivadas de scatter search. Novas estratégias são propostas para encontrar soluções de alta qualidade e extensivos testes computacionais são realizados em instâncias da literatura / Abstract: We present a computational study of parametric tabu search for solving 0-1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems that solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. The core procedure is founded on short term memory, whereas both intensification and diversification phases are induced by long term memory based on frequency and ideas derived from scatter search. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature / Doutorado / Automação / Doutor em Engenharia Elétrica

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this paper we present some counting tools like graphs and generating functions. Before we discuss about the basics of counting that are additive and multiplicative principles. At the end we show an algorithm that calculates the number of integer partitions that inherently uses the idea of graphs. / Neste texto apresentaremos algumas ferramentas de contagem como grafos e funções geradoras. Antes discutiremos sobre os princípios básicos de contagem que são os princípios aditivo e multiplicativo. Ao final exibiremos um algoritmo que calcula o número de partições de inteiros que utiliza intrinsecamente a ideia de grafos.

Orientador: Cid Carvalho de Souza / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:41:44Z (GMT). No. of bitstreams: 1 Hoshino_EdnaAyako_D.pdf: 1434503 bytes, checksum: c1b32d8a6dc810d6d7ff6100d1a77c79 (MD5) Previous issue date: 2009 / Resumo: Nesta tese,dois problemas de otimização combinatória em grafos são modelados por programação linear inteira e resolvidos através de técnicas de geração de colunas. Os dois casos correspondem a generalizações de problemas clássicos em grafos e que ocorrem em muitas situações práticas. O primeiro, chamado problema dos anéis-estrelas capacitados, é uma generalização do problema de roteamento de veículos e modela situações reais encontradas nas áreas de logística de distribuição e de transporte. O segundo, conhecido por problema da coloração particionada, generaliza o problema da coloração de vértices em grafos e ocorre em aplicações no projeto de redes ópticas. As formulações de programação linear inteira desenvolvidas neste trabalho para modelar ambos os problemas estão relacionadas 'a técnica da decomposição de Dantzig-Wolfe e usam uma quantidade exponencialmente grande de variáveis de decisão . Nestas formulações, cada uma das variáveis representa uma estrutura específica do problema sendo estudado. No problema dos anéis-estrelas capacitados, cada variável está associada a um anel-estrela e, no problema da coloração particionada, a um conjunto independente. As relaxações lineares destes tipos de modelos, em geral, apresentam limitantes duais mais apertados que outros modelos compactos, isto é, definidos para um número polinomial de variáveis. Nesta tese, nós avaliamos estas novas formulações, comparando-as com outros modelos conhecidos para os problemas estudados. Além disso, nos dois casos, projetamos e implementamos algoritmos exatos do tipo branch-and-price e/ou branch-and-cut-and-price capazes de computar os modelos propostos. Experimentos computacionais foram realizados com estes algoritmos que confirmaram a adequação das técnicas aqui empregadas. Tanto para o problema dos anéis-estrelas capacitados quanto para o problema da coloração particionada, os resultados alcançados por nós foram comparados com aqueles reportados na literatura e mostraram que os algoritmos baseados em geração de colunas tiveram desempenho melhor que os algoritmos propostos anteriormente / Abstract: In this thesis, two combinatorial optimization problems are modeled by integer linear programming and solved using the column generation technique. Both cases correspond to generalizations of classical problems in graphs that occur in many practical situations. The first, called capacitated ring-star problem is a generalization of the vehicle routing problem and models real situations found in logistics and transportation. The second, known as the partition coloring problem, generalizes the vertex coloring problem in graphs and arises in design of fiber optics networks. The integer linear programming formulations developed in this work to model both problems are related to the Dantzing-Wolfe decomposition and use exponential number of decision variables. In these formulations, each decision variable represents a specific structure of the problem under study. For the capacitated ring-star problem, each variable is assigned to a ring-star and, for the partition coloring problem, to an independent set. The linear relaxation of this kind of model in general leads to tighter dual bounds than the ones obtained from compact models, i.e., defined over a polynomial number of variables. In this thesis, we evaluated both new formulations, comparing them to other known models for the respective problems. Moreover, in both cases, we designed and implemented exact branch-and-price and/or branch-and-cut-and-price algorithms that are able to solve the proposed models. Computational experiments were performed with these algorithms and showed that the used techniques were adequate. Both for the capacitated ring-star problem and for the partition coloring problem, we compared our results with those reported in the literature and showed that the algorithms based on column generation outperformed the previous ones / Doutorado / Otimização Combinatoria / Doutor em Ciência da Computação