Doctor en Sistemas de Ingeniería / En este trabajo se estudia la calidad que ofrecen las soluciones óptimas locales para problemas de programación de tareas en máquinas en paralelo. Los ambientes considerados son máquinas idénticas, idénticas restringidas, uniformes restringidas y no-relacionadas. El objetivo considerado es la minimización del tiempo ponderado de completación. Para estudiar la calidad de los óptimos locales se determinan los factores de aproximación para las soluciones localmente óptimas de los vecindarios de inserción (jump) e intercambio (swap). Los resultados indican que para los ambientes de máquinas paralelas uniformes y no-relacionadas, el costo de cualquier óptimo local se encuentra alejado a lo más en un factor 2,618 con respecto al costo del óptimo. Si solo se considera la minimización del tiempo de completación, se tiene que el factor es 2. El mismo resultado se obtuvo para el ambiente de máquinas uniformes con tareas unitarias, para los casos ponderado y no ponderado. Por otra parte, para el problema de máquinas paralelas idénticas restringidas, se determinó que el factor de aproximación se encuentra entre 1,75 y 1,809. Para el caso no ponderado este factor se encuentra entre 1,5333 y 1,618. Para el caso de tareas unitarias, donde el objetivo es la minimización del tiempo ponderado de completación, se determinó que el factor de aproximación se encuentra entre 1,5333 y 1,618. Mientras que para el caso no ponderado se tienen evidencias que indican que el factor de aproximación es 1,5333. / Este trabajo ha sido parcialmente financiado por Universidad del Bío-Bío; Conicyt, Programa de Formación de Capital Humano Avanzado; Núcleo Milenio Información y Coordinación en Redes

Nessa dissertação apresentamos um problema de programação da produção, motivado por uma indústria alimentícia caracterizada pela perecibilidade dos produtos, sequenciamento da produção dos lotes e pela necessidade de sincronização de recursos escassos para operação das linhas de produção. Em indústrias desse ramo, existem altos custos associados a estocagem dos produtos, a fim de evitar sua perda, de modo que é essencial a boa gestão dos processos industriais e do estoque. Modelos matemáticos de programação inteira mista foram desenvolvidos para tratar o problema, bem como o estudo da inclusão de diversas restrições da literatura para o tratamento da perecibilidade. Testes computacionais foram realizados para as validações dos modelos matemáticos, entretanto, devido à dificuldade de determinar soluções de boa qualidade pelo solver de otimização, foram propostos métodos heurísticos baseados na formulação matemática. Com o objetivo de mostrar o desempenho das heurísticas, comparamos as suas performances na resolução de instâncias da literatura e exemplares baseados no cenário produtivo da indústria com os resultados do solver. / In this dissertation we present a lot sizing and scheduling problem motivated by a food industry characterized by the perishability of the products, sequencing the production of the lots and by the need of synchronization of scarce resources for the operation of the production lines. In this type of industry, there are high costs associated with stocking the products in order to avoid their loss, so that good management of industrial processes and inventory is essential. Mathematical models of mixed integer programming were developed to treat the problem, as well as the study of the inclusion of several restrictions of the literature for the treatment of perishability. Computational tests were performed for the validations of the mathematical models, however, due to the difficulty of determining solutions of good quality by the optimization solver, heuristic methods based on the mathematical formulation were proposed. In order to show the performance of the heuristics, we compare their performances in solving instances of the literature and exemplars based on the productive scenario of the industry with the results of solver.

O problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês Assembly Line Worker Assignment and Balancing Problem ) é uma extensão do problema simples de balanceamento de linhas na qual os tempos de execução de tarefas são dependentes dos trabalhadores. Este problema tem sua motivação prática oriunda de linhas de produção com trabalhadores deficientes. Neste trabalho, focamos em uma extensão para o problema que permite lidar com a possibilidade de layouts de linhas com estações em paralelo. Além disso, estudamos uma segunda variante do problema que permite que os trabalhadores colaborem uns com os outros em uma mesma estação. Apresentamos formulações matemáticas para ambas as versões do problema. Adicionalmente, a partir de adaptações de métodos existentes para o ALWABP serial, desenvolvemos heurísticas construtivas para o ALWABP paralelo e ALWABP colaborativo. Testes computacionais em instâncias da literatura e uma análise detalhada dos resultados são apresentados / The assembly line and worker assignment balancing problem is an extension of the classical simple assembly line balancing problem where task execution times are workerdependent. This problem is motivated by the situation faced when balancing assembly lines with disabled workers. In this study, we focus on an extension for the problem with the goal of including the possibility of having layouts with parallel workstations. We also study a second variation for this problem that allows workers collaborating with each other. We present mathematical formulations for both problems. Moreover, constructive heuristics are developed, based on heuristic methods for the serial assembly line worker assignment and balancing problem. Computational tests on literature instances and a detailed analysis of the results are reported

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T18:59:59Z No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-07T19:00:25Z (GMT) No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-02-07T19:00:25Z (GMT). No. of bitstreams: 2 Tese_Rainer X. Amorim.pdf: 6271497 bytes, checksum: 42feec49cd385dde2a106aee5c11c269 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-10-06 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / This research investigates scheduling problems with earliness and tardiness penalties on single and parallel machine environments. This problem is also known in the literature as Just-in-Time scheduling, system widely used in industries to reduce inventories and costs, in order to lead product to be produced according to demand. In this work we present a hybrid exact-heuristic algorithmic strategy, based on an arc-time indexed integer programming formulation and a generalized evolutionary heuristic based on a strong local search, to better solve classical parallel machine scheduling problems involving weighted earliness-tardiness penalties, with independent jobs and arbitrary processing times. Selected arcs from local optima solutions generated by a genetic algorithm based on a strong local search (GLS) with generalized pairwise interchanges are given as input to the arc-time formulation, to produce better solutions than those obtained by both methods when used isolated. Computational experiments present competitive results according to the literature. Our proposed method also solves large instances up to 500 jobs in identical parallel machines. / Esta pesquisa investiga problemas de escalonamento com penalidades de antecipação e atraso em ambiente mono e multiprocessado envolvendo máquinas paralelas. Este problema é também conhecido na literatura como escalonamento Just-in-Time, sistema amplamente utilizado em indústrias para reduzir estoques e os custos decorrentes, a fim de que o produto seja produzido de acordo com a demanda. Neste trabalho é proposta uma estratégia algorítmica híbrida exato-heurística, baseada em uma formulação de programação inteira arc-time e um algoritmo evolucionário fortemente baseado em busca local, para melhor resolver problemas clássicos de escalonamento em máquinas paralelas envolvendo penalidades de antecipação e atraso, com tarefas independentes e tempos de processamento arbitrários. Os arcos são selecionados das soluções ótimas locais obtidas pelo algoritmo genético fortemente baseado em busca local (GLS) com movimentos generalizados de troca de pares, que são fornecidos como entrada para a formulação arc-time, para gerar soluções melhores do que as obtidas por ambos os métodos quando utilizados isoladamente. Os experimentos computacionais apresentam resultados competitivos em relação à literatura. O método proposto também resolve instâncias de tamanho maior de até 500 tarefas em máquinas paralelas idênticas.

The main objective of this work is to propose optimization methods of the production to a medium size market foundry industry. Taking into consideration the peculiarities of the enterprise used as case study, on the contrary of many other works in this area, the present research is focused in the production programming which is based in the macharia ( it is a mold made of sand which serves to give shape to the final piece) and molding machines programming. The kilns programming do not represent a delay in the productive process which has been studied, however, their capacity is taken into consideration during the production of the optimization methods. The proposed model considers the programming of tasks in parallel machines with families set up dependent of the sequence. In order to solve the problem it is used a meta-heurística GRASP. The computing results show that it is significantly possible to improve the procedure of the production programming nowadays used in the foundry industry case study. / O presente trabalho tem por objetivo propor métodos de otimização da produção para uma fundição de mercado de médio porte. Dada as peculiaridades da empresa utilizada como estudo de caso, diferentemente de outros trabalhos nesta área, a presente pesquisa enfoca a programação da produção baseada na programação das máquinas da macharia e da moldagem. A programação dos fornos não representa gargalo no processo produtivo em estudo, no entanto, a capacidade dos mesmos é levada em conta no momento da confecção dos métodos de otimização. O modelo proposto considera a programação de tarefas em máquinas paralelas com famílias de setup dependente da seqüência. Para resolver o problema assim definido é utilizada uma meta-heurística GRASP. Os resultados computacionais demonstram que é possível melhorar significativamente o procedimento de programação da produção utilizado atualmente na fundição estudo de caso.

No description available.

O problema de balanceamento de linhas de produção e designação de trabalhadores (ALWABP, do inglês Assembly Line Worker Assignment and Balancing Problem ) é uma extensão do problema simples de balanceamento de linhas na qual os tempos de execução de tarefas são dependentes dos trabalhadores. Este problema tem sua motivação prática oriunda de linhas de produção com trabalhadores deficientes. Neste trabalho, focamos em uma extensão para o problema que permite lidar com a possibilidade de layouts de linhas com estações em paralelo. Além disso, estudamos uma segunda variante do problema que permite que os trabalhadores colaborem uns com os outros em uma mesma estação. Apresentamos formulações matemáticas para ambas as versões do problema. Adicionalmente, a partir de adaptações de métodos existentes para o ALWABP serial, desenvolvemos heurísticas construtivas para o ALWABP paralelo e ALWABP colaborativo. Testes computacionais em instâncias da literatura e uma análise detalhada dos resultados são apresentados / The assembly line and worker assignment balancing problem is an extension of the classical simple assembly line balancing problem where task execution times are workerdependent. This problem is motivated by the situation faced when balancing assembly lines with disabled workers. In this study, we focus on an extension for the problem with the goal of including the possibility of having layouts with parallel workstations. We also study a second variation for this problem that allows workers collaborating with each other. We present mathematical formulations for both problems. Moreover, constructive heuristics are developed, based on heuristic methods for the serial assembly line worker assignment and balancing problem. Computational tests on literature instances and a detailed analysis of the results are reported

Nessa dissertação apresentamos um problema de programação da produção, motivado por uma indústria alimentícia caracterizada pela perecibilidade dos produtos, sequenciamento da produção dos lotes e pela necessidade de sincronização de recursos escassos para operação das linhas de produção. Em indústrias desse ramo, existem altos custos associados a estocagem dos produtos, a fim de evitar sua perda, de modo que é essencial a boa gestão dos processos industriais e do estoque. Modelos matemáticos de programação inteira mista foram desenvolvidos para tratar o problema, bem como o estudo da inclusão de diversas restrições da literatura para o tratamento da perecibilidade. Testes computacionais foram realizados para as validações dos modelos matemáticos, entretanto, devido à dificuldade de determinar soluções de boa qualidade pelo solver de otimização, foram propostos métodos heurísticos baseados na formulação matemática. Com o objetivo de mostrar o desempenho das heurísticas, comparamos as suas performances na resolução de instâncias da literatura e exemplares baseados no cenário produtivo da indústria com os resultados do solver. / In this dissertation we present a lot sizing and scheduling problem motivated by a food industry characterized by the perishability of the products, sequencing the production of the lots and by the need of synchronization of scarce resources for the operation of the production lines. In this type of industry, there are high costs associated with stocking the products in order to avoid their loss, so that good management of industrial processes and inventory is essential. Mathematical models of mixed integer programming were developed to treat the problem, as well as the study of the inclusion of several restrictions of the literature for the treatment of perishability. Computational tests were performed for the validations of the mathematical models, however, due to the difficulty of determining solutions of good quality by the optimization solver, heuristic methods based on the mathematical formulation were proposed. In order to show the performance of the heuristics, we compare their performances in solving instances of the literature and exemplars based on the productive scenario of the industry with the results of solver.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents three evolutionary strategies to solve the problem of scheduling a given set of n jobs to m identical parallel machines with the objective of minimizing makespan. There is a sequence dependent setup times. We also compares our method with two other well succeeded heuristics, one is a tabu search based heuristic and the second is a memetic approach, which combines a population-based method with local search procedures. As benchmarks for smallsized instances, optimal values are used provide by a dichotomous search. For larger instances, the comparisons try to show the robust behavior in solution quality as well as in computational effort of our evolutionary strategy. / Este trabalho propõe três estratégias evolutivas para resolver o problema de seqüenciamento de n tarefas em m máquinas paralelas idênticas, buscando minimizar o tempo máximo de finalização (makespan). São considerados tempos de preparação dependentes da seqüência. Os métodos propostos são comparados com outras duas heurísticas de qualidade comprovada, uma baseada em Busca Tabu e outra baseada em Algoritmos Meméticos. Para algumas instâncias de pequeno porte, comparações são feitas com o valor ótimo obtido através de uma busca dicotômica. Para instâncias maiores, as comparações demonstram a robustez e a boa qualidade das soluções encontradas pelas estratégias evolutivas através da comparação com as outras heurísticas.

O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive