A presente pesquisa tem como objetivo estudar a integração entre dois temas clássicos da literatura de pesquisa operacional e gestão de operações: problemas de corte e empacotamento; e problemas de programação da produção. Ainda que sejam duas áreas intensamente exploradas e pesquisadas, e, ainda, que seja uma situação facilmente encontrada em sistemas de produção reais, abordagens de ambos problemas de forma coordenada ainda carecem de maiores pesquisas. Neste trabalho é feita uma revisão de ambos temas, com foco em problemas de bin packing e programação em ambiente de máquina única com objetivo de minimizar soma de atrasos e adiantamentos ponderados. Uma formulação matemática linear e inteira mista é proposta para o problema, contemplando as restrições que concernem a cada um e também à sua consideração simultânea. Como se trata de um problema que une dois outros, cada um NP-hard isoladamente, um método heurístico é proposto para obter uma solução interessante em tempos computacionais bastante reduzidos. Foram obtidas propriedades físicas de definição de data ideal de programação de um conjunto de itens atribuídos a um bin. Também é proposto um método para geração de um limitante inferior melhorado em relação a pacotes de otimização de mercado para o problema. Ambos métodos foram testados em uma massa de dados de 1.152 instâncias, geradas para retratar cenários de diferentes datas de entrega, setups, custos de atraso e adiantamento em relação à matéria-prima, tamanho de itens e número de itens na instância. Os resultados mostram-se largamente superiores aos obtidos por um otimizador genérico (CPLEX), embora ainda sejam gaps excessivamente grandes, o que reforça a dificuldade do problema. / The present research aims to explore the integration between two classic themes on operations research and operations management literature: cutting and packing problems; and production scheduling problems. Although they are intensive explored and researched areas and, besides, it\'s an easily found situation on real production systems, coordinated approaches of both themes still need deeper research. On this paper, it was done a review of both themes, focusing on bin packing problems and single-machine environment scheduling problems aiming to minimize total weighed earliness and tardiness. A mixed integer-linear mathematical formulation is proposed to the problem, including constraints referred to each problem and, also, to their simultaneous consideration. Once it\'s a problem that joins the other two, each one NP-hard solely, an heuristic method is proposed to obtain an interesting solution in reasonable computational times. Physical properties were identified, defining the best date to allocate a given lot of items to be processed together. Also, a lower bound generation method is proposed, improving the one generated by optimization softwares. Both methods were tested on a 1.152 instances mass of data, generated to represent well several scenarios of different due dates, setup times, earliness and tardiness costs compared to raw material, size of items and number the items the instance. Results show largely superiority the ones obtained by an optimization pack (CPLEX), although gaps are still excessively large, fact the reinforces problem\'s difficulty.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.

Made available in DSpace on 2015-04-22T22:10:50Z (GMT). No. of bitstreams: 1 diego.pdf: 1646868 bytes, checksum: 184608f031ef1b7a63b685a26977dde9 (MD5) Previous issue date: 2010-10-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This paper presents a model for programming calibration services balance, applied to a calibration laboratory installed in the city of Manaus, in order to promote improvements in the management of productive capacity. The calibration of the measuring instrument is part of the metrological services that support enterprises that have a quality management system certificate. The proposed model, seeking to align itself with these management practices, adopts the structure of the mapping process organized phases input, processing and output. The research method used to construct the model is the literature in the areas of production management, service management and metrology. This consultation revealed some difficulties because the approach is relatively new in the service area. In this context, we surveyed the main features present in any operation targeting the sort of service calibration laboratory. The classification was established by combining the characteristics of the activities of front line service represented by the calibration scale and the rear of activities by managing the laboratory calibration, resulting in framing shop services based on the volume of customers served by day at the plant. In our case, the high degree of standardization and repeatability in this provision of the calibration scale, facilitated the use of tools of production planning and control, through the technical choice of sequencing of work orders and their proper calibration schedule, being pulled to the type selected. To evaluate this process were investigated performance measures consistent with the service sector, revealing management indicators applicable in the following the calibration of instruments. The results contributed to increasing productivity in services researched, reflecting the adoption of certain management practices based on principles of production system used in the manufacturing area. / Este trabalho apresenta um modelo para programação dos serviços de calibração de balança, aplicado a um laboratório de calibração instalado na cidade de Manaus, com o objetivo de promover melhorias na gestão da capacidade produtiva. A calibração de instrumento de medição faz parte dos serviços de metrologia que dão suporte às empresas que possuem um sistema de gestão da qualidade certificado. O modelo proposto, buscando alinhar-se com essas práticas de gestão, adota a estrutura do mapeamento de processo organizado nas fases entrada, transformação e saídas. O método de pesquisa utilizado para construir o modelo foi o bibliográfico nas áreas de administração da produção, gestão de serviços e metrologia. Essa consulta revelou algumas dificuldades devido à abordagem ser relativamente nova na área de serviços. Nesse contexto, foram pesquisadas as principais características presentes em qualquer operação visando classificar os serviços do laboratório de calibração. A classificação foi estabelecida ao combinar as características das atividades de linha de frente representada pelo serviço de calibração de balança e as atividades de retaguarda por meio do gerenciamento do laboratório de calibração, resultando no enquadramento de loja de serviços com base no volume de clientes atendidos por dia na unidade produtiva. No caso estudado, o alto grau de padronização e repetitividade presente na prestação do serviço calibração de balança facilitaram o uso de ferramentas de planejamento e controle da produção, através da escolha da técnica de sequenciamento das ordens de serviços de calibração e sua devida programação, sendo a do tipo puxada selecionada. Para avaliar esse processo foram pesquisadas medidas de desempenho compatíveis com o setor de serviços, revelando indicadores gerenciais aplicáveis no seguimento de calibração de instrumentos. Os resultados obtidos contribuíram para o aumento da produtividade no setor de serviços pesquisado, refletindo a adoção de algumas práticas de gerenciamento baseado em princípios do sistema da produção utilizados na área de manufatura.

Neste trabalho será estudado um ambiente de produção que é freqüentemente encontrado na prática: o flowshop com múltiplos processadores. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Todas as tarefas devem ser processadas por todos os estágios. O objetivo é minimizar o atraso das tarefas. Primeiramente o problema foi abordado através de um método que programa as tarefas por estágio e em ordem direta, ou seja, do primeiro para o último estágio. Em seguida, foram desenvolvidas duas novas regras que utilizam o mesmo método de programação, porém consideram o ambiente como uma série de problemas de máquinas em paralelo. Uma das regras desenvolvidas tem como característica principal considerar estados futuros do sistema. Também foi desenvolvido um novo método de programação em ordem inversa, no qual as tarefas são programadas do último para o primeiro estágio. Este método apresenta melhor desempenho se comparado com o método de programação em ordem inversa da literatura. Por último foi desenvolvido um método de programação com foco no estágio gargalo, visto que este estágio pode impedir um bom fluxo das tarefas pelo sistema e resultar em uma conclusão tardia das mesmas. Este método é mais simples, rápido e tem resultados competitivos frente ao método com foco no gargalo da literatura. / This work considers a production environment that is frequently found in practice: the flexible flowshop. In the case studied, there are stages in series and in each stage there are a number of identical parallel machines. All jobs must be processed by all stages. The objective is to minimize the tardiness of jobs. First the problem was addressed by a method in which jobs are schedule forward, that is, from first to last stage. Two new rules were developed using this same method, but considering the environment as a series of parallel machines problems. One of the rules is able to consider future states of the system. It was also developed a new method in which jobs are scheduled backward, i.e., from last to first stage. This method shows better performance compared to the literature method. At last, it was developed a method that focus on the bottleneck stage scheduling (since this stage may prevent a good flow of jobs throughout the system and result in late completions). This method is simpler, faster and competitive next to the literature method.

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.

Made available in DSpace on 2016-06-02T19:51:30Z (GMT). No. of bitstreams: 1 DissJRDL.pdf: 648879 bytes, checksum: d0336140896c62906f4999d62e04668f (MD5) Previous issue date: 2003-01-01 / This work presents optimization models to support decisions of the Production Planning and Control (PPC) in the industry of grains electrocasting. A case study was accomplished in one of the largest companies in the State of São Paulo. The objective of the study is to contribute for the improvement of the system of PCP of companies of grains electrocasting, in such a way to obtain gains of productivity and to improve the user service level with respect to due date satisfaction. For that Mixed Integer Linear Programming models were applied to aid particularly in the decisions of production scheduling. Optimizing the production scheduling in the industry of grains electrocasting is not a simple task, mainly due to the greatness of setup times of the equipments, the diversity of products and the limitations of the order due dates. / Este trabalho apresenta modelos de otimização para apoiar decisões do Planejamento e Controle da Produção (PCP) na indústria de grãos eletrofundidos. Um estudo de caso foi realizado numa das maiores empresas do setor no estado de São Paulo. O objetivo do estudo é contribuir para a melhoria do sistema de PCP de empresas de grãos eletrofundidos, de maneira a obter ganhos de produtividade e melhorar o nível de serviço aos clientes no atendimento dos prazos de entrega. Para isso, foram aplicados modelos de Programação Linear Inteira Mista para auxiliar particularmente nas decisões da programação da produção, e analisar os resultados obtidos. Otimizar a programação da produção na indústria de grãos eletrofundidos não é uma tarefa simples, principalmente devido à grandeza dos tempos de preparação dos equipamentos, à diversidade de produtos e às limitações dos prazos de entrega.

Made available in DSpace on 2016-06-02T19:51:42Z (GMT). No. of bitstreams: 1 2820.pdf: 746407 bytes, checksum: 8dba34a22c959017a0c27b0c233087b3 (MD5) Previous issue date: 2009-08-28 / The modeling process of the fine (detailed) production scheduling is responsible for mapping and planning of all activities relative to the production tasks. Conceptual models are references for these activities and also to support the implementation of the scheduling. In this work, a model is proposed considering data collection, analysis, data processing and provided information. Using this model it's possible to take decision based on data that are accurated, detailed and easy to get. / O processo modelagem de programação detalhada da produção é responsável pelo mapeamento e planejamento de todas as atividades de programação produção. Modelos conceituais são referências para implantação e organização deste processo. É proposto um modelo que considera a coleta de dados, análise, tratamento e disponibilização destes dados, permitindo que sejam tomadas decisões com base em dados mais precisos, detalhados e fáceis de serem obtidos.

A presente pesquisa tem como objetivo estudar a integração entre dois temas clássicos da literatura de pesquisa operacional e gestão de operações: problemas de corte e empacotamento; e problemas de programação da produção. Ainda que sejam duas áreas intensamente exploradas e pesquisadas, e, ainda, que seja uma situação facilmente encontrada em sistemas de produção reais, abordagens de ambos problemas de forma coordenada ainda carecem de maiores pesquisas. Neste trabalho é feita uma revisão de ambos temas, com foco em problemas de bin packing e programação em ambiente de máquina única com objetivo de minimizar soma de atrasos e adiantamentos ponderados. Uma formulação matemática linear e inteira mista é proposta para o problema, contemplando as restrições que concernem a cada um e também à sua consideração simultânea. Como se trata de um problema que une dois outros, cada um NP-hard isoladamente, um método heurístico é proposto para obter uma solução interessante em tempos computacionais bastante reduzidos. Foram obtidas propriedades físicas de definição de data ideal de programação de um conjunto de itens atribuídos a um bin. Também é proposto um método para geração de um limitante inferior melhorado em relação a pacotes de otimização de mercado para o problema. Ambos métodos foram testados em uma massa de dados de 1.152 instâncias, geradas para retratar cenários de diferentes datas de entrega, setups, custos de atraso e adiantamento em relação à matéria-prima, tamanho de itens e número de itens na instância. Os resultados mostram-se largamente superiores aos obtidos por um otimizador genérico (CPLEX), embora ainda sejam gaps excessivamente grandes, o que reforça a dificuldade do problema. / The present research aims to explore the integration between two classic themes on operations research and operations management literature: cutting and packing problems; and production scheduling problems. Although they are intensive explored and researched areas and, besides, it\'s an easily found situation on real production systems, coordinated approaches of both themes still need deeper research. On this paper, it was done a review of both themes, focusing on bin packing problems and single-machine environment scheduling problems aiming to minimize total weighed earliness and tardiness. A mixed integer-linear mathematical formulation is proposed to the problem, including constraints referred to each problem and, also, to their simultaneous consideration. Once it\'s a problem that joins the other two, each one NP-hard solely, an heuristic method is proposed to obtain an interesting solution in reasonable computational times. Physical properties were identified, defining the best date to allocate a given lot of items to be processed together. Also, a lower bound generation method is proposed, improving the one generated by optimization softwares. Both methods were tested on a 1.152 instances mass of data, generated to represent well several scenarios of different due dates, setup times, earliness and tardiness costs compared to raw material, size of items and number the items the instance. Results show largely superiority the ones obtained by an optimization pack (CPLEX), although gaps are still excessively large, fact the reinforces problem\'s difficulty.

Neste trabalho será estudado um ambiente de produção que é freqüentemente encontrado na prática: o flowshop com múltiplos processadores. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Todas as tarefas devem ser processadas por todos os estágios. O objetivo é minimizar o atraso das tarefas. Primeiramente o problema foi abordado através de um método que programa as tarefas por estágio e em ordem direta, ou seja, do primeiro para o último estágio. Em seguida, foram desenvolvidas duas novas regras que utilizam o mesmo método de programação, porém consideram o ambiente como uma série de problemas de máquinas em paralelo. Uma das regras desenvolvidas tem como característica principal considerar estados futuros do sistema. Também foi desenvolvido um novo método de programação em ordem inversa, no qual as tarefas são programadas do último para o primeiro estágio. Este método apresenta melhor desempenho se comparado com o método de programação em ordem inversa da literatura. Por último foi desenvolvido um método de programação com foco no estágio gargalo, visto que este estágio pode impedir um bom fluxo das tarefas pelo sistema e resultar em uma conclusão tardia das mesmas. Este método é mais simples, rápido e tem resultados competitivos frente ao método com foco no gargalo da literatura. / This work considers a production environment that is frequently found in practice: the flexible flowshop. In the case studied, there are stages in series and in each stage there are a number of identical parallel machines. All jobs must be processed by all stages. The objective is to minimize the tardiness of jobs. First the problem was addressed by a method in which jobs are schedule forward, that is, from first to last stage. Two new rules were developed using this same method, but considering the environment as a series of parallel machines problems. One of the rules is able to consider future states of the system. It was also developed a new method in which jobs are scheduled backward, i.e., from last to first stage. This method shows better performance compared to the literature method. At last, it was developed a method that focus on the bottleneck stage scheduling (since this stage may prevent a good flow of jobs throughout the system and result in late completions). This method is simpler, faster and competitive next to the literature method.

Este trabalho aborda o problema de programação da produção em um flexible flow line com tempos de setup. De acordo com a literatura, este ambiente pode ser considerado como um caso especial do Flow Shop com múltiplas máquinas, onde as tarefas podem saltar estágios. Neste estudo, foram analisados dois problemas: o primeiro, com tempos de setup independentes da sequência, e o segundo, com setup dependente da sequência de tarefas. Além disso, o setup das máquinas para as tarefas pode ser antecipado ou não. No primeiro caso, as máquinas de um estágio podem ser preparadas para o processamento de uma tarefa antes do seu término no estágio anterior. Se o setup não pode ser antecipado, a tarefa deve esperar o seu término no estágio de produção anterior. Este ambiente produtivo pode ser encontrado em um vasto número de indústrias tais como química, eletrônica, automotiva e têxtil. A medida de desempenho dos problemas é a duração total da programação (makespan). Este é um critério apropriado para sistemas de produção com grandes cargas de trabalho e em que a utilização dos recursos produtivos em longo prazo deve ser otimizada. O exame da literatura mostrou que há poucos estudos abordando a programação em flexible flow line. Considerando este aspecto, este trabalho apresenta heurísticas construtivas originais para a obtenção de programações apropriadas ao problema mencionado. Uma extensiva experimentação computacional foi executada para avaliar o desempenho relativo das heurísticas. Os resultados experimentais foram analisados e discutidos. / This work addresses the job scheduling on a flexible flow line with separate setup times. According to the literature, this scheduling problem can be considered as a special case of the Flow Shop with multiple machines, where the jobs may skip stages. Two modeled problems have been studied. In the first scheduling problem the setup times are sequence independent, and in the second one these times are sequence dependent. Moreover, the machine setup task can be either anticipatory or non-anticipatory. In the first case, a k-stage machine may be prepared for a job processing before its completion on the k-1 production stage. Otherwise, the setup task must wait for the job completion on the former production stage. This production environment can be found in a number of industries such as chemicals, electronics, automotive, and textiles. The performance measure of the production schedules is the makespan, that is, the total time to complete the schedule. This is an appropriate performance criterion for production systems with large workloads, and where the utilization of productive resources in the long term should be optimized. The literature examination has shown that there is a small number of studies dealing with flexible flow line scheduling. Having this in mind, this work introduces original constructive heuristics in order to obtain suitable schedules for the aforementioned scheduling problem. An extensive computational experience has been carried out in order to evaluate the relative performance of the heuristics. Experimental results are discussed.