Simultaneous lot-sizing and scheduling problem is the problem to decide what products to be produced on which machine and in which order, as well as the quantity of each product. Problems of this type are hard to solve. Therefore, they were studied for years, and a considerable number of papers is published to solve different lotsizing and scheduling problems, specifically real-case problems. This work proposes a Real-Coded Genetic Algorithm (RCGA) with a new chromosome representation to solve a non-identical parallel machine capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs, machine cost and backlogging. Such a problem can be found in real world production line at furniture manufacturer in Sweden. Backlogging is an important concept in this problem, and it is often ignored in the literature. This study implements three different types of crossover; one of them has been chosen based on numerical experiments. Four mutation operators have been combined together to allow the genetic algorithm to scan the search area and maintain genetic diversity. Other steps like initializing of the population and a reinitializing process have been designed carefully to achieve the best performance and to prevent the algorithm from trapped into the local optimum. The proposed algorithm is implemented and coded in MATLAB and tested for a set of standard medium to large-size problems taken from the literature. A variety of problems were solved to measure the impact of different characteristics of problems such as the number of periods, machines, and products on the quality of the solution provided by the proposed RCGA. To evaluate the performance of the proposed algorithm, the average deviation from the lower bound and runtime for the proposed RCGA are compared with three other algorithms from the literature. The results show that, in addition to its high computational speed, the proposed RCGA outperforms the other algorithms for non-identical parallel machine problems, while it is outperformed by the other algorithms for problems with the more identical parallel machine. The results show that the different characteristics of problem instances, like increasing setup cost, and size of the problem influence the quality of the solutions provided by the proposed RCGA negatively.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Esta tese aborda um problema de dimensionamento e sequenciamento de lotes de produção baseado em uma indústria alimentícia brasileira que opera por meio de diversas linhas de produção heterogêneas. Nesse ambiente produtivo, as linhas de produção compartilham recursos escassos, tais como, trabalhadores e máquinas e devem ser montadas (ativadas) em cada período produtivo, respeitando-se a capacidade disponível de cada recurso necessário para ativação das mesmas. Modelos de programação matemática inteira mista são propostos para representação do problema, bem como diversos métodos heurísticos de solução, compreendendo procedimentos construtivos e de melhoramento baseados na formulação matemática do problema e heurísticas lagrangianas. São propostas heurísticas do tipo relax-and-fix explorando diversas partições das variáveis binárias dos modelos e uma heurística baseada na decomposição do modelo para construção de soluções. Procedimentos do tipo fix-and-optimize e matheuristics do tipo iterative MIP-based neighbourhood search são propostas para o melhoramento das soluções iniciais obtidas pelos procedimentos construtivos. Testes computacionais são realizados com instâncias geradas aleatoriamente e mostram que os métodos propostos são capazes de oferecer melhores soluções do que o algoritmo Branch-and-Cut de um resolvedor comercial para instâncias de médio e grande porte. / This doctoral dissertation addresses the simultaneous lot sizing and scheduling problem in a real world production environment where production lines share scarce production resources. Due to the lack of resources, the production lines cannot operate all simultaneously and they need to be assembled in each period respecting the capacity constraints of the resources. This dissertation presents mixed integer programming models to deal with the problem as well as various heuristic approaches: constructive and improvement procedures based on the mathematical formulation of the problem and lagrangian heuristics. Relax-and-fix heuristics exploring some partitions of the set of binary variables of a model and a decomposition based heuristic are proposed to construct solutions. Fix-and-optimize heuristics and iterative MIP-based neighbourhood search matheuristics are proposed to improvement solutions obtained by constructive procedures. Computational tests are performed with randomly instances and show that the proposed methods can find better solutions than the Branch-and-Cut algorithm of a commercial solver for medium and large size instances.

Este trabalho aborda o problema multiestágio de planejamento e programação da produção em indústrias cervejeiras. O processo de fabricação de cerveja pode ser dividido em duas etapas principais: preparação do líquido e envase. A primeira etapa ocorre, na maior parte do tempo, dentro de tanques de fermentação e maturação. A segunda ocorre nas linhas de envase, podendo ter início assim que o líquido estiver pronto nos tanques. O tempo de preparação do líquido demora vários dias, enquanto que na maioria das indústrias de bebidas carbonatadas este tempo é de no máximo algumas horas. O objetivo deste estudo é obter planos de produção viáveis que visam otimizar as decisões de programação envolvidas nestes processos. Visitas a cervejarias no Brasil e em Portugal foram realizadas para uma maior familiaridade do processo de produção e dados foram coletados. Modelos de programação inteira mista para representar o problema foram desenvolvidos, baseados em abordagens CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) e ATSP (Asymmetric Travelling Salesman Problem). Os resultados mostram que os modelos são coerentes e representam adequadamente o problema, entretanto, mostram-se difíceis de serem resolvidos na otimalidade. Esta dificuldade de resolução dos modelos motivou o desenvolvimento de procedimentos MIP-heurísticos, como também de uma metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). As soluções obtidas pelos procedimentos heurísticos são de boa qualidade, quando comparadas ao melhor limitante inferior encontrado por meio da resolução dos modelos matemáticos. Os testes computacionais foram realizados utilizando instâncias geradas com base em dados reais. / This study deals with the multistage lot-sizing and scheduling problem in breweries. The brewing process can be divided into two main stages: preparation and filling of the liquid. The first stage occurs most of the time in fermentation and maturation tanks. The second stage occurs in the filling lines and it can start as soon as the liquid gets ready. The preparation time of the liquid takes several days, while in the carbonated beverage industries this time is at most a few hours. The purpose of this study is to obtain feasible production plans aimed at optimizing the decisions involved in these processes. Visits to brewery industries in Brazil and Portugal were held to a greater familiarity of the production process and data were collected. Mixed integer programming models have been developed to represent the problem, based on approaches for the CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) and ATSP (Asymmetric Travelling Salesman Problem). The results show that the models are consistent and adequately represent the problem; however, they are difficult to be solved at optimality. This motivated the development of MIP-heuristic procedures, as well as a meta-heuristic GRASP (Greedy Randomized Adaptive Search Procedure). The obtained solutions by the heuristics are of good quality, when compared to the best lower bound found by solving the mathematical models. The tests were conducted using generated instances based on real data.

Made available in DSpace on 2016-06-02T19:50:25Z (GMT). No. of bitstreams: 1 6346.pdf: 5901404 bytes, checksum: 2d78b0f5f68ac25a089acd315f55b157 (MD5) Previous issue date: 2014-06-09 / The production of sugar, ethanol and electricity from sugar cane necessarily involves harvesting and transportation of raw materials, which are expensive and complex operations and have significant influence on the quality of the industrial raw material. The literature reports several optimization approaches related to the planning of planting, harvesting and transporting of sugarcane, however the scheduling of harvesting fronts is underexplored. This thesis intends to contribute to the state-of-art of this important issue in the context of the Brazilian agribusiness. Optimization approaches to support scheduling decisions of harvesting fronts considering the balance of harvesting and transportation capacities, as well as good agronomic management are proposed. The approaches are inspired by the representation of the problem as a lot sizing and scheduling model with parallel machines and sequence-dependent setup costs and times, a modelling technique well studied in the production planning and control literature. Three variants of this formulation, based on mathematical programming models, were developed and tested in two real case studies of medium size sugar mills. Heuristic methods based on aggregation procedures and mathematical programming have also been studied and developed to solve large scaled problems found in practice. Among the three variants studied, one presented the best solution quality within the expected execution time. Important scenario analysis were done indicating that the schedule s fulfilment provides reduction of harvesting and transporting complexity to the following season, which can generate significant saves in the cases studied. Besides that, comparing the proposed scheduling method with one of the sector s practice, it can be generated also significant cost reduction in the cases studied. The results were analyzed according to a validation methodology (descriptive facet of tetraedrum) well known in the literature. / A produção de açúcar, álcool e energia elétrica a partir de cana-de-açúcar passa necessariamente pela colheita e transporte da matéria-prima, que são operações custosas, complexas e que interferem significativamente na qualidade da matéria-prima industrial. A literatura reporta várias abordagens de otimização relacionadas ao planejamento do plantio, da colheita e do transporte de cana-de-açúcar, todavia a programação das frentes de colheita é pouco explorada. Nesta tese pretende-se contribuir para o estado da arte deste importante tema no contexto do agronegócio brasileiro. Propõe-se abordagens de otimização para apoiar decisões de programação das frentes de colheita, considerando-se o equilíbrio das capacidades de colheita e transporte, bem como um bom manejo agronômico. As abordagens são inspiradas na representação do problema por meio de um modelo de dimensionamento de lotes e sequenciamento da produção em máquinas paralelas com custos e tempos de setup dependentes da sequência, bem estudado na literatura em contextos de planejamento e controle da produção. Para isso foram desenvolvidas três variantes desta formulação baseadas em programação matemática, voltadas para a programação das frentes de colheita, que foram testadas em dois estudos de caso reais de usinas de cana-de-açúcar de médio porte do setor. Métodos heurísticos baseados em procedimentos de agregação e programação matemática também foram estudados e desenvolvidos para a resolução dos problemas de grande porte encontrados na prática. Das três variantes estudadas, uma delas apresentou melhor qualidade da solução dentro de tempos computacionais aceitáveis para o problema. Análises de cenário importantes foram feitas indicando que o cumprimento da programação proporciona redução de complexidade da colheita e transporte na safra seguinte, podendo gerar economias significativas nos casos estudados. Além disso, a comparação dos resultados das abordagens aqui exploradas com o que é praticado no setor indica um potencial de redução de custos também significativo para os casos estudados. Os resultados foram analisados de acordo com uma metodologia de validação (faceta descritiva do tetraedro) conhecida na literatura.

Made available in DSpace on 2016-06-02T19:53:32Z (GMT). No. of bitstreams: 1 PEREZ_MARTINEZ_Karim_2013.pdf: 1435441 bytes, checksum: dc4551ff55ece881790f51193596d2bd (MD5) Previous issue date: 2013-09-27 / Financiadora de Estudos e Projetos / This research deals with the production planning and scheduling problem in the molded pulp packing industry, studying particularly a plant of molded pulp packages for eggs. The production process can be subdivided into two processes: molding process and printing process. The main challenge for production planning activities is on the molding process, where products are produced through tooling that have several molds. These tooling are called "Molding Patterns" or " Conformation Patterns". Each one of the molding patterns can contain one, two, until three kind of molds, allowing to produce several products simultaneously. Producing several products at the time can generate large inventory for low demand products and also null inventory for high demand products. Thus, different inventory levels are defined for each product based on their demand behavior, in order to control inventory quantities. In this way, decisions related to the production planning and scheduling in this production process involve deciding which molding patterns should used, how much time they should be used, and how they should be sequenced. All these should be make taking into account a parallel machine system and sequenced-dependent setups time and costs, in order to minimize inventory and setups costs, as well as penalties associated to inventory out of the specified inventory levels of each product. To represent this problem we proposed two formulations: the first one based on the Capacitated Lot Sizing and Scheduling Problem (CLSP), and the second one based on the General Lot Sizing and Scheduling Problem (GLSP). The results from the models were compared in a set of real word instances of a plant, in order to check the adequacy to represent the decisions involved in the studied production process, as well as the main differences between their production plans and performance of the models. The proposed formulations were also adapted for a particular instance, in order to compare their productions plans against the production plan implement by the studied plant. Results show that the proposed models represent rightly decisions involved in the production planning and scheduling in the molded pulp. Furthermore, the solutions obtained by the proposed models represent production plans with costs significantly lower than the schedule implemented by a real plant in this kind of industry. / Este trabalho aborda o problema de planejamento e programação da produção na indústria de embalagens em polpa moldada, considerando particularmente uma fábrica de embalagens para acondicionamento de ovos. O processo de produção pode ser subdividido em dois processos: processo de moldagem e processo de estampagem. O principal desafio para as atividades de planejamento encontra-se no processo de moldagem, em que a obtenção dos produtos depende da utilização de diferentes ferramentais, formados por um conjunto de moldes. Estes ferramentais são chamados de padrões de conformação ou padrões de moldagem , e podem conter um, dois ou até três tipos de moldes, permitindo a produção simultânea de produtos diferentes. Esta produção simultânea de itens pode gerar grandes níveis de estoque de produtos de baixa demanda e estoques nulos para produtos de alta demanda, desta forma, são definidos diferentes níveis de estoque para cada produto com base no comportamento da sua demanda. As decisões envolvidas no planejamento e programação da produção neste tipo de processo envolve a escolha dos padrões de moldagem a serem utilizados, o tempo de produção de cada padrão, e a sequência em que estes devem ser programados, considerando um sistema de linhas paralelas idênticas e tempos e custos de preparação dependentes da sequência. Estas decisões devem ser definidas de modo a minimizar os custos de estocagem, preparação, e penalidades associadas ao desvio do volume do estoque em relação aos níveis estabelecidos para cada produto. Para representar o problema são propostas dois tipos de formulações: a primeira baseada no Problema de Dimensionamento de Lotes Capacitado (CLSP), e a segunda baseada no Problema de Dimensionamento e Sequenciamento de Lotes Geral (GLSP). Os resultados da resolução dos modelos são comparados com base em exemplares reais da fábrica em estudo, a fim de verificar sua adequação para representar as decisões envolvidas no sistema de produção, as principais diferenças nos planos de produção gerados, e o desempenho destes modelos. Os resultados obtidos demonstram que os modelos propostos representam adequadamente as decisões no sistema de produção estudado, e geram planos de produção significativamente melhores que os planos praticados pela fábrica.

Este trabalho aborda o problema multiestágio de planejamento e programação da produção em indústrias cervejeiras. O processo de fabricação de cerveja pode ser dividido em duas etapas principais: preparação do líquido e envase. A primeira etapa ocorre, na maior parte do tempo, dentro de tanques de fermentação e maturação. A segunda ocorre nas linhas de envase, podendo ter início assim que o líquido estiver pronto nos tanques. O tempo de preparação do líquido demora vários dias, enquanto que na maioria das indústrias de bebidas carbonatadas este tempo é de no máximo algumas horas. O objetivo deste estudo é obter planos de produção viáveis que visam otimizar as decisões de programação envolvidas nestes processos. Visitas a cervejarias no Brasil e em Portugal foram realizadas para uma maior familiaridade do processo de produção e dados foram coletados. Modelos de programação inteira mista para representar o problema foram desenvolvidos, baseados em abordagens CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) e ATSP (Asymmetric Travelling Salesman Problem). Os resultados mostram que os modelos são coerentes e representam adequadamente o problema, entretanto, mostram-se difíceis de serem resolvidos na otimalidade. Esta dificuldade de resolução dos modelos motivou o desenvolvimento de procedimentos MIP-heurísticos, como também de uma metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). As soluções obtidas pelos procedimentos heurísticos são de boa qualidade, quando comparadas ao melhor limitante inferior encontrado por meio da resolução dos modelos matemáticos. Os testes computacionais foram realizados utilizando instâncias geradas com base em dados reais. / This study deals with the multistage lot-sizing and scheduling problem in breweries. The brewing process can be divided into two main stages: preparation and filling of the liquid. The first stage occurs most of the time in fermentation and maturation tanks. The second stage occurs in the filling lines and it can start as soon as the liquid gets ready. The preparation time of the liquid takes several days, while in the carbonated beverage industries this time is at most a few hours. The purpose of this study is to obtain feasible production plans aimed at optimizing the decisions involved in these processes. Visits to brewery industries in Brazil and Portugal were held to a greater familiarity of the production process and data were collected. Mixed integer programming models have been developed to represent the problem, based on approaches for the CSLP (The Continuous Setup Lot-Sizing Problem), GLSP (General Lot Sizing and Scheduling Problem), SPL (Simple Plant Location Problem) and ATSP (Asymmetric Travelling Salesman Problem). The results show that the models are consistent and adequately represent the problem; however, they are difficult to be solved at optimality. This motivated the development of MIP-heuristic procedures, as well as a meta-heuristic GRASP (Greedy Randomized Adaptive Search Procedure). The obtained solutions by the heuristics are of good quality, when compared to the best lower bound found by solving the mathematical models. The tests were conducted using generated instances based on real data.