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

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

Este trabalho trata de um problema de programação da produção em fundições de pequeno porte, que consiste em programar as ligas que devem ser produzidas em cada período do planejamento e como tais ligas devem ser usadas para a produção de itens sob encomenda, de modo que atrasos e custos operacionais sejam minimizados. Devido à certa incerteza nos dados do problema, a estratégia de horizonte rolante foi empregada. Este problema é representado por um modelo matemático de programação linear inteira mista. Neste trabalho foi desenvolvida uma heurística do tipo residual para obter uma boa solução inteira factível do problema, partindo da solução contínua encontrada pelos métodos relaxe-e-fixe e busca local / This work addresses a planning production problem that arises in small market-driven foundries, which consists of programming a number of alloys that have to be produced in each period of the planning horizon and how these alloys should be used to producing ordered items, in such way that delays and operational costs are minimized. Due to uncertainties in the problem data, the strategy of rolling horizon was used. This problem is modeled as a mixed integer linear programe. In this work we developed a residual typed heuristic in order to obtain a good feasible integer solution of the problem, which are built from the continuous solution found by relax-and-fix and local search methods. Keywords: Lot-sizing problems, mixed integer linear programming, production planning in foundries

L'incertitude a été toujours présente dans les problèmes d'optimisation. Dans ce travail, nous nous intéressons aux problèmes d'optimisation multi-niveaux où l'incertitude apparaît très naturellement. Les problèmes d'optimisation multi-niveaux avec incertitude ont suscité un intérêt à la fois théorique et pratique. L'optimisation robuste fait partie des méthodes les plus étudiées pour traiter ces problèmes. En optimisation robuste, nous cherchons une solution qui optimise la fonction objective pour le pire scénario appartenant à un ensemble d'incertitude donné. Les problèmes d'optimisation robuste multi-niveaux sont difficiles à résoudre, même de façon heuristique. Dans cette thèse, nous abordons les problèmes d'optimisation robuste à travers le prisme des méthodes de décomposition. Ces méthodes décomposent le problème en un problème maître (MP) et plusieurs problèmes satellites de séparation (AP). Dans ce contexte, les solutions et les relaxations heuristiques ont une importance particulière. Même pour les problèmes d'optimisation combinatoires, les relaxations sont importantes pour analyser l'écart de l'optimalité des solutions heuristiques. Un autre aspect important est l'utilisation des heuristiques comme integrés dans une méthode exacte. Les principales contributions de ce travail sont les suivantes. Premièrement, nous proposons une nouvelle relaxation pour les problèmes multi-niveaux basée sur l’approche dite d’information parfaite dans le domaine de l’optimisation stochastique. L'idée principale derrière cette méthode est d'éliminer les contraintes de non anticipativité du modèle pour obtenir un problème plus simple. Nous pouvons ensuite fournir des algorithmes combinatoires ad-hoc et des formulations de programmation mixte en nombres entiers compactes pour ce problème. Deuxièmement, nous proposons de nouveaux algorithmes de programmation dynamique pour résoudre les problèmes satellites apparaissant dans une classe spécifique de problèmes robustes pour un ensemble d'incertitude de type budget. Ce type d'incertitude est basé sur le nombre maximum d'écarts autorisés et leur taille. Ces algorithmes peuvent être appliqués à des problèmes de lot-sizing et à des problèmes de tournées de véhicules. Enfin, nous proposons un modèle robuste pour un problème lié à l’installation équitable de capteurs. Ce modèle fait le lien entre l'optimisation robuste et l'optimisation stochastique avec contraintes probabilistes ambigües. / Uncertainty has always been present in optimization problems, and it arises even more severely in multistage optimization problems. Multistage optimization problems underuncertainty have attracted interest from both the theoretical and the practical level.Robust optimization stands among the most established methodologies for dealing with such problems. In robust optimization, we look for a solution that optimizes the objective function for the worst possible scenario, in a given uncertainty set. Robust multi-stage optimization problems are hard to solve even heuristically. In this thesis, we address robust optimization problems through the lens of decompositions methods. These methods are based on the decomposition of the robust problem into a master problem (MP) and several adversarial separation problems (APs). The master problem contains the original robust constraints, however, written only for finite numbers of scenarios. Additional scenarios are generated on the y by solving the APs. In this context, heuristic solutions and relaxations have a particular importance. Similarly to combinatorial optimization problems, relaxations are important to analyze the optimality gap of heuristic solutions. Heuristic solutions represent a substantial gain from the computational viewpoint, especially when used to solve the separation problem. Because the adversarial problems must be solved several times, good heuristic solution may avoid the exact solution of the APs. The main contributions of this work are three-fold. First, we propose a new relaxation for multi-stage problems based on the approach named perfect information in the field of stochastic optimization. The main idea behind this method is to remove nonanticipativity constraints from the model to obtain a simpler problem for which we can provide ad-hoc combinatorial algorithms and compact mixed integer programming formulations. Second, we propose new dynamic programming algorithms to solve the APs for robust problems involving budgeted uncertainty, which are based on the maximum number of deviations allowed and on the size of the deviations. These algorithms can be applied to lot-sizing problems and vehicle routing problems among others. Finally, we study the robust equitable sensor location problem. We make the connection between the robust optimization and the stochastic programming with ambiguous probabilistic constraints. We propose linear models for several variants of the problem together withnumerical results.

Submitted by JACKELINE DEL CARMEN HUACCHA NEYRA null (jacky_157_93@hotmail.com) on 2017-03-24T15:38:11Z No. of bitstreams: 1 dissertação jackeline.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-03-24T18:02:08Z (GMT) No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) / Made available in DSpace on 2017-03-24T18:02:08Z (GMT). No. of bitstreams: 1 huacchaneyra_jc_me_sjrp.pdf: 1416143 bytes, checksum: 3865afc18803fe4e45d315a9ee3afaf9 (MD5) Previous issue date: 2017-03-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os problemas de dimensionamento de lotes consistem em determinar a quantidade de itens que devem ser produzidos em todos os períodos de um horizonte de planejamento. Em geral, são considerados custos de produção, preparação de máquina e de manutenção de estoque. Neste trabalho estuda-se uma extensão do problema de dimensionamento de lotes com restrição de capacidade que considera tempos de preparação, preparação carryover e crossover, em que se tem uma única máquina, único estágio, multi-itens e big-bucket (CLSP-SCC). Novas formulações para o CLSP-SCC são apresentadas e evitam a necessidade de definir novas variáveis binárias para modelar a preparação crossover. Também são propostas restrições de quebra de simetria para formulações propostas na literatura. São provadas as relações teóricas que existem entre cada uma destas formulações estudadas. Além disso, é proposta uma heurística híbrida que combina as heurísticas Relax-and-Fix e Fix-and-Optimize (RF-FO), em que a heurística Relax-and-Fix é usada para obter uma solução inicial e a heurística Fix-and-Optimize melhora essa solução. Por fim, apresentam-se os resultados computacionais e conclui-se que os resultados obtidos melhoram significativamente quando comparam-se a formulação clássica com as formulações sem preparação carryover. Compara-se também os resultados da heurística com os do pacote computacional CPLEX e, quando ambos são limitados ao mesmo tempo computacional, a heurística RF-FO obtém melhores resultados. / Lot-Sizing Problems consist of determining the quantity of items to be produced in each period of a planning horizon. In general, production, setup and inventory costs are considered. In this work an extension of the Capacitated Lot-Sizing Problem is studied, which considers setup times, Setup Carryover and Setup Crossover, single machine, single level, multi items, multi periods and big-bucket (CLSP-SCC). New formulations to the CLSP-SCC are presented and avoid the necessity of defining new extra binary variables to model the setup crossover. Furthermore, symmetry breaking constraints are proposed for formulations from the literature. The theoretical relations between the studied formulations are proved. A Relax-and-Fix and Fixand-Optimize (RF-FO) hybrid heuristic is proposed, in which the Relax-and-Fix helps to find an initial solution and the Fix-and-Optimize improves it. Computational results are presented and the obtained results improve significantly when comparing the classical formulation with the formulation without setup carryover. Finally, the results obtained by the RF-FO heuristic and the computational package CPLEX are compared and, when they both are limited to the same computational time, the RF-FO heuristic obtains better results.