Orientador: Maria do Socorro Nogueira Rangel / Banca: Horácio Hideki Yanasse / Banca: Silvio Alexandre de Araújo / Resumo: Neste trabalho, estudamos o Problema de Corte de Estoque Bidimensional aplicado à indústria de móveis. Para realizar este estudo, visitamos uma empresa característica do noroeste paulista com o intuito de observarmos a prática da empresa e desenvolver métodos de solução para aumentar sua produtividade. O critério de otimização considerado é a redução do número de ciclos da serra. Três métodos de solução foram propostos para a resolução do problema. O primeiro utiliza um modelo matemático que contém restrições que garantem que o número de objetos cortados de acordo com um determinado padrão de corte seja um múltiplo da capacidade da serra. Duas heurísticas, baseadas na heurística de repetição exaustiva de padrões de corte, são propostas para atender exatamente às demandas e reduzir o número de ciclos da serra na indústria de móveis visitada. Os estudos computacionais realizados, mostraram que as estratégias propostas obtêm resultados próximos aos da empresa e, em alguns casos, melhores. / Abstract: In this work we have studied the Two-dimensional Cutting Stock Problem applied to a furniture industry. In order to carry out this study, we have visited a characteristic company at the Northwest region of the state of São Paulo in order to observe the industry practice and develop solution methods to increase its productivity. The goal is minimize the number of saw cycles. We propose three solution methods to solve the problem. The first one is a mathematical model which imposes that the number of objects to be cut according to a given cutting pattern is a "multiple" of the saw capacity. Two heuristics based on the sequential heuristic procedure are proposed to fulfil the demands and to reduce the number of saw cycles. By the computational tests results, we can conclude that these solution methods provide similar results to the industry's practice and, in some cases, better ones. / Mestre

PETROBRAS / Este trabalho apresenta uma abordagem para otimização do scheduling de uma rede dutoviária real com uma origem e múltiplos destinos, a rede OSBRA. A rede é composta por uma refinaria que abastece cinco órgãos ligados por um único poliduto. Decisões sobre bateladas (volumes operacionais) de diferentes produtos a serem enviados pela refinaria e recebidos nos órgãos de consumo ao longo de um horizonte de tempo devem ser tomadas de modo otimizado de forma a controlar os níveis de estocagem, respeitando limites operacionais da rede de dutos. Propõe-se uma abordagem de solução por decomposição que utiliza Programação Linear Inteira Mista (PLIM) em conjunto com algoritmos heurísticos. A abordagem está dividida em 2 etapas: (i) alocação e sequenciamento e (ii) programação das entregas. A etapa de alocação e sequenciamento é responsável por determinar a ordem, o volume e a vazão de cada batelada que deverá ser bombeada da refinaria para os órgãos. Esta etapa é composta por um modelo PLIM que é executado iterativamente em uma abordagem com horizonte com tempo rolante. Em seguida, a etapa de programação de entregas detalha como ocorrem as entregas das bateladas em cada órgão, considerando a operação de rebombeio no último trecho de duto. Para o rebombeio, executa-se um modelo matemático iterativamente também utilizando o conceito de horizonte rolante, definindo uma nova sequência de bateladas que deverão ser bombeadas pelo órgão de Goiânia para Brasília, ou seja, no trecho de duto mais distante da refinaria. Consideram-se características próximas da realidade de operação da rede OSBRA, como controle de inventário, limites de vazão, variação diária de demanda, manutenção de tanque, manutenção de duto (total ou parcial). Dois estudos de caso são apresentados considerando cenários baseados em dados reais com horizontes de programação de 30 dias, no qual o segundo foi submetido a diversas modificações com o intuito de evidenciar funcionalidades da abordagem proposta. A análise dos resultados permite concluir que a abordagem de solução apresenta resultados adequados para a operação dos especialistas da rede, dessa forma podendo auxiliar no processo de decisão do scheduling da rede OSBRA. / This work presents an approach to optimize the scheduling of a real pipeline network with one source and multiple destinations, the OSBRA network. The network consists of a refinery that supplies five terminals, which are connected by a single pipeline. Batches of different products are sent from refinery and received by terminals during a time horizon. Optimized scheduling decisions must be taken to attend inventory issues at the same time that operational constraints are respected. This work proposes a decomposition approach solution using Mixed Integer Linear Programming (MILP) combined with heuristic algorithms. The solution approach is divided into two phases: (i) allocation and sequencing and (ii) scheduling of deliveries. The allocation and sequencing phase is responsible for determining the order, volume, and flow rate of each batch to be pumped from the refinery to the terminals. This phase is composed of an MILP model that runs iteratively in a rolling horizon approach. In a following step, the scheduling of deliveries phase details how the batches' deliver will occur in each terminal, considering the repumping operation in the last pipeline segment. For the repumping, a mathematical model is executed iteratively, also using the concept of rolling horizon, setting a new sequence of batches to be pumped from Goiânia to Brasília, the farthest pipeline segment from the refinery. Similar characteristics of the real OSBRA network are considered, such as inventory control, flow limits, daily demand, tank maintenance, total or partial pipeline maintenance. Two study cases considering scenarios based on real data with a 30-day programming horizon are presented, in which the second case was subjected to a series of modifications in order to evidence the proposed approach functionalities. The result's analysis supports the conclusion that the solution approach provides adequate results for the operation of the network experts. Thus, the obtained results can aid the operational scheduling decision of OSBRA network.

O estudo tem como finalidade tratar a alocação de recursos no nível operacional com a presença de incertezas. Para isso, foi proposta uma abordagem de otimização usando métodos heurísticos. As soluções de problemas de produção e logística, comumente abordadas em pesquisa operacional, exploram diversos parâmetros dentre os quais o presente estudo considera três como de incerteza: demanda, tempo de execução e indisponibilidade de recursos. Para tal finalidade foi escolhido como estudo de caso a resolução de um problema de logística. O problema consiste na minimização dos custos de operação, na seleção de veículos em uma frota heterogênea, consolidação das cargas para cada cliente e na seleção do tipo de frete utilizado. Quanto ao tipo de frete, são considerados dois, os quais se diferenciam quanto aos ativos envolvidos na produção e ao tipo de prestação de serviço, sendo eles: i) frota da empresa com serviço terceirizado; ii) frota e serviços totalmente terceirizados. O problema original foi decomposto em duas etapas: i) Compartimentalizador e ii) Alocador. As duas etapas são solucionadas via a abordagem de Busca Tabu, sendo que a primeira etapa (Compartimentalizador) gera uma lista dos carregamentos factíveis que atenda pedidos de até três clientes distintos. O Alocador se utiliza da lista dos carregamentos factíveis para definir como e quando cada pedido será atendido. Os resultados indicam a viabilidade da adoção desta abordagem para a solução de problemas reais. / The study aims to address the allocation of resources at the operational level under uncertainties. For this reason, it was proposed an optimization approach based on heuristic methods. The resolutions of production and logistics problems, commonly addressed in operational research, explore various parameters among which the present study considers three variables of uncertainty: demand, operation time and resources availability. For this purpose a logistics problem was chosen as study of case. The problem consists in minimizing cost operation, selection of vehicles in a heterogeneous fleet, consolidation of loads for each client and selecting the type of freight payables. Regarding of freight payables types, there are centered in two different tariffs, mainly due to assets and service negotiation, such as: i) fleet controlled by company and service outsource; ii) fleet and service completely outsource. The resolution of the original problem was broke down in two steps: i) Compartmentalizer and ii) Allocator. Both steps are solved through Tabu Search approach; the first step (Compartmentalizer) generates a list of feasible shipments to fulfill orders up to three different customers. The second step, the allocator uses the list of feasible shipments to define how and when each request will be supplied. The results aim the feasibility of assumes this approach in order to solve real problems.

Fundação Araucária; RENAULT; Seti / A Pesquisa Operacional investiga as (melhores) formas de se configurar e coordenar sistemas ou operações usando técnicas de otimização. Geralmente, a otimização de um sistema é modelado com base no estado final almejado. Porém, como atingir ou implementar tal estado final em sistemas é pouco retratado na literatura. Esta dissertaçãode mestrado propõe uma nova classe de problema de otimização: a programação das operações entre o estado inicial e o final de um sistema, o Problema de Implementação. A programação das operações é especialmente importante para linhas de montagem. A indústria automobilística é fortemente baseada em linhas de produção que podem ser usadas até 24 horas por dia. Assim, as oportunidades de intervenções para mudar ou otimizar o sistema produtivo são poucas. As condições de implementação aplicadas ao balanceamento de linhas produtivas são discutidas, e as características observadas resultam no proposto Problema de Implementação de Linhas de Montagem (PILM). Na dissertação, um guia de modelagem baseado em Programação Linear Inteira Mista (PLIM) é desenvolvido para a formulação de diversas variações do Problema de Implementação. As instruções de modelagem são usadas para desenvolver um conjunto de modelos PLIM para o Problema de Implementação de Linhas de Montagem. Para a obtenção de resultados, um conjunto de instâncias é proposto. Assim, uma análise de sensibilidade em função de cada um dos parâmetros formadores das instâncias é realizada. As formulações são comparadas, junto com as diferentes formas de apresentar e resolver o problema. Ademais, um método de decomposição é usado para resolver um problema industrial real. A modelagem mostrase correta para a divisão da implementação de mudanças em linhas de montagem. Os resultados mostram que a divisão do esforço de implementação resulta em apenas poucas mudanças a mais (cerca de 7% para os casos pequenos e médios) comparadas com a implementação em uma fase. A possibilidade de programar a implementação em etapas menores aumenta a aplicabilidade de projetos, que, de outra forma, requeririam grande paradas de produção. / Operations Research investigates the (best) ways to configure and coordinate systems or operations with optimization procedures. Usually, the optimization of a system is modeled based on the aimed final configuration. However, little is published about how to reach or implement such optimal configurations in the systems. This master thesis proposes a new class of optimization problem: a scheduling of operations between initial and final states of a system, the Implementation Problem. The scheduling of operations is especially important to assembly lines. The automotive industry strongly relies on production lines that can operate 24 hours a day. Thus, the intervention opportunities to change or optimize the production system are very few. The implementation conditions of balancing on assembly lines are discussed, and the observed characteristics result in the proposal of the Assembly Line Implementation Problem (ALIP). The master thesis proposes a Mixed-Integer Linear Programming (MILP) modeling guide for the formulation of several variations of Implementation Problems. The modeling instructions are used to develop a set of MILP models for the Assembly Line Implementation Problem. For the results, a dataset is proposed and a sensitivity analysis on each of the consistent parameters of the dataset is performed. The proposed formulations are compared, along with the different forms of presenting and solving the problem. Furthermore, a decomposition method is used to solve a real-world industrial problem. The modeling correctly represents the division of the implementation of changes in assembly lines. The results show that the division of the effort in multiple stages only need a few more changes (around 7\% for the small and medium cases) comparing to a straightforward implementation. The possibility of scheduling the implementation in smaller steps increases the applicability of projects that otherwise would require a large system's stoppage time.

Fundação Araucária; CNPq; RENAULT; Seti / As linhas de montagem que envolvem soldagem por pontos estão amplamente presentes na indústria de fabricação automotiva. O processo de montagem da estrutura do veículo emprega vários robôs equipados com ferramentas de soldagem por pontos. Estes robôs e ferramentas possuem altos custos, fazendo surgir a necessidade de projetar a linha cuidadosamente, atendendo à demanda do produto e reduzindo as despesas ao mesmo tempo. Nesta dissertação, propõe-se e estuda-se o problema do Projeto de Linha de Montagem Robótica (PLMR), com base nas características práticas de uma empresa automotiva localizada no Brasil. Desenvolve-se um modelo de Programação Linear Inteira Mista (PLIM) que permite: (i) paralelização de estações, (ii) seleção de equipamentos e (iii) múltiplos robôs por estação de trabalho. O modelo matemático visa minimizar o custo total à uma taxa de produção desejada, o que envolve robôs, ferramentas e instalações. O modelo proposto considerou o tempo morto durante um ciclo, restrições de espaço, restrições de alocação de tarefas e possibilidades de paralelismo. O tempo morto é um tempo improdutivo e fixo do trabalho de manuseio de peças que acompanha o tempo de movimento dos robôs transportadores capacitados. Experimentos computacionais foram realizados para evidenciar a influência dos parâmetros sobre a solução ótima do projeto de linha. Além disso, foram realizados estudos de casos práticos com parâmetros reais coletados de uma linha de montagem robotizada para soldagem, localizada na região metropolitana de Curitiba-PR, chegando à otimalidade. Em comparação com as linhas estritamente seriais, o modelo mostrou grandes vantagens ao permitir paralelizar as estações no sistema de produção, permitindo avaliar uma compensação entre a taxa de produção e o custo total. / Spot welding assembly lines are widely present in the automotive manufacturing industry. The procedure of building the vehicle’s body employs several robots equipped with spot welding tools. These robots and tools are quite costly, arising the necessity of designing the line consciously, meeting the product demand and reducing expenses at the same time. In this master thesis, the Robotic Assembly Line Design (RALD) problem is proposed and studied based on practical characteristics from an automotive company located in Brazil. A Mixed-Integer Liner Programming (MILP) formulation is developed allowing: (i) station paralleling, (ii) equipment selection, and (iii) multiples robots per workstation. The mathematical model aims at minimising the total cost at the desired production rate, which involves robots, tools and facilities. The proposed model considered dead time during a cycle, space constraints, task assignment restrictions, and parallelism possibilities. Dead time is an unproductive and fixed work-piece handling time that accompany the capacitated transporter robots’ movement time. Computational experiments were performed in order to evidence the parameters’ influence over the optimal line design solution. In addition, practical case studies were conducted with parameters collected from a real-world robotic welding assembly line located on the outskirts of Curitiba-PR (Brazil), reaching optimality. Compared to the strictly serial lines, the model led to great advantages by allowing station paralleling in the production system, making it possible to evaluate an expected trade-off between the production rate and the total cost.

PETROBRAS / Este trabalho apresenta uma abordagem para otimização do scheduling de uma rede dutoviária real com uma origem e múltiplos destinos, a rede OSBRA. A rede é composta por uma refinaria que abastece cinco órgãos ligados por um único poliduto. Decisões sobre bateladas (volumes operacionais) de diferentes produtos a serem enviados pela refinaria e recebidos nos órgãos de consumo ao longo de um horizonte de tempo devem ser tomadas de modo otimizado de forma a controlar os níveis de estocagem, respeitando limites operacionais da rede de dutos. Propõe-se uma abordagem de solução por decomposição que utiliza Programação Linear Inteira Mista (PLIM) em conjunto com algoritmos heurísticos. A abordagem está dividida em 2 etapas: (i) alocação e sequenciamento e (ii) programação das entregas. A etapa de alocação e sequenciamento é responsável por determinar a ordem, o volume e a vazão de cada batelada que deverá ser bombeada da refinaria para os órgãos. Esta etapa é composta por um modelo PLIM que é executado iterativamente em uma abordagem com horizonte com tempo rolante. Em seguida, a etapa de programação de entregas detalha como ocorrem as entregas das bateladas em cada órgão, considerando a operação de rebombeio no último trecho de duto. Para o rebombeio, executa-se um modelo matemático iterativamente também utilizando o conceito de horizonte rolante, definindo uma nova sequência de bateladas que deverão ser bombeadas pelo órgão de Goiânia para Brasília, ou seja, no trecho de duto mais distante da refinaria. Consideram-se características próximas da realidade de operação da rede OSBRA, como controle de inventário, limites de vazão, variação diária de demanda, manutenção de tanque, manutenção de duto (total ou parcial). Dois estudos de caso são apresentados considerando cenários baseados em dados reais com horizontes de programação de 30 dias, no qual o segundo foi submetido a diversas modificações com o intuito de evidenciar funcionalidades da abordagem proposta. A análise dos resultados permite concluir que a abordagem de solução apresenta resultados adequados para a operação dos especialistas da rede, dessa forma podendo auxiliar no processo de decisão do scheduling da rede OSBRA. / This work presents an approach to optimize the scheduling of a real pipeline network with one source and multiple destinations, the OSBRA network. The network consists of a refinery that supplies five terminals, which are connected by a single pipeline. Batches of different products are sent from refinery and received by terminals during a time horizon. Optimized scheduling decisions must be taken to attend inventory issues at the same time that operational constraints are respected. This work proposes a decomposition approach solution using Mixed Integer Linear Programming (MILP) combined with heuristic algorithms. The solution approach is divided into two phases: (i) allocation and sequencing and (ii) scheduling of deliveries. The allocation and sequencing phase is responsible for determining the order, volume, and flow rate of each batch to be pumped from the refinery to the terminals. This phase is composed of an MILP model that runs iteratively in a rolling horizon approach. In a following step, the scheduling of deliveries phase details how the batches' deliver will occur in each terminal, considering the repumping operation in the last pipeline segment. For the repumping, a mathematical model is executed iteratively, also using the concept of rolling horizon, setting a new sequence of batches to be pumped from Goiânia to Brasília, the farthest pipeline segment from the refinery. Similar characteristics of the real OSBRA network are considered, such as inventory control, flow limits, daily demand, tank maintenance, total or partial pipeline maintenance. Two study cases considering scenarios based on real data with a 30-day programming horizon are presented, in which the second case was subjected to a series of modifications in order to evidence the proposed approach functionalities. The result's analysis supports the conclusion that the solution approach provides adequate results for the operation of the network experts. Thus, the obtained results can aid the operational scheduling decision of OSBRA network.

O estudo tem como finalidade tratar a alocação de recursos no nível operacional com a presença de incertezas. Para isso, foi proposta uma abordagem de otimização usando métodos heurísticos. As soluções de problemas de produção e logística, comumente abordadas em pesquisa operacional, exploram diversos parâmetros dentre os quais o presente estudo considera três como de incerteza: demanda, tempo de execução e indisponibilidade de recursos. Para tal finalidade foi escolhido como estudo de caso a resolução de um problema de logística. O problema consiste na minimização dos custos de operação, na seleção de veículos em uma frota heterogênea, consolidação das cargas para cada cliente e na seleção do tipo de frete utilizado. Quanto ao tipo de frete, são considerados dois, os quais se diferenciam quanto aos ativos envolvidos na produção e ao tipo de prestação de serviço, sendo eles: i) frota da empresa com serviço terceirizado; ii) frota e serviços totalmente terceirizados. O problema original foi decomposto em duas etapas: i) Compartimentalizador e ii) Alocador. As duas etapas são solucionadas via a abordagem de Busca Tabu, sendo que a primeira etapa (Compartimentalizador) gera uma lista dos carregamentos factíveis que atenda pedidos de até três clientes distintos. O Alocador se utiliza da lista dos carregamentos factíveis para definir como e quando cada pedido será atendido. Os resultados indicam a viabilidade da adoção desta abordagem para a solução de problemas reais. / The study aims to address the allocation of resources at the operational level under uncertainties. For this reason, it was proposed an optimization approach based on heuristic methods. The resolutions of production and logistics problems, commonly addressed in operational research, explore various parameters among which the present study considers three variables of uncertainty: demand, operation time and resources availability. For this purpose a logistics problem was chosen as study of case. The problem consists in minimizing cost operation, selection of vehicles in a heterogeneous fleet, consolidation of loads for each client and selecting the type of freight payables. Regarding of freight payables types, there are centered in two different tariffs, mainly due to assets and service negotiation, such as: i) fleet controlled by company and service outsource; ii) fleet and service completely outsource. The resolution of the original problem was broke down in two steps: i) Compartmentalizer and ii) Allocator. Both steps are solved through Tabu Search approach; the first step (Compartmentalizer) generates a list of feasible shipments to fulfill orders up to three different customers. The second step, the allocator uses the list of feasible shipments to define how and when each request will be supplied. The results aim the feasibility of assumes this approach in order to solve real problems.

Fundação Araucária; RENAULT; Seti / A Pesquisa Operacional investiga as (melhores) formas de se configurar e coordenar sistemas ou operações usando técnicas de otimização. Geralmente, a otimização de um sistema é modelado com base no estado final almejado. Porém, como atingir ou implementar tal estado final em sistemas é pouco retratado na literatura. Esta dissertaçãode mestrado propõe uma nova classe de problema de otimização: a programação das operações entre o estado inicial e o final de um sistema, o Problema de Implementação. A programação das operações é especialmente importante para linhas de montagem. A indústria automobilística é fortemente baseada em linhas de produção que podem ser usadas até 24 horas por dia. Assim, as oportunidades de intervenções para mudar ou otimizar o sistema produtivo são poucas. As condições de implementação aplicadas ao balanceamento de linhas produtivas são discutidas, e as características observadas resultam no proposto Problema de Implementação de Linhas de Montagem (PILM). Na dissertação, um guia de modelagem baseado em Programação Linear Inteira Mista (PLIM) é desenvolvido para a formulação de diversas variações do Problema de Implementação. As instruções de modelagem são usadas para desenvolver um conjunto de modelos PLIM para o Problema de Implementação de Linhas de Montagem. Para a obtenção de resultados, um conjunto de instâncias é proposto. Assim, uma análise de sensibilidade em função de cada um dos parâmetros formadores das instâncias é realizada. As formulações são comparadas, junto com as diferentes formas de apresentar e resolver o problema. Ademais, um método de decomposição é usado para resolver um problema industrial real. A modelagem mostrase correta para a divisão da implementação de mudanças em linhas de montagem. Os resultados mostram que a divisão do esforço de implementação resulta em apenas poucas mudanças a mais (cerca de 7% para os casos pequenos e médios) comparadas com a implementação em uma fase. A possibilidade de programar a implementação em etapas menores aumenta a aplicabilidade de projetos, que, de outra forma, requeririam grande paradas de produção. / Operations Research investigates the (best) ways to configure and coordinate systems or operations with optimization procedures. Usually, the optimization of a system is modeled based on the aimed final configuration. However, little is published about how to reach or implement such optimal configurations in the systems. This master thesis proposes a new class of optimization problem: a scheduling of operations between initial and final states of a system, the Implementation Problem. The scheduling of operations is especially important to assembly lines. The automotive industry strongly relies on production lines that can operate 24 hours a day. Thus, the intervention opportunities to change or optimize the production system are very few. The implementation conditions of balancing on assembly lines are discussed, and the observed characteristics result in the proposal of the Assembly Line Implementation Problem (ALIP). The master thesis proposes a Mixed-Integer Linear Programming (MILP) modeling guide for the formulation of several variations of Implementation Problems. The modeling instructions are used to develop a set of MILP models for the Assembly Line Implementation Problem. For the results, a dataset is proposed and a sensitivity analysis on each of the consistent parameters of the dataset is performed. The proposed formulations are compared, along with the different forms of presenting and solving the problem. Furthermore, a decomposition method is used to solve a real-world industrial problem. The modeling correctly represents the division of the implementation of changes in assembly lines. The results show that the division of the effort in multiple stages only need a few more changes (around 7\% for the small and medium cases) comparing to a straightforward implementation. The possibility of scheduling the implementation in smaller steps increases the applicability of projects that otherwise would require a large system's stoppage time.

Fundação Araucária; CNPq; RENAULT; Seti / As linhas de montagem que envolvem soldagem por pontos estão amplamente presentes na indústria de fabricação automotiva. O processo de montagem da estrutura do veículo emprega vários robôs equipados com ferramentas de soldagem por pontos. Estes robôs e ferramentas possuem altos custos, fazendo surgir a necessidade de projetar a linha cuidadosamente, atendendo à demanda do produto e reduzindo as despesas ao mesmo tempo. Nesta dissertação, propõe-se e estuda-se o problema do Projeto de Linha de Montagem Robótica (PLMR), com base nas características práticas de uma empresa automotiva localizada no Brasil. Desenvolve-se um modelo de Programação Linear Inteira Mista (PLIM) que permite: (i) paralelização de estações, (ii) seleção de equipamentos e (iii) múltiplos robôs por estação de trabalho. O modelo matemático visa minimizar o custo total à uma taxa de produção desejada, o que envolve robôs, ferramentas e instalações. O modelo proposto considerou o tempo morto durante um ciclo, restrições de espaço, restrições de alocação de tarefas e possibilidades de paralelismo. O tempo morto é um tempo improdutivo e fixo do trabalho de manuseio de peças que acompanha o tempo de movimento dos robôs transportadores capacitados. Experimentos computacionais foram realizados para evidenciar a influência dos parâmetros sobre a solução ótima do projeto de linha. Além disso, foram realizados estudos de casos práticos com parâmetros reais coletados de uma linha de montagem robotizada para soldagem, localizada na região metropolitana de Curitiba-PR, chegando à otimalidade. Em comparação com as linhas estritamente seriais, o modelo mostrou grandes vantagens ao permitir paralelizar as estações no sistema de produção, permitindo avaliar uma compensação entre a taxa de produção e o custo total. / Spot welding assembly lines are widely present in the automotive manufacturing industry. The procedure of building the vehicle’s body employs several robots equipped with spot welding tools. These robots and tools are quite costly, arising the necessity of designing the line consciously, meeting the product demand and reducing expenses at the same time. In this master thesis, the Robotic Assembly Line Design (RALD) problem is proposed and studied based on practical characteristics from an automotive company located in Brazil. A Mixed-Integer Liner Programming (MILP) formulation is developed allowing: (i) station paralleling, (ii) equipment selection, and (iii) multiples robots per workstation. The mathematical model aims at minimising the total cost at the desired production rate, which involves robots, tools and facilities. The proposed model considered dead time during a cycle, space constraints, task assignment restrictions, and parallelism possibilities. Dead time is an unproductive and fixed work-piece handling time that accompany the capacitated transporter robots’ movement time. Computational experiments were performed in order to evidence the parameters’ influence over the optimal line design solution. In addition, practical case studies were conducted with parameters collected from a real-world robotic welding assembly line located on the outskirts of Curitiba-PR (Brazil), reaching optimality. Compared to the strictly serial lines, the model led to great advantages by allowing station paralleling in the production system, making it possible to evaluate an expected trade-off between the production rate and the total cost.

Made available in DSpace on 2014-12-17T14:56:18Z (GMT). No. of bitstreams: 1 DemetriusAMC_DISSERT.pdf: 2429364 bytes, checksum: 57aaf24560c189720b218dbca0ef1a56 (MD5) Previous issue date: 2014-01-24 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This work presents a scalable and efficient parallel implementation of the Standard Simplex algorithm in the multicore architecture to solve large scale linear programming problems. We present a general scheme explaining how each step of the standard Simplex algorithm was parallelized, indicating some important points of the parallel implementation. Performance analysis were conducted by comparing the sequential time using the Simplex tableau and the Simplex of the CPLEXR IBM. The experiments were executed on a shared memory machine with 24 cores. The scalability analysis was performed with problems of different dimensions, finding evidence that our parallel standard Simplex algorithm has a better parallel efficiency for problems with more variables than constraints. In comparison with CPLEXR , the proposed parallel algorithm achieved a efficiency of up to 16 times better / Este trabalho apresenta uma implementa??o paralela escal?vel e eficiente do algoritmo Simplex padr?o em arquitetura de processadores multicore para resolver problemas de programa??o linear de grande escala. Apresenta-se um esquema geral explicando como foi paralelizado cada passo do algoritmo simplex padr?o, apontando pontos importantes da implementa??o paralela. Foram realizadas an?lises de desempenho atrav?s da compara??o dos tempos sequenciais utilizando o Simplex tableau e Simplex do CPLEXR da IBM. Os experimentos foram realizados em uma m?quina de mem?ria compartilhada com 24 n?cleos. A an?lise de escalabilidade foi feita com problemas de diferentes dimens?es, encontrando evid?ncias de que a implementa??o paralela proposta do algoritmo simplex padr?o tem melhor efici?ncia paralela para problemas com mais vari?veis do que restri??es. Na compara??o com CPLEXR , o algoritmo proposto paralelo obteve uma efici?ncia de at? 16 vezes maior