We study simulation optimization methods for the stochastic economic lot scheduling problem. In contrast to prior research, we focus on methods that treat this problem as a black box. Based on a large-scale numerical study, we compare approximate dynamic programming with a global search for parameters of simple control policies. We propose two value function approximation schemes based on linear combinations of piecewise- constant functions as well as control policies that can be described by a small set of parameters. While approximate value iteration worked well for small problems with three products, it was clearly outperformed by the global policy search as soon as problem size increased. The most reliable choice in our study was a globally optimized fixed-cycle policy. An additional analysis of the response surface of model parameters on optimal average cost revealed that the cost effect of product diversity was negligible. (authors' abstract)

We consider the stochastic economic lot scheduling problem (SELSP) with lost sales and random demand, where switching between products is subject to sequence-dependent setup times. We propose a solution based on simulation optimization using an iterative two-step procedure which combines global policy search with local search heuristics for the traveling salesman sequencing subproblem. To optimize the production cycle, we compare two criteria: minimizing total setup times and evenly distributing setups to obtain a more regular production cycle. Based on a numerical study, we find that a policy with a balanced production cycle leads to lower cost than other policies with unbalanced cycles. (authors' abstract)

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-07-01Bitstream added on 2014-06-13T18:30:54Z : No. of bitstreams: 1 carretero_mm_me_sjrp.pdf: 795127 bytes, checksum: 64b07e80db6689945e91fc1c317deb3c (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Em alguns setores, o planejamento da produção envolve dois aspectos: o dimensionamento do tamanho dos lotes e a programação da produção (sequenciamento dos lotes). O primeiro problema consiste em determinar o tamanho dos lotes de produção de cada item a ser produzido em uma ou mais máquinas em cada período ao longo de um horizonte de planejamento finito. O segundo problema consiste em encontrar a ordem em que os lotes devem ser produzidos em um dado conjunto de máquinas. Estes dois aspectos do planejamento da produção podem ser tratados de forma independente: em um estágio é resolvido o problema de dimensionamento dos lotes e no outro, realizado antes ou depois, é resolvido o problema de seqüenciamento. No entanto, uma tendência recente na literatura são trabalhos que apresentam modelos matemáticos que capturam simultaneamente as relações entre os dois problemas. Na literatura pode-se encontrar modelos integrados que incluem restrições de eliminação de subrotas, propostas para o Problema do Caixeiro Viajante (PCV), para formular as restrições de sequenciamento. No entanto, alguns dos modelos propostos usam restrições de ordem polinomial que fornecem uma relaxação linear fraca. O objetivo desse trabalho é avaliar o uso de inequações válidas, propostas na literatura, para obtenção de formulações mais fortes para o problema integrado de dimensionamento e sequenciamento da produção. Resultados computacionais usando exemplares aleatórios e exemplares da literatura mostram que as reformulações propostas são eficientes para cenários em que o modelo original não é eficiente. / Often, the production planning involves the lot sizing and scheduling of items. The first problem is to determine the lot size of each item to be produced in one or more machines in each period over a finite planning horizon. The second problem is to find the order in which the items will be produced. These two aspects of the production planning can be treated independently: in one stage the lot sizing problem is solved, and in the other, that can be executed before or after, the scheduling problem is solved. A recent trend in the literature is to propose mathematical models that capture the relationships between these two problems. In the literature one can find integrated models that include subtour elimination constraints, proposed for the Traveling Salesman Problem, to formulate the scheduling decisions. However, in some of these models, constraints of polynomial order, that provides a weak linear relaxation, are used.The purpose of this study is to evaluate the use of valid inequalities proposed in the literature to obtain stronger formulations to the lot and scheduling problem. Computational results using random instances and instances from the literature show that the proposed formulations have a better performance in scenarios where the original model is not efficient.

Orientador: Silvio Alexandrede Araujo / Banca: Bernardo Sobrinho Simões de Almada Lobo / Banca: Franklina Maria Bragion Toledo / Resumo: O problema de dimensionamento de lotes é um problema de otimização da produção, em que o objetivo é planejar a quantidade de itens a ser produzida em várias, ou única, máquinas em cada período ao longo do horizonte de tempo, de modo a tender uma demanda e otimizar uma função objetivo. Este trabalho aborda o problema de dimensionamento de lotes em um único estágio em um ambiente com máquinas paralelas distintas. Cada item pode ser produzido em qualquer máquina, acarretando um tempo de preparação que é gasto antes de começar a produção. O objetivo do trabalho consiste em obter limitantes inferiores de boa qualidade para este problema. Para tanto, é desenvolvido um método de solução baseado numa reformulação do problema a e na relaxação lagrangiana de um conjunto de restrições. Alguns resultados computacionais são apresentados algumas propostas futuras para a continuidade do trabalho. / Abstract: The lot-sizing problem is a production optimization problem, where the objective is to plan the quantity of items to be produced in multiple, or single, machines in each period over a time horizon, in order to satisfy a demand and optimize an objective function. This work addresses the single stage parallel machine lot-sizing problem. Each item can be produced on any machine, and incur a setup time before to start the production. The objective of this work is to lower bounds of good quality for this problem. A solution method is developed based on a reformulation of the problem and the Lagrangian relaxation of a set of constrainsts. Some computational results are presented comparing the proposed method with a method from the literature, and, some future researches are proposed. / Mestre

Submitted by Melka Carolina Faria Catelan (melka_cfc@hotmail.com) on 2018-10-01T01:11:45Z No. of bitstreams: 1 Dissertação_última_versão.pdf: 797278 bytes, checksum: 7979645e9787343042f8c46ec0bc3884 (MD5) / Approved for entry into archive by Elza Mitiko Sato null (elzasato@ibilce.unesp.br) on 2018-10-02T16:34:19Z (GMT) No. of bitstreams: 1 catelan_mcf_me_sjrp.pdf: 838964 bytes, checksum: 686ef2d2d0419b1b9223004df8411dad (MD5) / Made available in DSpace on 2018-10-02T16:34:19Z (GMT). No. of bitstreams: 1 catelan_mcf_me_sjrp.pdf: 838964 bytes, checksum: 686ef2d2d0419b1b9223004df8411dad (MD5) Previous issue date: 2018-07-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho trata-se do problema de dimensionamento de lotes com máquinas paralelas flexíveis, que consiste basicamente em determinar a quantidade de itens a serem produzidos, em um horizonte de tempo finito, satisfazendo uma demanda, com várias máquinas. Este problema é de origem econômica e envolve custos de produção, estoque e preparação de máquinas. No problema padrão, cada item pode ser produzido em qualquer uma das máquinas, ou seja, têm-se a flexibilidade total de máquinas. No entanto nem sempre é viável ter flexibilidade total das máquinas, devido aos custos. Portanto, pode ser interessante implementar apenas uma flexibilidade limitada. A consideração ou não de uma máquina para produzir um produto específico torna-se uma variável de decisão e há um custo de investimento associado às estas decisões. Os resultados computacionais realizados com o CPLEX mostraram que a formulação é muito difícil, especialmente para instâncias com muitos itens. Assim, neste trabalho foram propostas três heurísticas para o problema, com intuito de buscar boas soluções para o problema em baixos tempos computacionais. As heurísticas foram comparadas ao modelo via pacote de otimização e observou que conforme o número de itens e de máquinas foram aumentando, os resultados obtidos foram melhores. / This work deals with the problem of lot-sizing with flexible parallel machines, which basicallyconsistsofdeterminingthequantityofitemstobeproduced, inafinitetime horizon, satisfying a demand, with several machines. This problem is of economic origin and involves production, inventory and machine preparation costs. In the standard problem, each item can be produced in any of the machines, that is, they have the total flexibility of machines. However, it is not always feasible to have total machine flexibility due to costs. Therefore, it may be interesting to implement only limited flexibility. The consideration or not of a machine to produce a specific product becomes a decision variable and there is an investment cost associated with these decisions. The computational results obtained with CPLEX showed that the formulation is very difficult, especially for instances with many items. Thus, in this work three heuristics were proposed for the problem, in order to find good solutions to the problem in low computational times. The heuristics were compared to the model via optimization package and observed that as the number of items and machines were increasing, the results were better. / CAPES: 3300415307

In this paper we proposed 0-1 integer programming formulation to model single batch processing machine. This problem deals with a set of jobs with non-identical sizes and processing times that has to be grouped to form batches according to the limited capacity of the machine. The processing time of a batch is the longest processing time of all jobs in the batch. The performance measure is the total time required to process all jobs (makespan). The formulation presented strengthens the model, i.e., it is closer to the optimal formulation than those proposed in the literature. Computational experiments demonstrate that the model is consistent and adequately represents the problem addressed. / Neste trabalho é proposta uma formulação de programação inteira 0-1 para modelar o problema de programação e dimensionamento de lotes de produção em máquina única. Este problema considera um conjunto de tarefas com diferentes tamanhos e tempos de processamento que devem ser agrupadas em lotes de acordo com a capacidade limitada da máquina. O tempo de processamento de um lote é determinado pelo maior tempo de processamento dentre todas as tarefas que compõem o lote. A medida de desempenho é o tempo total necessário para processar todas as tarefas (makespan). A formulação apresentada é mais forte, ou seja, mais próxima da formulação ideal do que aquelas propostas na literatura. Experimentos computacionais demonstram que o modelo é consistente e representa adequadamente o problema tratado.

abstract: In this thesis, a single-level, multi-item capacitated lot sizing problem with setup carryover, setup splitting and backlogging is investigated. This problem is typically used in the tactical and operational planning stage, determining the optimal production quantities and sequencing for all the products in the planning horizon. Although the capacitated lot sizing problems have been investigated with many different features from researchers, the simultaneous consideration of setup carryover and setup splitting is relatively new. This consideration is beneficial to reduce costs and produce feasible production schedule. Setup carryover allows the production setup to be continued between two adjacent periods without incurring extra setup costs and setup times. Setup splitting permits the setup to be partially finished in one period and continued in the next period, utilizing the capacity more efficiently and remove infeasibility of production schedule. The main approaches are that first the simple plant location formulation is adopted to reformulate the original model. Furthermore, an extended formulation by redefining the idle period constraints is developed to make the formulation tighter. Then for the purpose of evaluating the solution quality from heuristic, three types of valid inequalities are added to the model. A fix-and-optimize heuristic with two-stage product decomposition and period decomposition strategies is proposed to solve the formulation. This generic heuristic solves a small portion of binary variables and all the continuous variables rapidly in each subproblem. In addition, the case with demand backlogging is also incorporated to demonstrate that making additional assumptions to the basic formulation does not require to completely altering the heuristic. The contribution of this thesis includes several aspects: the computational results show the capability, flexibility and effectiveness of the approaches. The average optimality gap is 6% for data without backlogging and 8% for data with backlogging, respectively. In addition, when backlogging is not allowed, the performance of fix-and-optimize heuristic is stable regardless of period length. This gives advantage of using such approach to plan longer production schedule. Furthermore, the performance of the proposed solution approaches is analyzed so that later research on similar topics could compare the result with different solution strategies. / Dissertation/Thesis / Masters Thesis Industrial Engineering 2015

Submitted by WALTER RIBEIRO DA ROCHA JUNIOR null (walter.ribeiro82@gmail.com) on 2016-09-04T19:44:54Z No. of bitstreams: 1 ROCHA_JUNIOR, W.R..pdf: 2685376 bytes, checksum: b6d3e7345437be7187c981049cd5ccee (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-09-06T19:36:54Z (GMT) No. of bitstreams: 1 rochajunior_wr_me_bauru.pdf: 2685376 bytes, checksum: b6d3e7345437be7187c981049cd5ccee (MD5) / Made available in DSpace on 2016-09-06T19:36:55Z (GMT). No. of bitstreams: 1 rochajunior_wr_me_bauru.pdf: 2685376 bytes, checksum: b6d3e7345437be7187c981049cd5ccee (MD5) Previous issue date: 2016-07-06 / Problemas de dimensionamento de lotes são amplamente estudados na literatura e fazem parte de uma classe de problemas que envolvem decisões de planejamento da produção industrial. Basicamente, esses problemas consistem em definir uma estratégia para a utilização da capacidade de determinada estrutura fabril. As decisões envolvem quais produtos serão produzidos, em quais quantidades e em qual período, de forma a atender a demanda com a melhor rela- ção custo-benefício possível. Neste trabalho, propomos um modelo matemático para resolver o problema de programação de pedidos e dimensionamento de lotes de produção em indústrias de móveis seriados. O problema se caracteriza como multi itens, multiestágio e com demanda dinâmica determinística. O modelo matemático tem por objetivo minimizar os custos de produção no dimensionamento de lotes, considerando a capacidade finita do sistema produtivo. Testes foram realizados com dados fornecidos por uma empresa do setor moveleiro da cidade de Arapongas, Paraná. O modelo proposto foi implementado e resolvido utilizando um pacote de otimização. Resultados preliminares mostram-se significativamente melhores quando comparados com as programações utilizadas na prática da empresa, demonstrando a aderência de aplicações práticas de modelagem matemática em rotinas de planejamento de produção em empresas de fabricação de móveis seriados. / Lot sizing problems are widely studied in the literature and are part of a class of problems involving planning decisions of industrial production. Basically, these problems consist in defining a strategy for the capacity utilization of certain industrial structure. Decisions involve what products will be produced, in what quantities and at what period, in order to meet the demand with the best value for money possible. In this work, we propose a mathematical model for solving the problem of scheduling requests and dimensioning of production batches in series furniture industries. The problem is characterized as multi items, multistage and deterministic dynamic demand. The mathematical model is to minimize production costs in the lot sizing, considering the finite capacity of the production system. Tests were carried out with data provided by a company of the furniture sector in the city of Arapongas, Paraná. The proposed model was implemented and solved using an optimization package. Preliminary results show significantly better when compared to the settings used in the practice of the company, demonstrating adherence to mathematical modeling of practical applications in production planning routines in manufacturing series mobile companies.

Neste trabalho, abordamos métodos de resolução para o problema de dimensionamento de lotes que contempla o planejamento da produção de vários produtos em múltiplas máquinas. A fabricação dos produtos consome tempo de produção e preparação de uma capacidade de produção limitada. A demanda pelos produtos é conhecida e pode ser atendida com atraso durante um horizonte de planejamento finito. O objetivo é minimizar a soma dos custos de produção, preparação para a produção, estoque dos produtos e atraso na entrega destes. Em uma primeira etapa, desenvolvemos uma busca tabu determinística baseada em outra, aleatória, que foi apresentada na literatura. Com isso, realizamos uma análise sobre a influência de fatores aleatórios sobre heurísticas do tipo busca tabu quando aplicadas ao problema estudado. Posteriormente, desenvolvemos um método híbrido baseado em busca tabu, branch-and-cut e programação linear para a resolução do problema. Nos testes computacionais realizados, o método proposto mostrou-se competitivo quando comparado a outras heurísticas apresentadas na literatura / This paper proposes two methods to solve the capacitated lot-sizing problem with multiple products and parallel machines. The manufacturing of products consumes machines capacity (production time and setup time), which is scarce. The demand for the products is known and can be met with backlogging. The objective is to minimize the sum of production, setup, holding and backlog costs. In a first step, we developed a deterministic tabu search heuristic based on a random version from the literature and then conducted an analysis of the influence of random factors on tabu search heuristics when applied to solve the studied problem. Subsequently, we designed a hybrid method based on tabu search, branch-andcut and linear programming. Computational experiments show that this hybrid method is competitive with other heuristics presented in the literature

Neste trabalho foi estudado um problema de dimensionamento de lotes em uma indústria química brasileira, cujo objetivo era determinar o tamanho dos lotes dos produtos para atender às demandas, minimizando os custos produtivos. Os itens podem ser produzidos em máquinas paralelas distintas, através de diferentes processos, e devem ser armazenados em taques cativos, exclusivos a um produto, ou multipropósitos, compartilhado entre produtos, desde que não simultaneamente. Foram propostos dois modelos matemáticos de programação inteira mista para representar o problema, o primeiro apresentava uma função objetivo compreendendo o preço das matérias-primas consumidas nas reações, os gastos com a estocagem de produtos e o custo de descarte de produtos quando os tanques de armazenamento não tiverem capacidade suficiente para armazená-los, já o segundo estendendo este modelo para considerar custos de preparação de máquina. Experimentos computacionais com os modelos propostos, utilizando instâncias geradas a partir dos dados fornecidos pela empresa, mostraram que o software de otimização empregado foi capaz de resolver poucas instâncias, após uma hora de processamento. Portanto, foram propostas heurísticas construtivas do tipo LP-and-fix e relax-and-fix, além de heurísticas de melhoria do tipo fix-and-optimize. Após serem realizados testes com essas heurísticas, constatou-se que algumas proporcionaram a obtenção de soluções factíveis de boa qualidade, quando comparadas às obtidas pelo software, sendo ainda capazes de resolver um maior número de instâncias / In this dissertation the lot sizing problem in a chemical Brazilian industry was studied, with the goal to determine the products lot size to satisfy the demands, minimizing the production costs. The items can be produced on distinct parallel machines through different processes and then must be stored in exclusive tanks, used by only one product, or multipurpose tanks, when more than one product can use the tank, but not simultaneously. Two models were proposed to represent the problem, the first one aiming to minimize the price of raw material consumed in the reactions, storage product spending and the cost of discarting products when the storage tanks do not have enough capacity to store them, and the second one considering setup cost either. Computational experiments using the proposed models, with instances were generated from the data provided by the company, showed that the used optimization software was able to solve only few instances after processing for one hour. In this dissertation we propose constructives heuristics such LP-and-fix and relax-and-fix, and improving heuristics like fix-and-optimize. After performing the tests with those heuristics, it was found that some of them provided feasible solutions with good quality, when compared to the ones obtained by the software, and they were also able to solve a larger number of instances