Submitted by MARCOS LEANDRO TEIXEIRA DE OLIVEIRA (marcosteixeira@ufv.br) on 2018-09-04T13:38:28Z No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) / Made available in DSpace on 2018-09-04T13:38:28Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1118685 bytes, checksum: 94e01364e7abc576bdbab9d4b54cd7cf (MD5) Previous issue date: 2018-01-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o Problema de Roteamento de Veículos para Coleta de Lixo com Janelas de Tempo (WCVRPTW), cujo objetivo é encontrar as rotas para os veículos coletores de lixo de modo que todos os clientes sejam plenamente atendidos e a distância total percorrida pelos veículos seja a menor possível, minimizando assim os custos de transporte. Para alcançar este objetivo é necessário que algumas restrições sejam atendidas: os clientes devem ser atendidos dentro de um período de tempo; existe horário de saída e retorno dos veículos ao depósito; os veículos possuem restrições de capacidade; as rotas possuem restrições de volume de carregamento e número de clientes atendidos; os veículos devem sair e retornar vazios ao depósito, e, quando cheios, devem ir para o aterro sanitário mais próximo para descarga do lixo. Além disso, os motoristas dos veículos devem realizar uma parada de almoço. O WCVRPTW é um problema real que pertence à classe NP-difícil. Para resolvê-lo, são desenvolvidos quatro algoritmos heurísticos: Simulated Annealing (SA), Tabu Search (TS), e dois algoritmos híbridos baseados nas metaheurísticas Iterated Local Search (ILS) e Variable Neighborhood Descent (VND), denominados ILS-VND e ILS-RVND. Os desempenhos dos algoritmos propostos são analisados em instâncias de pequeno e médio porte geradas para este trabalho, e também em instâncias de grande porte disponíveis na literatura. Os experimentos computacionais mostram que os algoritmos propostos são eficientes, competitivos e rápidos. / In this work we address The Waste Collection Vehicle Routing Problem with Time Windows (WCVRPTW), whose objective is to find the routes for garbage collection vehicles so that all customers are fully served and the total distance traveled by the vehicles is the smallest possible, thus minimizing transportation costs. In order to achieve this objective, some constraints must be satisfied: customers must be ser- ved within a period of time; there are departing and return times of the vehicles to the warehouse; vehicles have capacity constraints; the routes have loading volume constraints and number of customers served; the vehicles should leave and return empty to the depot, and when full should go to the nearest landfill for garbage disposal. In addition, drivers of the vehicles must have a lunch break. WCVRPTW is a real problem that belongs to the NP-hard class. In this work, to solve it, four heuristic algorithms are developed: Simulated Annealing (SA), Tabu Search (TS), and two hybrid methods based on the Iterated Local Search (ILS) and Varia- ble Neighborhood Descent (VND) metaheuristics, called ILS-VND and ILS-RVND. The performances of the proposed methods are analyzed in small and medium-sized instances generated in this work, and also in large instances available in the lite- rature. Computational experiments show that the proposed methods are efficient, competitive and fast.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-09-05T17:12:27Z No. of bitstreams: 1 texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5) / Made available in DSpace on 2018-09-05T17:12:27Z (GMT). No. of bitstreams: 1 texto completo.pdf: 804859 bytes, checksum: ed4ee44a672aa18b9e35cf4a363ab38a (MD5) Previous issue date: 2017-12-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda um problema de sequenciamento (scheduling) onde as tarefas são processadas em lotes em máquinas paralelas idênticas. Neste problema uma má- quina pode executar um conjunto (lote) de tarefas simultaneamente. Além disso, as tarefas são classificadas em famílias, onde uma família agrupa tarefas que possuam alguma característica em comum. Assim, os lotes devem conter somente tarefas de uma mesma família. O problema também considera tarefas com diferentes tempos de chegada (release times) e tempos de processamento. As tarefas possuem ainda uma data de entrega e uma prioridade. O problema consiste em determinar os lo- tes (grupos) de tarefas para serem sequenciados nas máquinas de tal maneira que o atraso total ponderado das tarefas seja minimizado. O problema envolvendo se- quenciamento de lotes, que é uma extensão do sequenciamento de tarefas clássico (onde uma máquina processa somente uma tarefa por vez), possui muitas aplicações reais, como em indústrias de fundição, de fabricação de móveis, de processamento de metais, de processamento de alimentos, farmacêuticas e de semicondutores. Para resolver o problema abordado, três algoritmos baseados em meta-heurísticas foram desenvolvidos: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) e Simulated Annealing (SA). Todos estes algoritmos utilizam técnicas de busca em vizinhança para melhorar a qualidade de uma solução. As meta-heurísticas ALNS, IG e SA possuem estruturas simples e elas têm sido aplicadas satisfatoriamente para resolver diferentes problemas de otimização combinatória, especialmente problemas de sequenciamento da produção, o que justifica a utilização para o problema em es- tudo. Experimentos computacionais, utilizando dados da literatura foram realizados a fim de avaliar o desempenho dos algoritmos. Os resultados são comparados com os resultados gerados por dois algoritmos da literatura (Memetic Algorithm e Variable Neighborhood Search) e com os resultados da resolução do modelo matemático do problema. Os experimentos e testes realizados demonstram que os algoritmos de- senvolvidos neste trabalho geram soluções válidas de excelente qualidade superando as melhores soluções apresentadas na literatura. / This work addresses a scheduling problem where the jobs are processed in batches on a identical parallel machines. In this problem a machine can process a set (batch) of jobs simultaneously. In addition, jobs are classified into families, where a family groups jobs that have some characteristic in common. Thus, the batches must con- tain only jobs of a same family. Also, the problem considers jobs with different release times and processing times. The jobs also have a due date and a priority. The objective of the problem is to group the job set into batches and assign the batches to the parallel machines in order to minimize the total weighted tardiness of the jobs. The parallel batch processing machines scheduling problem, that is an extension of classic job sequencing(where a machine processes only one task at a time) has many real application, such as in the foundry industry manufacturing, food processing industries, pharmaceutical industries and semiconductor industries. To solve this problem, three algorithms based on meta-heuristics were developed: Adaptive Large Neighborhood Search (ALNS), Iterated Greedy (IG) and Simula- ted Annealing (SA). All of these algorithms use neighborhood search techniques to improve the quality of solutions. In addition, the meta-heuristics ALNS, IG and SA have been applied satisfactorily to solve different combinatorial optimization problems. Computational experiments using literature data were performed to eva- luate the performance of the algorithms. The obtained results are compared with the results generated by two algorithms from the literature (Memetic Algorithm and Variable Neighborhood Search) and with the mathematical model of the problem. The computational experiments demonstrate that the algorithms developed in this work generate valid solutions of excellent quality, outperforming the best solutions presented in the literature.

Orientador: Fernando José Von Zuben / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T05:45:11Z (GMT). No. of bitstreams: 1 Mello_AlanGodoySouza_M.pdf: 2308252 bytes, checksum: f9e7cf4b923ecf59d07a767543b8a7c4 (MD5) Previous issue date: 2010 / Resumo: Este trabalho propõe uma variante de otimização por enxame de partículas, na qual as influências entre as partículas são definidas através de uma rede complexa dinâmica. O objetivo principal é melhorar a capacidade de exploração do mecanismo de busca, particularmente junto a problemas multimodais. Com a vizinhança entre as partículas sendo definida de forma dinâmica e apresentando propriedades típicas de redes complexas, pretende-se: (i) promover uma rápida difusão de informação pela rede; (ii) viabilizar a formação de comunidades; e (iii) permitir que a influência das partículas ao longo da busca seja ajustável. Para validar o algoritmo proposto, foi feita uma análise sobre qual sua sensibilidade à variação de características da topologia. Em seguida, o seu desempenho foi comparado ao de outras propostas de otimização por enxame de partículas, presentes na literatura, utilizando para isso sete funções de teste com alta dimensionalidade e diferentes graus de dificuldade. Os resultados obtidos mostraram-se competitivos, indicando que topologias dinâmicas e complexas conduzem a mecanismos de busca eficazes e flexíveis, capazes de lidar com diferentes cenários de otimização / Abstract: This work proposes a variant of particle swarm optimization, in which the influences among particles are defined by a dynamic complex network. The main purpose of this work is to improve the exploration capability of the search mechanism, particularly in multimodal problems. With the neighborhood of the particles being defined in a dynamic way and presenting typical properties of complex networks, the intention is: (i) to promote a rapid diffusion of information throughout the network; (ii) to enable the formation of communities; and (iii) to allow an adjustable influence of the particles along the search. To validate the proposed algorithm, an analysis of its sensitivity to alternative characteristics of the topology was performed. Further, its performance was compared to other particle swarm optimization proposals, available in the literature, on seven high-dimensional benchmark functions presenting distinct difficulty levels. The obtained results were competitive, indicating that dynamic complex topologies guide to effective and flexible search mechanisms, capable of dealing with distinct optimization scenarios / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

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: 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-07-21T20:24:03Z (GMT). No. of bitstreams: 1 MaqueraSosa_NelidaGladys_M.pdf: 3207129 bytes, checksum: d82f6742a78882c2faf1ce8aef31ccc1 (MD5) Previous issue date: 1996 / Resumo: As técnicas de agrupamento são aplicadas com diferentes finalidades e necessárias em muitos campos da ciência. No Problema de Agrupamento Capacitado (PAC) são dados objetos que possuem um peso associado que devem ser particionados em agrupamentos com capacidades limitadas. Apresentam-se quatro heurísticas de construção baseadas em pesos e distâncias dos objetos; uma heurística de melhoria que realiza inserções e permutações de objetos e uma aplicação de Busca Tabu (BT) simples. Além disso, é aplicado um mecanismo de abordagem adaptativa de horizonte arbitrário (HTA) baseado em BT que integra as fases de intensificação e diversificação durante a busca. Foram realizados testes computacionais mostrando que HTA obtém soluções de boa qualidade independentemente do ponto de partida e que algoritmos baseados em pesos .dos objetos têm melhor desempenho que algoritmos baseados em distâncias. Aplica-se a mesma metodologia ao Problema de Distritamento Político (PDP) que é um caso particular do PAC. É realizado um estudo preliminar de distritamento da cidade de Campinas dividindo-a em 10 distritos eleitorais. Estes resultados foram obtidos com aplicação da BT, mostrando que este problema pertencente às ciências políticas pode ser tratado pela programação matemática com erros mínimos / Abstract: Clustering techniques can be applied aiming different purposes with applications in severa! fields of science. In the Capacitated Clustering Problem (CCP) objects with distinct weights must be partitioned into clusters with limited capacity. It is presented four constructive heuristics that use weights and distances as optimization criteria. An improvement heuristic that performs insertions and interchanges of objects and a single Tabu Search (TS) application is also proposed. Moreover, it is applied an adaptive mechanism (HTA) based on TS which joins both intensifying and diversifying phases during the search. Computational tests show that HTA attains good quality solutions independent1y from the starting solution. They also show that a!gorithms based on object weights perform better than the ones based on distances. The same methodology is applied to a Political Districting Problem (PDP) which is a particular case of CCP. A preliminary study on the districting of Campinas city has shown that districting plans can be obtained with very reasonable errors / Mestrado / Mestre 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: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-23T02:02:04Z (GMT). No. of bitstreams: 1 Sacchi_LuisHenrique_M.pdf: 7567752 bytes, checksum: 7824c0b8e2f8e9bcfbc63ee5eb48371e (MD5) Previous issue date: 1997 / Resumo: Este trabalho aborda o problema de programação de tarefas no ambiente de produção ftow Shop flexível,também conhecido comoftow shop com máquinas paralelas. Algoritmos genéticos são utilizados para minimizar o tempo de processamento de todas as tarefas, isto é, o makespan. Implementações clássicas, baseadas em conhecimento e híbridas são apresentadas. Os algoritmos genéticos são comparados com as principais heurísticas da literatura e com um limitante inferior. Estratégias de busca local também são analisadas / Abstract: This work addresses the scheduling of jobs in a flexible flow shop or flow shop with parallel machines. The problem of minimizing the makespan is tackled by genetic algorithms. Classical, knowledge based and hybrid implementations are presented. The genetic algorithms are compared with the main heuristics from the literature and also with a lower bound. Local search strategies are also analysed. / Mestrado / Mestre 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

Orientador: Christiano Lyra Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-27T01:55:40Z (GMT). No. of bitstreams: 1 Bueno_EdilsonAparecido_M.pdf: 2749662 bytes, checksum: 4aed2eedc35e7de920f72fc065f5d3d7 (MD5) Previous issue date: 2000 / Resumo: Em sistemas de energia elétrica, continuamente ocorrem perdas, devido à resistência elétrica nas linhas e equipamentos. Estima-se que 7% de toda a energia elétrica gerada em sistemas de potência são perdidas, sendo 2% na transmissão e 5% na distribuição. O problema de minimização de perdas procura encontrar uma configuração da rede onde o montante das perdas seja reduzido. Este trabalho propõe um procedimento que combina técnicas para otimização de fluxos em redes com funções não lineares com o método GRASP para otimização combinatória. GRASP é um método iterativo que combina um método construtivo com busca local. Na fase de construção, cria uma solução viável, combinando uma função gulosa com seleção aleatória. Na fase de busca local, procura melhorar a solução. A estrutura da rede de distribuição de energia elétrica é usualmente radial. Inicialmente, relaxa-se a restrição de operação radial, encontrando-se uma solução otimista (limitante inferior) para o problema. Informações sobre os valores dos fluxos nos arcos da solução otimista são utilizadas para abrir chaves, guiando a fase de construção do método GRASP para encontrar soluções factíveis de boa qualidade. A busca local procura obter reduções adicionais de perdas através do método de troca de ramos. Estudos de casos ilustram as possibilidades da abordagem / Abstract: Energy is continuously dissipated in electric power systems due to electrical resistance in the lines and equipment. Losses amount to around 7% of total energy production, 2% in transmission and 5% in distribution. The problem of loss minimization tries to find a network configuration where the amount of losses is reduced. This work proposes a procedure that combines non-linear network flow optimization techniques with the GRASP method. GRASP is an iterative method that uses a combination of a constructive procedure with a local search. The construction phase obtains a feasible solution, combining a greedy function with a randomize selection. The local search tries to improve the solution. The structure of the electric power distribution network usually has a radial configuration. Initially, the constraint of radial operation is relaxed, meeting an optimistic solution (a lower bound) for the problem. Information from are flows in the optimistic solution are used to open switches, guiding the construction phase of GRASP to find feasible and good quality solutions. The local search tries to get additional reductions of losses through the branch-exchange procedure. Case studies iIIustrate the possibilities of the approach / Mestrado / Mestre em Engenharia Elétrica

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