Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching). / This study focuses a job scheduling problem in a flow shop with some specific features, which, all together, make it different from the usual flow shop scheduling problems. There are N jobs to be processed in M different machines and each job has a particular route, skipping, eventually, one or more machines; each job should be finished within a time interval, called time window, and there are penalties for earliness and tardiness. This is a combinatorial problem for which, in the extreme case, there are (N!)^M solutions, belonging to NP-Hard class. In this study, a mathematical model is proposed for representing the problem; the CPLEX solver is used for solving the mixed integer linear problem obtained. Given the computational complexity of the model, heuristic procedures are proposed in order to solve large- scale instances of this problem. Combined procedures, using an initial solution obtained by a proposed heuristic and the mathematical model, either using the general branching procedure of CPLEX or a specific local branching procedure, are also shown.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A maioria dos paÃses do globo tem incrementado o uso do gÃs natural, motivados pela necessidade de uma fonte energÃtica mais limpa e polivalente. PorÃm, para se obter os reais benefÃcios do gÃs natural à preciso priorizar o seu uso atravÃs de alternativas que possibilitem alta eficiÃncia energÃtica. Dentre estas alternativas, sÃo destacadas a substituiÃÃo do uso da eletricidade para aquecimento ou resfriamento (eletrotermia), a substituiÃÃo do GLP nas cozinhas e o suprimento de sistemas de cogeraÃÃo. A efetivaÃÃo destas estratÃgias produziria impactos positivos principalmente nos setores residencial e comercial, pois as residÃncias e estabelecimentos comerciais nÃo tÃm acesso ao gÃs natural e nem sequer dispÃem de informaÃÃes acerca das novas tecnologias disponÃveis para operaÃÃo em setores de pequena escala de consumo. Portanto, à fundamental que as distribuidoras de gÃs natural utilizem as infra-estruturas de distribuiÃÃo disponÃveis para facilitar a acessibilidade ao combustÃvel. Como a decisÃo acerca da implantaÃÃo de infra-estruturas de distribuiÃÃo de gÃs natural à de carÃter estratÃgico, o objetivo primordial deste trabalho à elaborar um modelo para minimizar os custos de implantaÃÃo de infra-estruturas para distribuiÃÃo de gÃs natural. Desta forma, foi desenvolvido um modelo matemÃtico utilizando programaÃÃo linear binÃria para apontar quais as infra-estruturas de distribuiÃÃo de gÃs natural devem ser implantadas, de modo a minimizar o custo total. Na resoluÃÃo do modelo foi utilizado o software LINGO 7.0. O modelo proposto foi validado atravÃs de testes em 3 cenÃrios elaborados, demonstrando-se eficiente e flexÃvel, permitindo a obtenÃÃo da soluÃÃo Ãtima mesmo quando sujeito a variaÃÃes dos parÃmetros de entrada. Estas variaÃÃes, representadas pelos cenÃrios elaborados, sÃo situaÃÃes reais que podem acontecer durante a operaÃÃo do sistema de distribuiÃÃo de gÃs natural / Most countries in the world has been increasing the use of the natural gas, motivated by the need of an environmental and versatile energy source. However, to obtain high benefits of the natural gas use, it is necessary to spread its use through alternatives that make possible high energy efficiency. Among these alternatives, the substitution of the electricity use for heating or cooling, and the PLG use in the kitchens, as well as the supply for cogeneration systems must be emphasized. The adoption of these strategies will produce effective economical environmental returns mainly in the residential and commercial sectors, if residences and commercial establishments do have access to natural gas and also information concerning the new available technologies for operation in those small scale consumption sectors. Therefore, it is fundamental that the natural gas dealers provide better acessibility to the distribution infrastructures. Considering that the decision concerning the infrastructures implantation for distribution of natural gas is strategic, the primordial objective of this work is to build a model to minimize the costs of providing of infrastructures for natural gas distribution. For this, a mathematical model was developed using binary linear programming to indicate infrastructures to be implemented which minimize the total supply costs. The software LINGO 7.0. was used to help in the solution of the problem. Three tests of the model were run which present good reults. The model led to optimal solutions even when subjected to variations of the input parameters, proving to be efficient and flexible. These variations, considered in the different sceneries, represent real situations that may happen during the operation of natural gas distribution system

Production planning problems are of paramount importance within supply chain planning, supporting decisions on the transformation of raw materials into finished products. Lot sizing in production planning refers to the tactical/operational decisions related to the size and timing of production orders to satisfy a demand. The objectives of lot-sizing problems are generally economical-related, such as saving costs or increasing profits, though other aspects may be taken into account such as quality of the customer service and reduction of inventory levels. Lot-sizing problems are very common in production activities and an efficient planning of such activities gives the company a clear advantage over concurrent organizations. To that end it is required the consideration of realistic features of the industrial environment and product characteristics. By means of mathematical modelling, such considerations are crucial, though their inclusion results in more complex formulations. Although lot-sizing problems are well-known and largely studied, there is a lack of research in some real-world aspects. This thesis addresses two main characteristics at the lot-sizing context: (a) setup crossover; and (b) perishable products. The former allows the setup state of production line to be carried over between consecutive periods, even if the line is not yet ready for processing production orders. The latter characteristic considers that some products have fixed shelf-life and may spoil within the planning horizon, which clearly affects the production planning. Furthermore, two types of perishable products are considered, according to the duration of their lifetime: medium-term and short-term shelf-lives. The latter case is tighter than the former, implying more constrained production plans, even requiring an integration with other supply chain processes such as distribution planning. Research on stronger mathematical formulations and solution approaches for lot-sizing problems provides valuable tools for production planners. This thesis focuses on the development of mixed-integer linear programming (MILP) formulations for the lot-sizing problems considering the aforementioned features. Novel modelling techniques are introduced, such as the proposal of a disaggregated setup variable and the consideration of lot-sizing instead of batching decisions in the joint production and distribution planning problem. These formulations are subjected to computational experiments in state-of-the-art MILP-solvers. However, the inherent complexity of these problems may require problemdriven solution approaches. In this thesis, heuristic, metaheuristic and matheuristic (hybrid exact and heuristic) procedures are proposed. A lagrangean heuristic addresses the capacitated lot-sizing problem with setup carryover and perishable products. A novel dynamic programming procedure is used to achieve the optimal solution of the uncapacitated single-item lot-sizing problem with setup carryover and perishable item. A heuristic, a fix-and-optimize procedure and an adaptive large neighbourhood search approach are proposed for the operational integrated production and distribution planning. Computational results on generated set of instances based on the literature show that the proposed methods yields competitive performances against other literature approaches. / Problemas de planejamento da produção são de suma importância no planejamento da cadeia de suprimentos, dando suporte às decisões da transformação de matérias-primas em produtos acabados. O dimensionamento de lotes em planejamento de produção é definido pelas decisões tático-operacionais relacionadas com o tamanho das ordens de produção e quando fabricá-las para satisfazer a demanda. Os objetivos destes problemas são geralmente de cunho econômico, tais como a redução de custos ou o aumento de lucros, embora outros aspectos possam ser considerados, tais como a qualidade do serviço ao cliente e a redução dos níveis de estoque. Problemas de dimensionamento de lotes são muito comuns em atividades de produção e um planejamento eficaz de tais atividades, estabelece uma clara vantagem à empresa em relação à concorrência. Para este objetivo, é necessária a consideração de características realistas do ambiente industrial e do produto. Para a modelagem matemática do problema, estas considerações são cruciais, embora sua inclusão resulte em formulações mais complexas. Embora os problemas de dimensionamento de lotes sejam bem conhecidos e amplamente estudados, várias características reais importantes não foram estudadas. Esta tese aborda, no contexto de dimensionamento de lotes, duas características muito relevantes: (a) preservação da preparação total e parcial; e (b) produtos perecíveis. A primeira permite que o estado de preparação de uma linha de produção seja mantido entre dois períodos consecutivos, mesmo que a linha de produção ainda não esteja totalmente pronta para o processamento de ordens de produção. A ultima característica determina que alguns produtos tem prazo de validade fixo, menor ou igual do que o horizonte de planejamento, o que afeta o planejamento da produção. Além disso, de acordo com a duração de sua vida útil, foram considerados dois tipos de produtos perecíveis: produtos com tempo de vida de médio e curto prazo. O ultimo caso resulta em um problema mais apertado do que o anterior, o que implica em planos de produção mais restritos. Isto pode exigir uma integração com outros processos da cadeia de suprimentos, tais como o planejamento de distribuição dos produtos acabados. Pesquisas sobre formulações matemáticas mais fortes e abordagens de solução para problemas de dimensionamento de lotes fornecem ferramentas valiosas para os planejadores de produção. O foco da tese reside no desenvolvimento de formulações de programação linear inteiro-mistas (MILP) para os problemas de dimensionamento de lotes, considerando as características mencionadas anteriormente. Novas técnicas de modelagem foram introduzidas, como a proposta de variáveis de preparação desagregadas e a consideração de decisões de dimensionamento de lotes ao invés de decisões de agrupamento de ordens de produção no problema integrado de planejamento de produção e distribuição. Estas formulações foram submetidas a experimentos computacionais em MILP-solvers de ponta. No entanto, a complexidade inerente destes problemas pode exigir abordagens de solução orientadas ao problema. Nesta tese, abordagens heurísticas, metaheurísticas e matheurísticas (híbrido de métodos exatos e heurísticos) foram propostas para os problemas discutidos. Uma heurística lagrangeana aborda o problema de dimensionamento de lotes com restrições de capacidade, preservação da preparação total e produtos perecíveis. Um novo procedimento de programação dinâmica e utilizado para encontrar a solução ótima do problema de dimensionamento de lotes de um único produto perecível, sem restrições de capacidade e preservação da preparação total. Uma heurística, um procedimento x-and-optimize e uma abordagem por buscas adaptativas em grande vizinhanças são propostas para o problema integrado de planejamento de produção e distribuição. Resultados computacionais em conjuntos de instâncias geradas com base na literatura mostram que os métodos propostos obtiveram performances competitivas com relação a outras abordagens da literatura.

Este trabalho propõe modelos matemáticos e heurísticas para a definição da malha de voos de uma empresa aérea, como parte de seu planejamento operacional, visando à maior eficiência de operação frente às restrições relacionadas aos aeroportos, a equipamentos e à demanda. Em especial, é proposta uma função objetivo, baseada no momento de transporte, para a modelagem integrada dos problemas de Programação de Voos e Alocação de Frotas que inclui elementos específicos para a consideração de slots de pouso e decolagem. A abordagem tem aplicação especialmente relevante no âmbito de empresas aéreas de pequeno e médio porte atuando em mercados regionais, cuja malha é composta principalmente por voos de curta duração, em geral operando com aeronaves de pequeno e médio porte. Nestas condições, tais empresas trabalham com margens de lucro limitadas e, portanto, podem-se beneficiar sensivelmente da definição de uma malha mais eficiente e eficaz. Os modelos desenvolvidos, baseados em programação linear inteira e na meta-heurística Ant Colony Optimization, foram aplicados com sucesso ao caso de uma empresa aérea regional, com atuação no mercado brasileiro, possibilitando a definição de malhas alternativas, bem como fornecendo subsídos para a avaliação dos impactos na malha oriundos da utilização de novas aeronaves. / This research proposes mathematical models and heuristics to define the flight mesh of an airline, as part of its operational planning, considering restrictions related to airports, equipment and demand. In particular, an objective function is formulated, based on transport momentum, proposed for the integrated modeling of Flight Scheduling and Fleet Assignment problems that includes specific elements to consider landing and takeoff slots at airports. The approach is especially relevant for small and medium airlines operating in regional markets, with short-haul flights, in general operating with small or medium size aircraft. Accordingly, these companies work with limited profit margins, and, therefore, they can take great benefit from a more efficient and effective flight mesh. The models proposed, based on integer linear programming and on the Ant Colony Optimization meta-heuristic, were successfully applied to the case of a regional airline with operations in Brazil, enabling the definition of mesh alternatives as well as providing information for the assessment of impacts in its flight network arising from the utilization of new aircraft.

O sucesso da mineração de opiniões para processar automaticamente grandes quantidades de conteúdo opinativo disponíveis na Internet tem sido demonstrado como uma solução de baixa latência e mais barata para a análise de opinião pública. No presente trabalho foi investigado se é possível prever variações de intenção de voto com base em séries temporais de sentimento extraídas de comentários de notícias, utilizando três eleições brasileiras como estudo de caso. As contribuições deste estudo de caso são: a) a comparação de duas abordagens para a mineração de opiniões em conteúdo gerado por usuários em português do Brasil; b) a proposta de dois tipos de atributos discriminantes para representar o sentimento em relação a candidatos políticos a serem usados para a previsão, c) uma abordagem para prever variações de intenção de voto que é adequada para cenários de dados esparsos. Foram desenvolvidos experimentos para avaliar a influência dos atributos discriminantes propostos em relação a acurácia da previsão, e suas respectivas preparações. Os resultados mostraram uma acurácia de 70% na previsão de variações de intenção de voto positivas e negativas. Estas contribuições são importantes passos em direção a um framework que é capaz de combinar opiniões de diversas fontes para encontrar a representatividade de uma população alvo, de modo que se possa obter previsões mais confiáveis. / The success of opinion mining for automatically processing vast amounts of opinionated content available on the Internet has been demonstrated as a less expensive and lower latency solution for gathering public opinion. In this work, we investigate whether it is possible to predict variations in vote intention based on sentiment time series extracted from news comments, using three Brazilian elections as case study. The contributions of this case study are: a) the comparison of two approaches for opinion mining in user-generated content in Brazilian Portuguese; b) the proposition of two types of features to represent sentiment behavior towards political candidates that can be used for prediction, c) an approach to predict polls vote intention variations that is adequate for scenarios of sparse data. We developed experiments to assess the influence on the forecasting accuracy of the proposed features, and their respective preparation. Our results display an accuracy of 70% in predicting positive and negative variations. These are important contributions towards a more general framework that is able to blend opinions from several different sources to find representativeness of the target population, and make more reliable predictions.

Made available in DSpace on 2017-05-12T14:47:14Z (GMT). No. of bitstreams: 1 Douglas Cezar Ebert.pdf: 309790 bytes, checksum: f0e2ece9bbf557060d09d5530f238727 (MD5) Previous issue date: 2007-07-17 / Slaughter and meat processing of poultries occur at the environment called poultry slaughter industry where are carried out unitary operations logically organized. According to Operations Research fundaments a poultry slaughter industry is characterized as system which is associated the following factors: (i) input variables example: daily number of poultries to be slaughtered; and daily schedules; (ii) system parameters example: processing rates and water and vapor availabilities; and (iii) output variables example: production quantities of meats and derivatives, fixed and variable costs, and waist volumes. In reason of the number of factors involved, and the fact of theses could be stochastic, it is hard to define mental scenarios to support decision processes. In reason of that, use of simulation technique is appropriate, because it permit to realize experiments such as: sensitivity analysis, scenario analysis, optimization, and Monte Carlo simulation. Therefore, this work was carried out with objective to develop a computational model, using the simulation language EXTENDTM to (a) simulate the dynamic of poultry slaughter industry; and (b) realize sensitivity analysis. Developed model was classified as dynamic, stochastic and discrete. The real system modeled is located in Paraná State at Southwest Region and has daily slaughter capacity of 500,000 poultries, using three processing lines and operating in three daily schedules. At model validation was obtained data related to three schedules that were slaughtered 174,239; 166,870 and 144,021 poultries, respectively. Output variables contrasted, considering data obtained from system and generated by model, were: (i) processing time; (i) total live weight (kg); (iii) available live weight (kg); (iv) sub product weight (kg); (v) total production weight (kg); (vi) whole slaughtered poultry weight (kg); and (vii) total slaughtered poultry part weight (kg). Sensitivity analysis carried out, by changes lines processing rates in 7,000; 8,000 and 9,000 poultries per hour, showed the following averages for processing time 8.69, 7.86 and 7.86 hours, respectively. Results demonstrate that for current situation, the increase of processing rates in 9,000 poultries h-1 does not imply in a directly decrease of processing time, because current frequency of cargos arrives can establish idle periods of poultry slaughter facility. / O abate de aves e o processamento da carne desenrolam-se no ambiente denominado matadouro-frigorífico em que são realizadas operações unitárias, lógicas e seqüenciadas. De acordo com os preceitos da Pesquisa Operacional, um matadouro-frigorífico é caracterizado como um sistema quando os fatores associados são: (i) variáveis de entrada - exemplos: número de aves abatidas diariamente e turnos de funcionamento; (ii) parâmetros do sistema, exemplos: velocidades das linhas de processamento e disponibilidades de água e vapor; e (iii) variáveis de saída - exemplos: volumes de produção de carnes e derivados, custos fixos e variáveis e volume de dejetos. Em razão do número de fatores envolvidos e, além disso, devido ao fato desses poderem ser estocásticos; tornase árdua a definição mental de cenários para fundamentação de tomadas de decisão. Perante essa situação, o uso da técnica de simulação é pertinente por propiciar a condução de experimentos tais como: análise de sensibilidade, comparação de cenários, otimização e simulação de Monte Carlo. Deste modo, o presente trabalho foi conduzido com o objetivo de implementar um modelo computacional, por meio da linguagem de simulação EXTENDTM, para: (a) simular a dinâmica de atividades de um matadouro-frigorífico de aves e (b) conduzir análises de sensibilidade. O modelo implementado foi classificado como dinâmico, estocástico e discreto. O sistema real modelado está localizado na Região Sudoeste do Paraná e tem capacidade diária de abate próxima a 500.000 aves, utilizando-se três linhas de processamento, com operação em três turnos de trabalho diários. Para validação do modelo, foram coletados dados relativos a três turnos, em que foram abatidas 174.239, 166.870 e 144.021 aves, respectivamente. As variáveis de saída comparadas, considerando os dados obtidos do sistema real e gerados pelo modelo, foram: (i) tempo de processamento; (ii) peso vivo total; (iii) peso vivo aproveitado; (iv) peso de subproduto; (v) peso produção total; (vi) peso frango inteiro; (vii) peso total cortes. O modelo apresentou-se aplicável, uma vez que os erros médios percentuais foram inferiores a 1% para as variáveis comparadas. Análises de sensibilidades, conduzidas mediante as alterações das velocidades de processamento das linhas em 7.000, 8.000 e 9.000 frangos h-1, apresentaram os seguintes valores médios para variável tempo de processamento: 8,69, 7,86 e 7,86 horas, respectivamente. Os resultados demonstram que, para a atual situação, o aumento da velocidade de processamento para 9.000 frangos h-1 não implicará diretamente na redução do tempo de processamento, pois, a cadência atual da chegada das cargas do campo pode estabelecer períodos de ociosidade do matadouro-frigorífico.

Submitted by camilla martins (camillasmmartins@gmail.com) on 2017-02-22T16:41:33Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_AlgoritmoGeneticoInteracao.pdf: 9371469 bytes, checksum: 3a41c7209c53c0ad6336c12038f01281 (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-02-23T11:41:16Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_AlgoritmoGeneticoInteracao.pdf: 9371469 bytes, checksum: 3a41c7209c53c0ad6336c12038f01281 (MD5) / Made available in DSpace on 2017-02-23T11:41:16Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_AlgoritmoGeneticoInteracao.pdf: 9371469 bytes, checksum: 3a41c7209c53c0ad6336c12038f01281 (MD5) Previous issue date: 2012-04-19 / Este trabalho apresenta um nova nova metaheurística híbrida e bioinspirada na natureza, baseada em três pilares fundamentais, que são: os Algoritmos Genéticos; a Teoria dos Jogos; e, a Lógica Nebulosa. Assim, o Algoritmo Genético com Interação Social Nebulosa, ou F-SIGA, é fundamentado e caracterizado por permitir aos indivíduos da população a possibilidade de participar do processo de Interação Social. Essa etapa é anterior ao processo de seleção para a geração dos descendentes, e nela eles podem obter ganhos através das disputas com outros indivíduos. Para isso, cada indivíduo é caracterizado por dois cromossomos, sendo um referente a solução do problema em questão; e, o outro, com a codificação genética da sua estratégia de comportamento. Como ambiente de disputas é utilizado o jogo Dilema do Prisioneiro, nas versões de 2-pessoas e N-pessoas, inclusive com a abordagem nebulosa. Além disso, os indivíduos são avaliados por uma função de fitness que engloba: a representação da solução do problema, os ganhos obtidos nas disputas e, ainda, o Fator de Experiència, que utiliza da experiência adquirida pelo indivíduo também como componente para auxiliar no processo evolutivo da população. Esta característica deu origem ao algoritmo ESIA – não previsto inicialmente – onde apenas as informações obtidas nas Interações Sociais são consideradas na seleção dos indivíduos para a etapa de reprodução. Metodologicamente, o trabalho evoluiu para o surgimento do algoritmo ESIA, que é uma nova classe de Algoritmos Evolucionários baseados em Interação Social. Sendo assim, este trabalho apresenta quatro algoritmos: o SIGA, o NpSIGA, o F-SIGA e o ESIA, com suas fundamentações teóricas e, também, resultados práticos ao aplicá-los à problemas de otimização global, com e sem restrições; e, à instâncias do Problema do Caixeiro Viajante. / This work presents a new new hybrid metaheuristic and bioinspired in nature, based on three main pillars, namely: Genetic Algorithms; Game Theory; and Fuzzy Logic. Thus, the Fuzzy Social Interaction Genetic Algorithm , or F-SIGA, is based and characterized by allowing individuals in the population the possibility to participate in the Social Interaction process. This step is prior to the selection process for the generation of offspring, and in it they can make gains through disputes with other individuals. For this, each individual is characterized by two chromosomes, one related to solving the problem in question; and, the other, with the gene encoding a behavioral strategy. As disputes environment is used the Prisoner's Dilemma game, in 2-person and N-person versions, including the fuzzy approach. In addition, individuals are evaluated by a fitness function that includes: a representation of the problem´ solution, the gains made in disputes and also the experience factor, using the experience acquired by the individual as well as a component to assist in the evolving process of the population. This characteristic gave rise to the ESIA algorithm - not originally planned - where only the information obtained from social interactions are considered in the selection of individuals for reproduction stage. Methodologically, the work evolved into the emergence of the ESIA algorithm, which is a new class of Evolutionary Algorithms based on social interaction. Thus, this work presents four algorithms: SIGA, NpSIGA, F-SIGA and ESIA, with its theoretical foundations and also practical results of applying them to global optimization problems with and without constraints; and the instances of the Travelling Salesman Problem.

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.

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.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-02-27Bitstream added on 2014-06-13T19:47:35Z : No. of bitstreams: 1 santos_smpg_me_sjrp.pdf: 975189 bytes, checksum: 365d7872dbad44341fdaa7290f787b15 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos o processo produtivo de uma fábrica de móveis característica do Pólo Moveleiro de Votuporanga/SP e propomos um modelo de otimização inteira mista para o processo de produção desta fábrica acoplando o Problema de Dimensionamento de Lotes (PDL) com o Problema de Corte de Estoque (PCE) Bidimensional. O modelo considera vários itens (produtos finais), horizonte rolante de planejamento, sendo que somente o período inicial é programado detalhadamente em relação às restrições de atendimento à demanda por peças e de capacidade das máquinas. Dois conjuntos de padrões de corte são utilizados, aqueles preferidos pela empresa e um conjunto de padrões tabuleiros compostos, e visa a utilização da capacidade total de corte da máquina seccionadora. Testes computacionais fazendo várias comparações foram realizados e mostram a eficiência da abordagem quando o problema é resolvido de forma integrada e quando o conjunto de padrões de corte tabuleiros compostos é utilizado. / In this work we studied the production process of a furniture company located in Votuporanga/SP and we propose a mixed-integer optimization model for the furniture industry production process, integrating the Lot Sizing Problem with the Cutting Stock Problem. The mathematical model considers multi items (final products) in a rolling horizon basis, where only the initial period is detailed with respect to the pieces demanded and capacity machines constraints. Two cutting pattern sets are used, the industry preferred cutting patterns and a set of composed checkerboard patterns, and aims at using the total capacity of the saw machine use. Computational tests with multiple comparisons show the approach effectiveness when the problem is solved in an integrated form and when the composed checkerboard patterns set is used.