O presente trabalho trata do problema integrado de dimensionamento e sequenciamento de lotes de produção. O processo de dimensionar e sequenciar lotes de produção consiste em determinar quanto produzir de cada produto e a sequência de produção desses lotes em cada máquina a cada período a fim de atender a uma demanda prevista sob as condições e capacidades operacionais existentes. O caso estudado nesse trabalho aborda o cenário de uma empresa de grande porte da indústria de bens de consumo de higiene pessoal, um mercado bastante concorrido no qual o bom nível de serviço de atendimento e a gestão de custos mostram-se essenciais na competição pelos clientes. Nessa empresa, existe um ambiente operacional complexo, composto por máquinas distintas em paralelo com capacidade limitada de produção cujos tempos de preparação (setup) são dependentes da sequência de produção, além de uma restrição de capacidade de armazenagem dos produtos fabricados, característica não encontrada na literatura existente. Os clientes permitem que ocorram atrasos de atendimento da demanda, porém isso é extremamente indesejável. Esse tipo de problema é NP-difícil, sendo geralmente tratado na literatura por heurísticas. Nesse trabalho, elaboramos nove diferentes estratégias de resolução baseadas na heurística relax-and-fix. O objetivo é, não somente resolver um problema real complexo, como também avaliar se o modo de articionamento e a sequência de resolução dos subproblemas influencia no desempenho da heurística. Os testes computacionais foram conduzidos em instâncias geradas aleatoriamente e em casos reais. Os resultados mostraram um bom desempenho e robustez da abordagem proposta. Técnicas alternativas foram aplicadas na estratégia com os melhores resultados para potencializar seu desempenho. / This work adresses the integrated lot sizing and scheduling problem. The process of lot sizing and scheduling consists of determining how much to produce of each product and the scheduling of these lots in each machine in order to meet the demand under existing restrictions and operational capabilities. The case studied in this work describes the scenario of a big company in the industry of consumer goods for personal hygiene, a very competitive market in which the good service level for customers and the cost management show up in the competition for the clients. In this company, there is a complex operational environment, composed of distinct parallel machines with limited production capacity and sequence dependente setup times. There is also a limited finished goods storage capacity, a characteristic not found in the existing literature. Backordering is allowed but it is extremely undesirable. This problem is NP-hard and it has been treated by heuristics in the literature. In this work, we developed nine different solving strategies based on the relax-and-fix heuristics. The aim of this approach is not only to solve a complex real problem but also assess whether the form of partitioning and the sequence of solving the subproblems influences the performance of the relax-and-fix heuristics. The computational experiments were conducted on ramdomly generated instances and real problems. The results showed the good performance and the robustness of the proposed approach. Alternative techniques were applied in the strategy with the best results in the previous tests to enhance its performance.

Neste trabalho, apresentamos um estudo sobre o problema de dimensionamento de lotes com múltiplas plantas, múltiplos itens e múltiplos períodos. As plantas têm capacidade de produção limitada e a fabricação de cada produto incorre em tempo e custo de preparação de máquina. Nosso objetivo é encontrar um plano de produção que satisfaça a demanda de todos os clientes, considerando que a soma dos custos de produção, de estoque, de transporte e de preparação de máquina seja a menor possível. Este trabalho tem duas contribuições centrais. Primeiramente, propomos a modelagem do problema de dimensionamento de lotes com múltiplas plantas utilizando o conceito de localização de facilidades. Para instâncias de pequena dimensão, os testes computacionais mostraram que a resolução do problema remodelado apresenta, como esperado, resultados melhores que o modelo original. No entanto, seu elevado número de restrições e de variáveis faz com que as instâncias de maiores magnitudes não consigam ser resolvidas. Para trabalhar com instâncias maiores, propomos um método híbrido (math-heurística), que combina o método relax-and-fix, com a restrição de local branching. Testes computacionais mostram que o método proposto apresenta soluções factíveis de boa qualidade para estas instâncias / In this work, we present a study about the multi-plant, multi-item, multi-period lot-sizing problem. The plants have limited capacity, and the production of each item implies in setup times and setup costs. Our objective is to find a production plan which satisfies the demand of every client, considering that the sum of the production, stocking, transport and setup costs is the lowest possible. This work has two main contributions. Firstly, we propose the multi-plant lot-sizing problem modeling using the facility location concept. For small dimension problems, computational tests showed that the remodeled problem resolution presents, as expected, better results than the original model. However, the great number of restrictions and variables make bigger instances to be intractable. To work with the bigger dimension instances, we propose a hybrid method (math-heuristic), which combines the relax-and-fix method and the local branching restriction. Computational tests show that the proposed math-heuristic presents good quality feasible solutions for these instances

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

Submitted by Filipe dos Santos (fsantos@pucsp.br) on 2017-02-16T12:26:05Z No. of bitstreams: 1 Ana Paula Goyos Browne.pdf: 1022443 bytes, checksum: 1971f4babcf0667fd18919603e8090fb (MD5) / Made available in DSpace on 2017-02-16T12:26:05Z (GMT). No. of bitstreams: 1 Ana Paula Goyos Browne.pdf: 1022443 bytes, checksum: 1971f4babcf0667fd18919603e8090fb (MD5) Previous issue date: 2017-02-09 / The present work deals with the division of urban areas under the condominium regime of lots, appreciating them from the perspective of Urban Law. Firstly, we find that lots condominiums are a form of urban expansion that is not appreciated by the law of land subdivision, Law 6.766/ 79 and, neither, by the condominiums law in buildings, Law 4.591/ 64. It is a hybrid modality that involves both public and private interests, and affects both private law and public law. This is private law with regard to the right to property, and its developments, regulated in particular by civil law. Nevertheless, it is an institute of public law, since it impacts on the urban space that is studied mainly by the urban law, but also by other branches of law such as administrative law and environmental law. The characteristics of the condominiums and the modalities of urban land subdivision were studied, highlighting the similarities and differences of these developments and pointing out that the condominiums of lots do not fit into any modality and require their own regulation. We emphasize the importance of the role played by municipalities in the regulation of urban space and the normative function of the State Courts of Justice, so that the implementation of lots condominiums is carried out in a controlled manner, with requirements and approvals that attenuate the impacts of Segregation in the right to the city. It was necessary to analyze other modalities of closed residential projects to differentiate and understand the legal discipline of lots condominiums. Finally, we have seen that the validity and application of constitutional and legal provisions permit the regularity of the condominiums of lots, in accordance with the established municipal norms, with the regulation of the General Office of Justice and with the premises of Urban Law / O presente trabalho trata da divisão de glebas urbanas sob o regime de condomínio de lotes, apreciando-os na perspectiva do Direito Urbanístico. Em primeiro lugar verificamos que os condomínios de lotes são uma forma de expansão urbana que não é apreciada pela lei de parcelamento do solo, Lei 6.766/79 e, tampouco, pela lei de condomínios em edificações, a Lei 4.591/64. É modalidade híbrida que envolve interesses públicos e privados, sendo afeta tanto ao Direito Privado como ao Direito Público. Trata-se de direito privado no que tange ao direito de propriedade, e seus desdobramentos, regulado em especial pelo direito civil. Não obstante, é instituto de direito público, já que impacta no espaço urbano que é estudado principalmente pelo do direito urbanístico, mas também por outros ramos do direito como o direito administrativo e o direito ambiental. Foram estudadas as características dos condomínios e as modalidades de parcelamento do solo urbano, destacando as semelhanças e diferenças destes empreendimentos e apontando que os condomínios de lotes não se enquadram em nenhuma modalidade e exige regulamentação própria. Destacamos a relevância do papel cumprido pelos municípios na regulamentação do espaço urbano e a função normativa da Corregedoria Geral de Justiça dos estados, a fim de que à implantação dos condomínios de lotes seja realizada de forma controlada, com requisitos e aprovações que atenuem os impactos da segregação no direito à cidade. Foi necessária a análise de outras modalidades de empreendimentos residenciais fechados para diferenciarmos e compreendermos a disciplina jurídica dos condomínios de lotes. Finalmente, vimos que a vigência e aplicação dos dispositivos constitucionais e legais permitem a regularidade dos condomínios de lotes, desde que em consonância com as normas municipais estabelecidas, com a regulamentação da Corregedoria Geral de Justiça e com as premissas do Direito Urbanístico

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.

Orientador: Silvio Alexandre de Araujo / Coorientador: Diego Jacinto Fiorotto / Banca: Kelly Cristina Poldi / Banca: Victor C. B. de Camargo / Resumo: 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 / Abstract: 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 / Mestre

Made available in DSpace on 2014-06-11T19:26:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-02-23Bitstream added on 2014-06-13T20:55:42Z : No. of bitstreams: 1 defalque_cm_me_sjrp.pdf: 681826 bytes, checksum: 4534893f3d08420f599caa3a4835df06 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, propomos um modelo integrado de dimensionamento de lotes e programação da produção para uma fábrica de refrigerantes de pequeno porte denominado P1S1MTS. Neste modelo, as decisões de dimensionamento foram baseadas no modelo P1S1M encontrado na literatura, formulado com base no modelo GLSP. As decisões de sequenciamento foram modeladas utilizando restrições do problema do caixeiro viajante assimétrico. Para validação do modelo proposto e comparação entre os modelos P1S1MTS e P1S1M foram feitos testes computacionais com exemplares ilustrativos. Foram realizados também testes com exemplares baseados em dados reais da fábrica de refrigerantes e exemplares gerados aleatoriamente. Os testes foram resolvidos pelo método Branch-and-Cut incluído no pacote computacional CPLEX 10.0. Notamos que com algumas modificações, é possível que ambos os modelos retratem a mesma situação. A partir destas modificações e com os resultados obtidos, concluímos que a resolução de exempalres do modelo P1S1MTS apresentou um tempo de execução computacioanl menor que a resolução de exemplares do modelo P1S1M gerados com os mesmos dados. / In this work we propose a lot sizing and scheduling model, P1S1MTS, for a smallscale soft drink plant. In this model, the lot sising decisions were based on the P1s!m model found in the literaure. To model the scheduling decisions constraints of the asynmetric traveling salesman problem are used. For the validation of the proposed model and a comparison between the P1S1MTS and the P1S1M models computational tests were executed with illustratuve examples. Tests were also executed with examples based on real data and randomly generated instances. Tests were also executed with examples based on real data and randomly in the software CPLEX 10.0. The results showed taht, with some minor modifications, it is possible that both models depict same situation. From the results obtained we concluded that the P1s!MTS model presented a computational time performance better than the P1S1M model.

Made available in DSpace on 2014-06-11T19:27:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-03-23Bitstream added on 2014-06-13T19:15:35Z : No. of bitstreams: 1 silva_fm_me_sjrp.pdf: 817059 bytes, checksum: eb6c0e0e69f3687d3831dbbbc3cf6e09 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Este trabalho consiste numa extensão do estudo de um problema de dimensionamento de lotes com custo de transporte feito por Norden e Velde [53], onde a produção dos itens é transportada, em paletes, para um armazém. O transporte é feito por uma empresa terceirizada sob um contrato com os seguintes custos pré-estabelecidos: um custo fixo de contrato, um custo para o transporte de um determinado volume de paletes e um custo adicional para paletes extras. O problema foi estendido, no presente trabalho, considerando restrições de capacidade e a possibilidade de atrasos no atendimento a demanda. Nosso objetivo é propor um modelo matemático para o problema estendido e desenvolver dois métodos heurísticos de resolução. Tais métodos são baseados em dois tipos de relaxação: relaxação Lagrangiana e relaxação Lagrangiana/Surrogate. Os resultados obtidos pelas heurísticas são comparados com os resultados obtidos pelo pacote de otimização CPLEX 10.0. Além disso, é feita uma comparação entre os métodos heurísticos. / This work consist of an extension of a study of the capacitated lot-sizing problems with transportation cost by Norden and Velde [53], where the production of itens is transported into pallets to an warehouse. The transportation is executed by another company, under a contract with the following transportation cost established: a fixed contract cost, a transportation cost for determined quantity of pallets and an additional cost for extra pallets. The problem was extended, in this work, considering capacity constraint and backlogging. Our objective is to propose a mathematical model for the extended problem and to develop two heuristics methods of resolution. The methods are based on two types of relaxation: Lagrangian relaxation and Lagrangian/Surrogate relaxation. The results obtained by heuristics are compared with the results obtained by CPLEX 10.0. Furthermore, a comparison between the heuristics is made.

Made available in DSpace on 2016-06-02T19:51:23Z (GMT). No. of bitstreams: 1 DissEAVT.pdf: 1007944 bytes, checksum: 161890ccd40c1109dd2342d0421e9add (MD5) Previous issue date: 2003-01-01 / Universidade Federal de Minas Gerais / The object of this work is the integrated problem of lot sizing and sequencing the production of feed for animal nutrition. Such problem consists of deciding how much to produce of each feed in each period, taking itself in account the production sequencing of the lots, in way to satisfy the demand and to minimize the costs of production and storage. A case study was carried through in the facility of supplements from a company of this industry, located inland São Paulo, whose problem can be seen as multi-item, single-period and capacitated. One of the great difficulties to the production planning in this factory is the difficulty to adjust the productive capacity with the demand is season of the products, integrating the lot sizing decisions with the line scheduling decisions, since setup times are dependent of the production sequence. This work use integer linear programming for modeling the problem, which is solved with of the modeling language GAMS/CPLEX. To evaluate the performance of the considered model tests with real data had been carried through. The results show that the model can be useful to support the decisions of lot sizing and sequencing, therefore the solutions of the model in the tests realized are better than the ones elaborated by the production planning department of the company. / O objeto deste trabalho é o problema integrado de dimensionamento de lotes e sequenciamento da produção de rações para nutrição animal. Tal problema consiste em decidir quanto produzir de cada ração em cada período, levando-se em conta a seqüência de produção dos lotes, de maneira a satisfazer a demanda e minimizar os custos de produção e estocagem. Um estudo de caso foi realizado na unidade de suplementos de uma empresa do setor, localizada no interior de São Paulo, cujo problema pode ser visto como multi-item, monoestágio e capacitado. Uma das grandes dificuldades para o planejamento da produção nesta indústria é a dificuldade de ajustar a capacidade produtiva a sazonalidade da demanda dos produtos, integrando as decisões de dimensionamento dos lotes e as decisões de sequenciamento, uma vez que os tempos de preparação (setup) são dependentes da seqüência produtiva. Neste trabalho utiliza-se um modelo de programação linear inteira para tratar o problema, que é resolvido por meio de linguagem de modelagem GAMS/ CPLEX. Para avaliar o desempenho do modelo foram realizados testes com dados reais. Os resultados obtidos mostram que o modelo pode ser útil para apoiar as decisões de dimensionamento e seqüenciamento de lotes, pois os resultados do modelo nos testes realizados foram melhores que os elaborados pelo planejamento da empresa.

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-16T11:42:54Z No. of bitstreams: 1 arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5) / Made available in DSpace on 2017-08-16T11:42:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5) Previous issue date: 2016-07-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The problem of scheduling on a single machine, proven to be NP-hard, consists of de ning the job grouping in batches and of the sequence in which these batches will be processed on a machine. Each job is associated with a release date, a processing time, a due date, a priority level in relation to the others and a size. The machine is able to process a group of jobs (batch) simultaneously, provided that the sum of the job sizes belonging to the referred batch does not exceed the machine capacity. Each job must be processed only once and only one batch is processed at a time on the machine. In this work, we consider the objective as the minimization of total weighted tardiness, where the tardiness of a job is the di erence between its completion time and its due date, in case the job processing is nished after its due date and hence is late, or equals zero, otherwise. In the literature, this problem is usually referred to as 1jbatch; rj ; sj ; comptjPwjTj . When all jobs are available to be processed at time zero, the problem is usually represented as 1jbatch; sj ; comptjPwjTj . These problems are still poorly explored in the literature and in addition, cover a large number of variant forms. There are few studies involving the application of exact methods for solving both. Only one mathematical formulation was identi ed in the literature for these problems. Hence, four time-indexed formulations were developed to solve the aforementioned problems, one of which is capable of dealing with both problems. The results achieved by the developed models were compared between themselves and with the results of the model available in the literature. These computational results reveal that two of the proposed models obtained higher performance both in terms of quality of the solution, particularly regarding the achieved lower bounds, and in numbers of open nodes and of proven optimal solutions. / O problema de sequenciamento de lotes da produ c~ao em uma m aquina, comprovadamente tido como NP-dif cil, consiste na de ni c~ao do agrupamento de tarefas em lotes e da sequ^encia em que estes ser~ao processados em uma m aquina. Cada tarefa est a associada a uma data de libera c~ao, um tempo de processamento, uma data de entrega, um n vel de prioridade em rela c~ao as demais, e um tamanho. A m aquina e capaz de processar um conjunto de tarefas (lote) simultaneamente, contanto que a soma dos tamanhos das tarefas pertencentes ao referido lote respeite a capacidade da m aquina. Cada tarefa deve ser processada apenas uma vez e somente um lote e processado por vez na m aquina. Neste trabalho, considera-se como objetivo a minimiza c~ao do total de atrasos ponderados, onde o atraso de uma tarefa e igual ao seu tempo de t ermino menos a sua data de entrega, caso o processamento da tarefa seja nalizado ap os a sua data da entrega e, portanto, em atraso, e e igual a zero, caso contr ario. Na literatura, este problema e geralmente referenciado como 1jbatch; rj ; sj ; comptjPwjTj . Quando todas as tarefas est~ao dispon veis para serem processadas no instante de tempo zero, o problema e usualmente representado por 1jbatch; sj ; comptjPwjTj . Estes s~ao problemas ainda pouco investigados na literatura e, al em disso, abordam uma grande quantidade de variantes. Existem poucos trabalhos envolvendo a aplica c~ao de m etodos exatos para a resolu c~ao de ambos. Apenas uma formula c~ao matem atica foi identi cada na literatura para estes problemas. Dessa forma, quatro formula c~oes matem aticas com vari aveis indexadas no tempo foram desenvolvidas para resolver os problemas mencionados anteriormente, das quais uma e capaz de tratar de ambos os problemas. Os resultados alcan cados por meio dos modelos desenvolvidos foram comparados entre si e com os resultados do modelo dispon vel na literatura. Tais resultados computacionais demonstram que dois dos modelos propostos obtiveram desempenho superior tanto em termos de qualidade da solu c~ao, em especial em rela c~ao aos limites inferiores alcan cados, quanto em n umeros de n os abertos e quantidade de solu c~oes otimas comprovadas.