Orientadores: Pedro Sergio de Souza, Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T06:12:54Z (GMT). No. of bitstreams: 1 Ribeiro_WesleyElias_M.pdf: 3030614 bytes, checksum: 36a45d851a8415069c93b66b7f8b80da (MD5) Previous issue date: 1997 / Resumo: Esta dissertação trata do Problema do Caixeiro Viajante Coletor de Prêmios (Prize Collecting Traveling Salesman Problem-PCTSP). Este problema é uma generalização do bastante conhecido Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP), em que o caixeiro viajante não precisa visitar, necessariamente, todas as cidades, mas um número suficiente delas para a obtenção de um prêmio mínimo. Além disso, sua função objetivo é dada pela minimização do comprimento da rota adicionada às penalidades pagas por cidades não visitadas. A formulação do PCTSP foi feita com base em uma aplicação prática do problema, o escalonamento de equipamentos em uma indústria siderúrgica. O presente trabalho apresenta um estudo de algoritmos heurísticos disponíveis na literatura do problema. São, então, apresentadas novas heurísticas de construção e melhoria de soluções desenvolvidas para o PCTSP, e é efetuada uma comparação com o algoritmo de melhor garantia de desempenho encontrado na literatura. Este trabalho também compreende o desenvolvimento de um Time Assíncrono para o PCTSP. Times Assíncronos compreendem uma abordagem meta-heurística já aplicada com sucesso a diversos outros problemas de Otimização Combinatória. Seu princípio básico é a combinação sinérgica de diversos algoritmos (agentes), comunicando-se através de memórias compartilhadas. O Time Assíncrono foi implementado de forma distribuída, utilizando-se o pacote PVM (Parallel Virtual Machine), baseado em troca de mensagens. Para os testes foram geradas aleatoriamente diversas instâncias de tamanhos variados, e, para efeito de comparação, foram obtidos limites inferiores para estas instâncias utilizando-se o pacote de programação linear/inteira Cplex, aplicado a relaxações do problema desenvolvidas / Abstract: This dissertation deals with the Prize Collecting Traveling Salesman Problem (PCTSP). This problem is a generalization of the well-known Traveling Salesman Problem (TSP), where the salesman does not need to visit all the cities, but has to visit enough cities in order to obtain a minimum prize. Besides that, the objective function is given by the minimization of the tour lenght plus the penalties paid for unvisited cities. The formulation of the PCTSP was made based on a pratical application of the problem, the scheduling of production units in a steel plant. The present work presents a study of the heuristic algorithms available in the literature about the problem. It then shows new construction and improvement heuristics developed for the PCTSP, and presents a comparison between those new heuristics and the best performance guarantee algorithm found in the literature. This work also presents a Asynchronous Team developed for the PCTSP. Asynchronous Teams are a meta-heuristic approach already succesfully applied to many other Combinatorial Optimization problems. Its basic principle is the sinergic combination of many algorithms (agents), communicating through shared memories. The Asynchronous Team was implemented using distributed processing, by using the message-passing based PVM (Parallel Virtual Machine) package. Many instances of different sizes were randomically generated, and, for comparison, lower bounds for these instances were calculated using the Cplex linear /integer programming package, applied to relaxations of the problem / Mestrado / Mestre em Ciência da Computação

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2017-08-23T12:56:44Z No. of bitstreams: 1 texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5) / Made available in DSpace on 2017-08-23T12:56:44Z (GMT). No. of bitstreams: 1 texto completo.pdf: 993417 bytes, checksum: af46bc7032d180cae6ecae3aaebec7c1 (MD5) Previous issue date: 2017-03-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Em um mundo que, em tempo acelerado, tem-se tornado cada vez mais necessitado em bens consumíveis e não consumíveis, a logística no transporte destes produtos tem sido colocada à prova, sendo uma das etapas mais importantes da relação entre o processo de produção e o usuário final. Cerca de um terço dos custos logísticos desta relação (produção-usuário) são determinados pelo custo de transporte dos bens, tornando essa operação muito importante. Um novo problem surgiu a partir de um entrave encontrado numa situação prática. O Problema do Roteamento de Veículos Duplo com Múltiplas Pilhas (DVRPMS) consiste em um Problema do Caixeiro Viajante com Múltiplas Pilhas (DTSPMS) com múltiplos veículos. Os dois problemas apareceram pela necessidade urgente em otimizar o transporte intermodal em um contexto europeu. Consiste em coletar pedidos em uma região de coleta e carregá-los num conjunto de pilhas dentro de um container, que não deve ser rearranjado por razões de segurança. O container então é levado a região de entrega e os itens são entregues seguindo a política das pilhas, em que os itens do topo, coletados por último, devem ser entregues primeiro. Nesta dissertação, quatro heurísticas baseadas na busca local iterativa (ILS), na descida em vizinhança variável (VND) e no recozimento simulado (SA) são propostas. O problema foi estendido para uma versão onde há uma oferta de itens maior do que a capacidade da frota de veículos. Um método exato é proposto juntamente com outras três heurísticas baseadas no ILS, SA e na busca tabu (TS). Os algoritmos propostos foram testados em experimentos computacionais e análises estatísticas foram feitas com intenção de encontrar a melhor combinação de parâmetros para estas heurísticas. Os resultados encontrados foram bons, tendo encontrado melhores médias que a literatura atual. / In a world, that in a fast pace, has become increasingly needed in consumable and nonconsumable goods, the logistics in the transportation of these products has been put to the test, being one of the most important stages in the relationship between the pro-duction process and the end user. It is said that at least 30% of the costs between the industry and the end user are solely determined by the cost of transportation. A novel problem arose followed by a question that was encountered in a real-life scenario. The Double Routing Vehicle Problem with Multiple Stacks (DVRPMS) consists in a Dou-ble Traveling Salesman Problem with Multiple Stacks (DTSPMS) with multiple vehicles. Both problems appeared for the urgent need of optimizing intermodal transportation in the european context. It consists in gathering costumer inquires from a pickup region and loading them in a set of stacks inside a container that must not be rearranged for security reasons. The container moves to a delivery region and the items gathered must be delivered according the last-in-first-out policy of the stacks. In this work, four heuristics were proposed based on the Iterated Local Search (ILS), Variable Neighborhood Descent and Simulated Annealing (SA) metaheuristics. The DVRPMS was extended to a modi-fied version where the items offered are bigger than the vehicle fleet capacities. An exact model approach is proposed and three other heuristics, based on the ILS, SA and Tabu Search are proposed and tested. The approaches presented in this work were tested by computational experiments and a statistical analysis was made to chose the best com-bination of parameters. Good results were found, providing a better average than the current literature.

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2016-04-26T17:01:30Z No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) / Made available in DSpace on 2016-04-26T17:01:30Z (GMT). No. of bitstreams: 1 texto completo.pdf: 6402016 bytes, checksum: 2ad43c5bb42a77cb19379857a960b47d (MD5) Previous issue date: 2015-12-08 / Fundação de Amparo à Pesquisa do Estado de Minas Gerais / O Problema do Caixeiro Viajante Preto e Branco (PCV-PB) é uma generalização do Problema do Caixeiro Viajante (PCV), definido sobre um grafo onde os vértices são classificados como pretos ou brancos. Assim como o clássico PCV, o objetivo do PCV-PB é encontrar um ciclo hamiltoniano de custo mínimo, entretanto, duas restrições adicionais são consideradas. Enquanto que a restrição de cardinalidade restringe o número de vértices brancos entre dois vértices pretos consecutivos, a restrição de comprimento restringe a distância máxima entre os mesmos. Apli- cações do PCV-PB podem ser observadas no escalonamento de aeronaves e em configurações de redes de telecomunicações. A proposta deste estudo é analisar diferentes estratégias heurísticas aplicadas para o PCV-PB. Heurísticas construtivas da literatura foram aperfeiçoadas e uma nova estratégia para a construção da solução foi apresentada. Neste contexto foi utilizado métodos como Lin kernighan e Inserção Específica de Brancos. Além disso, foram propostas abordagens heurísticas baseadas nas metaheurísticas GRASP, VND, ILS e SA. Diversos experimentos computacionais foram realizados para comparar a eficácia das abordagens. Os resultados garantem a aplicabilidade dos algoritmos propostos para o problema. / The Black and White Traveling Salesman Problem (TSP-BW) is a generalization of the Travelling Salesman Problem (TSP), set on a graph where the vertices are classified as black or white. As in the classical PCV, a solution of the TSP-BW is a Hamiltonian cycle of minimal cost. However, two additional constraints are considered. While the cardinality constraint limits the number of white vertices between two consecutive black vertices, the length constraint restricts the maximum distance therebetween. Applications of TSP-BW can be observed in aircraft scheduling and telecommunications network settings. The purpose of this study is to analyze different heuristic strategies applied to TSP-BW. Literature constructive heuristics have been improved and a new strategy for building the solution was presented. In this context it used methods such as Lin Kernighan and Inserção Específica de Brancos. Also, it has been proposed heuristic approaches based on metaheuristics GRASP, VND, ILS and SA. Several computational experiments were performed to compare effectiveness of approa- ches. The results ensure the applicability of the proposed algorithms to the problem.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-09T16:23:31Z No. of bitstreams: 1 texto completo.pdf: 700752 bytes, checksum: d8590a35a9faff6d372adf439ca649d6 (MD5) / Made available in DSpace on 2016-09-09T16:23:31Z (GMT). No. of bitstreams: 1 texto completo.pdf: 700752 bytes, checksum: d8590a35a9faff6d372adf439ca649d6 (MD5) Previous issue date: 2016-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação apresentamos métodos gulosos para a seleção de um subconjunto de funções heurísticas de um grande conjunto de possibilidades com o objetivo de reduzir o tempo de execução de algoritmos de busca. Trabalhos anteriores mostraram que a busca pode ser mais rápido se vários bancos de dados padrão menores são usados em vez de um grande banco de dados padrão. Nossos métodos são capazes de selecionar boas heurísticas de um grande conjunto de funções heurísticas para guiar uma A*. Implementamos nosso método em Fast Downward e mostrou empiricamente que produz heurísticas que superam o estado-da-arte de outros planejadores na Competição Internacional de Planejamento. / In this dissertation we present greedy methods for selecting a subset of heuristic functions from a large pool of possibilities with the objective of reducing the running time of search algorithms. Previous works showed that search can be faster if several smaller pattern databases are used instead of one large pattern database. Our methods are able to select good heuristics from a large set of heuristic functions to guide A* search. We implemented our method in Fast Downward and showed empirically that it produces heuristics which outperform the state-of-the-art planners in the International Planning Competition benchmarks. / Autor sem Lattes.

Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2014-11-07T16:35:24Z No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2014-11-07T16:52:21Z (GMT) No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) / Made available in DSpace on 2014-11-07T16:52:21Z (GMT). No. of bitstreams: 2 license_rdf: 20592 bytes, checksum: 0c9b9c579af4cbbcf785ca803bd18d4b (MD5) DISSERTAÇÃO_AlgoritmoBaseadoMetaheurística.pdf: 2705222 bytes, checksum: fd00f5395b864397a2989217cec92430 (MD5) Previous issue date: 2014 / Este trabalho trata um problema particular de planejamento de lavra de uma mineradora localizada no quadrilátero ferrífero do Estado de Minas Gerais, Brasil. Neste problema há um conjunto de frentes de lavra, um conjunto de equipamentos de carga de diferentes produtividades, um conjunto de caminhões de diferentes capacidades e um conjunto de pontos de descarga para o material lavrado. Cada frente de lavra é subdividida em blocos, os quais, por sua vez, são subdivididos em sub-blocos. Cada sub-bloco pode conter um dentre quatro tipos de material: hematita, canga, itabirito e estéril. Além disso, cada sub-bloco somente pode ser lavrado se os sub-blocos precedentes tiverem sido totalmente lavrados. A cada ponto de descarga está associada uma meta de produção e uma qualidade de material a ser atendida. O objetivo é determinar a alocação das carregadeiras aos blocos e o número de viagens que cada caminhão deve fazer a cada sub-bloco, saindo de um determinado ponto de descarga, de forma a atender as metas de produção e qualidade estabelecidas para cada descarga. Para resolvê-lo foi desenvolvido um algoritmo heurístico baseado nas metaheurísticas Greedy Randomized Adaptive Search Procedures (GRASP) e Late Acceptance Hill-Climbing (LAHC). O algoritmo explora o espaço de soluções usando busca locais autoadaptativas. Experimentos computacionais comparam os resultados do algoritmo proposto com aqueles do otimizador LINGO aplicado a um modelo de programação linear inteira mista e mostram a efetividade da proposta. ________________________________________________________________________________________________ / ABSTRACT: This work deals with a particular problem of mine planning at a mining company located in the Iron Quadrangle of Minas Gerais, Brazil. In this problem there is a set of pit mining, a set of loader equipment of different yields, a set of trucks of different capacities and a set of delivery points for the discharge of materials. Each pit is subdivided into blocks, which, in turn, are subdivided into sub-blocks. Each sub-block can contain one of four types of material: hematite, canga, itabirito and waste. Furthermore, each sub-block can only be drawn up if the preceding sub-blocks have been fully drawn up. Every point of discharge is associated with a production and quality targets of material to be answered. The objective is to determine the allocation of loaders to blocks and the number of trips that each truck must do for each sub-block, leaving a certain point of discharge in order to meet production and quality targets requirements for each discharge. A heuristic algorithm, based on the metaheuristics Greedy Randomized Adaptive Search Procedures and Late Acceptance Hill-Climbing, was developed in order to solve this problem. The algorithm explores the solution space using self-adaptive local search. Computational experiments compare the results of the proposed algorithm with those of the optimizer LINGO model applied to a mixed integer linear programming and show its effectiveness.

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e Computação / Made available in DSpace on 2018-07-21T18:54:37Z (GMT). No. of bitstreams: 1 Coelho_MarcoAntonioFreitasdoEgito_D.pdf: 7042998 bytes, checksum: 9bebcee2dc4b60902fd40a01d09293f9 (MD5) Previous issue date: 1996 / Resumo: Nesta tese novos métodos e procedimentos para resolver o problema de programação de tarefas em múltiplas máquinas paralelas com custos de atraso e adiantamento são propostos. As máquinas são não-relacionadas, a divisão de tarefas é permitida, as tarefas podem ter datas previstas de entrega diferentes e os tempos de preparação de máquina para executar uma tarefa depende da tarefa anterior processada na mesma máquina. Este é um problema novo, de dificil resolução e não foram encontradas referências na literatura especializada. Apesar disso, tem muitas possíveis aplicações na manufatura. O problema é formulado através de um modelo linear de programação inteira mista para o caso sem divisão de tarefas e, posteriormente,dois outros modelos lineares são propostos para o caso onde a divisão de tarefas é permitida. Como o problema de minimização foi mostrado ser NP-completo, os modelos podem apenas ser utilizados para resolver pequenos problemas de teste. A partir do modelo de programação inteira mista, um método de busca em árvore é desenvolvido para uso com procedimentos Branch & Bound e Busca em Feixe Filtrada. Dois limitantes inferiores são desenvolvidos para o Branch & Bound e quatro limitantes para a Busca em Feixe Filtrada. Algumas propriedades e teoremas do problema original e um método de decomposição eficiente para resolver o modelo linear derivado do modelo de programação inteira mista, também são apresentados. Muitos problemas de teste com até 120 tarefas e 6 máquinas são utilizados para mostrar o desempenho dos métodos desenvolvidos aqui / Abstract: In this thesis new methods and procedures to solve the multimachine scheduling problem with early and tardy costs are proposed. The machines are unrelated, job splitting is allowed, the jobs may have different due dates and the changeover time to process a new job on a machine depends on the job previously processed on the same machine. This problem is new, hard to solve and no references have been found in respecialized literature. However, it has many applications in the manufacturing. Two linear mixed-integer programming models one stated when job splitting is allowed, as well as similarmodel is proposed for the case without job splitting. Since the problem is NP-hard, the models can oniy be used to solve small test problems. Based on the mixed-integer formulation, a tree search method is developed to be used in a Branch & Bound and in a Filtered Beam Search procedures. Two lower bounds are developed for the Branch & Bound and four bounds for the Filtered Beam Search. Some properties of the original problem and an efficient decomposition method to solve the LP model derived from the mixed-integer problem are presented. Many test problems with up to 120 jobs and 6 machines has been used to show the performance of the proposed methods / Doutorado / Doutor em Engenharia Elétrica

Orientador: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-21T22:57:01Z (GMT). No. of bitstreams: 1 Romero_PedroReumay_D.pdf: 28889216 bytes, checksum: 68552bf6c60166542203ea3ee686b940 (MD5) Previous issue date: 1996 / Resumo: Neste trabalho definem-se características de programação horária de peças, e sua solução, como problema de otimização combinatorial. É proposto um modelo formal para sua representação em uma célula flexível de manufatura com base na teoria de programação matemática, onde é modelado como um problema de programação linear inteira misto com o objetivo de minimizar o tempo total de processamento. Apresenta-se também, as idéias básicas da teoria de conjuntos nebulosos e sua contribuição ao desenvolvimento de modelos de tomada de decisão. Obtém-se soluções aproximadas do problema usando a lógica nebulosa e a programação linear nebulosa ... Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: In this work, the workpieces scheduling problem is characterized and modeled as a combination optimization problem. A formal model for flexible manufacturing cell is presented, based on the mathematical programminf theory: a mixed integer programming model minimizing the total processing time. The basic concepts of fuzzy logic and fuzzy numbers and sets is roughly presented and their contributions to the decision making models development are enfatized, using fuzzy logic and fuzzy linear programming ... Note: The complete abstract is available with the full electronic digital thesis or dissertations / Doutorado / Doutor em Engenharia Elétrica

Orientador: Fernando Iguti / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-07-26T15:45:20Z (GMT). No. of bitstreams: 1 Clapis_AntonioPedro_D.pdf: 6280663 bytes, checksum: d33f59de18e79beebaf4d0bb0cbdcd98 (MD5) Previous issue date: 1999 / Resumo: Nos últimos trinta anos pesquisadores tem procurado desenvolver métodos matemáticos e ou numéricos, na busca de se otimizar a configuração geométrica de uma dada estrutura. Como a análise estrutural é uma parte integrante do processo de otimização de forma, o progresso da otimização estrutural muitas vezes depende fundamentalmente do desenvolvimento de um bom modelo de elementos finitos. Partindo-se então do pressuposto que a discretização do modelo geometricamente e fisicamente tem sentido, pode-se implementar um algoritmo iterativo de busca da forma ótima de um elemento estrutural utilizando-se um principio heurístico de desenvolvimento. Extrapola-se um método de homogeneização do erro de discretização por elementos finitos no domínio para a homogeneização da densidade de energia de deformação por distorção (von Mises) dos elementos, onde o critério de convergência é a máxima densidade de energia de distorção permitida. Um código numérico em linguagem Fortran F32 é implementado. O programa tem como principal característica a utilização de dois modelos estruturais com graus de liberdade bem distintos (modelo físico e modelo geométrico). No modelo geométrico efetua-se a relocação dos nós da discretização por elementos finitos tendo como objetivo a melhor homogeneização possível da densidade de energia de deformação por distorção do elemento. A avaliação da potencialidade do método é feita através da otimização de algumas estruturas citadas na literatura e, com os resultados obtidos verifica-se a eficiência e a razão de convergência do método proposto / Abstract: In the past thirty years researchers have sought to develop mathematical methods and/or numerical methods to optimize the geometric configuration of a structure. Since structural analysis is part of the process of shape optimization, this success in our approach depends on the development of an adequate finite element model. Assuming that the geometrical and physical discretization of the model is established, it is possible to implement an iterative algorithm to seek the optimal shape of a structural component using a heuristic principIe. A method the balancing the error of each element in the plane stress state is extrapolated. This method is used to balance the energy of distortion deformation function (von Mises) of each element and the criterion to stop is the maximum distortion energy function in the uniaxial tension testoA numerical code using Fortran F32 language is implemented. The main characteristic of this code is the execution of two distinct structural modules (physical and geometric model). In the geometric model the nodes are relocated considering the homogenization the distortion deformation energy density per element. The potentiality of the proposed method is evaluated through some examples ftom the literature. With the results the efficiency and the convergence of the method are checked. / Doutorado / Mecanica dos Solidos / Doutor em Engenharia Mecânica

Orientadores: Luis Gimeno Latre, Maria Teresa Moreira Rodrigues / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T13:12:34Z (GMT). No. of bitstreams: 1 Rodrigues_LuizCarlosdeAbreu_D.pdf: 13439549 bytes, checksum: d1bf6cf4e43207b899cd4a6e1a44b3d4 (MD5) Previous issue date: 2000 / Resumo: O problema tratado é o planejamento e programação (scheduling) da produção em plantas operando em batelada. Considera-se a situação em que são produzidos diversos produtos finais (planta multiproduto) através de vários estágios de produção (operações), e os processadores são multipropósito, podendo ser utilizados por diversas operações. O objetivo é o estudo de problemas da indústria de processos e, para tanto, são consideradas as restrições de armazenagem típicas desta área. O problema considerado é o chamado de curto prazo, no qual o objetivo do planejamento e scheduling da produção é o atendimento de demandas específicas de produtos finais em termos de quantidades e prazos de entrega. A abordagem proposta é de dois níveis. O nível de planejamento utiliza como dados de entrada a demanda de produtos finais, a disponibilidade de matérias primas e a atribuição de operações a processadores. Através de procedimentos de explosão, determinase a quantidade de bateladas de cada operação que serão produzidas e a janela de tempo onde deverá ocorrer o processamento de cada batelada. Utilizam-se técnicas de propagação de restrições para analisar o carregamento induzido aos processadores e a factibilidade do plano de produção. O caráter interativo do sistema permite ao usuário modificar os dados de entrada para obter uma situação factível. O resultado do planejamento, na forma de janelas de tempo, é utilizado no scheduling para reduzir a dimensão do problema. Utilizam-se duas abordagens: uma abordagem de programação linear inteira mista (MILP) utilizando discretização uniforme do tempo e a técnica de simulated annealing. A formulação MILP utiliza intensivamente a informação dada pelas janelas de tempo, reduzindo a quantidade de variáveis binárias envolvidas e propõe-se uma formulação reduzida que explora as informações de carregamento dos processadores. O algoritmo de simulated annealing é acrescido de um processo de filtragem dos candidatos que elimina os candidatos infactíveis, dadas as restrições de ordenamento induzidas pelas janelas de tempo / Abstract: The problem focused in this thesis is the short term planning and scheduling of multipurpose batch plants. This is an important problem in the process industry and, because of that, intermediate storage limitations are explicitly considered. The main objective is to fulfill specific demands of final products, distributed along the horizon. It is proposed a two level approach: planning and scheduling. Product' s demands, raw material availability plan and operation/equipment assignment are the inputs to the planning level. At this level an exploding procedure is performed in order to determine the number of batches of each operation as well as their processing time windows. Constraint propagation techniques are used to analyze the plant loading and the production plan feasibility. The interactive nature of the proposed approach allows the user to change input data in order to define a feasible scenario. At the end of the planning level, a set of operations' time windows is released to the scheduling level. Two approaches have been implemented to schedule the operations inside their time windows: a MILP approach based on a uniform time discretization and a simulated annealing approach. The information given by the time windows is intensively used in the MILP formulation, reducing the number of binary variables in the problem. It is also proposed a reduced MILP model exploiting plant loading information. The simulated annealing algorithm implemented also uses the time windows information to eliminate infeasible candidates through a filtering procedure / Doutorado / Doutor em Engenharia Elétrica

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-14T08:51:37Z (GMT). No. of bitstreams: 1 Assis_LauraSilvade_M.pdf: 1632808 bytes, checksum: dfd28dc2bbd2bb5fe453a2fb1c2b7b6e (MD5) Previous issue date: 2009 / Resumo: O objetivo desta dissertação é desenvolver uma metodologia eficiente para solucionar o problema de agrupamento capacitado multicritério (PACM), no qual objetos com pesos associados são dados, os quais devem ser particionados em agrupamentos com capacidade limitada. Neste trabalho, o PACM está ambientado em um problema de reagrupamento de lotes urbanos, nos quais devem ser realizadas as leituras dos medidores de energia elétrica por concessionárias de distribuição de energia. A operação de leitura dos medidores é realizada sobre lotes geograficamente definidos e é desempenhada sobre rotas percorridas uma vez por mês pelos leituristas. A motivação deste trabalho é atribuída ao fato de que, com o passar do tempo, o tamanho e o formato dos lotes vão ficando obsoletos, devido a modificações introduzidas na conformação atual, desarranjando o equilíbrio entre os lotes e desatualizando as rotas. Por esse motivo é importante realizar um reagrupamento dos lotes buscando a diminuição dos custos operacionais de leitura, assim como a minimização dos custos e transtornos causados pelas modificações. O método proposto para resolver o problema abordado nesta dissertação é um algoritmo baseado na metaheurística GRASP (Greedy randomized adaptive search procedure). A eficiência do método proposto é testada sobre uma série de instâncias geradas e sobre uma rede real. Os experimentos computacionais demonstram a eficiência do método. / Abstract: The aim of this dissertation is to develop an eficient methodology to solve the multicriteria redistricting capacitated problem (PACM), in which objects with associated weights are given, which must be partitioned into groups with limited capacity. In this work, the PACM is inserted in to a reassignment problem of urban clusters of clients, in which the readings of the eletric energy measurement must be performed by the company of energy distribution. The reading operation is performed over lots geographically defined is performed once a month by the readers. The motivation of this work is due to the fact that the size and shape of the lots become obsolete after some time, due to modifications introduced in the current conformation, desarranging the balance between the lots and outdating the routes. For this reason it is important to achieve a reassignment of the lots trying to decrease the operational costs of reading, as well as minimizing the costs and inconvenience caused by the changes. The proposed method to solve the problem addressed in this dissertation is a algorithm based on GRASP (Greedy randomized adaptive search procedure) metaheuristic. The efectiveness of the proposed method is tested on a large number of generated instances and on a real network. Computational experiments demonstrate the efectiveness of the proposed approach. / Mestrado / Automação / Mestre em Engenharia Elétrica