O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.

Orientador: Sergio Azevedo de Oliveira / Banca: Rubén Augusto Romero Lázaro / Banca: Antônio César Baleeiro Alves / Resumo: Neste trabalho propõe-se o desenvolvimento de uma interface gráfica voltada para a resolução do problema de planejamento da expansão das linhas de transmissão, que utiliza-se de programas para a obtenção das soluções ótimas ou de boas soluções. A grande dificuldade encontrada por usuários ao interagir com estes programas, motivou o desenvolvimento de uma aplicação com interface gráfica, a qual disponibiliza ao usuário diversas metodologias para a resolução do problema do planejamento da expansão das linhas de transmissão de energia elétrica. Espera-se que software como este, agregado ao sistema de ensino tradicional que normalmente 'e utilizado num curso de engenharia elétrica, possa fortalecer o processo de aprendizagem do aluno. Assim, o software educacional Transmission Expansion Planning (TEP 1.0) está sendo desenvolvido visando propiciar um ambiente agradável para a realização de simulações e testes e favorecer a aprendizagem dos conceitos que envolvem o problema do planejamento da expansão da transmissão. É possível através deste software fazer simulações para os sistemas: Garver (6 barras/ 15 ramos), Sul brasileiro (46 barras/79 ramos) e Norte-Nordeste brasileiro (87 barras/179 ramos). O software se beneficia de recursos oferecidos por programas que são executados em background, bem como da utilização de meta-heurísticas e do ambiente de processamento de máquinas paralelas virtuais, as quais podem ser selecionadas para realização dos testes em determinado sistema / Abstract: This work proposes the development of a computational tool aimed at solving the problem of the transmission expansion planning, which uses programs in the background to obtain optimal solutions or good solutions. The great difficulty for users to interact with these programs, motivated the development of an application with a graphical interface, which provides the user with various methodologies for solving the problem of expansion planning of transmission lines of electricity. It is expected that software like this, added to the traditional school system which is normally used in electrical engineering courses, can strengthen the process of student learning. Thus, the educational software Transmission Expansion Planning (TEP 1.0) is being developed to provide a pleasant environment for simulations and testing and promote the learning of concepts involving the issue of transmission expansion planning. It is possible using this software to do simulations for the systems: Garver (6 nodes / 15 branches), South Brazilian (46 nodes / 79 branches) and North-Northeast Brazilian (87 nodes / 179 branches). The software takes advantage of capabilities offered by programs that run on background, and using meta-heuristics and the processing environment, parallel virtual machine, which can be selected to test on a system / Mestre

O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

Made available in DSpace on 2014-06-11T19:22:32Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-11-20Bitstream added on 2014-06-13T18:08:26Z : No. of bitstreams: 1 proto_ab_me_ilha.pdf: 2777482 bytes, checksum: ac3152da7c340dcf6ab04c187cabe418 (MD5) / Neste trabalho propõe-se o desenvolvimento de uma interface gráfica voltada para a resolução do problema de planejamento da expansão das linhas de transmissão, que utiliza-se de programas para a obtenção das soluções ótimas ou de boas soluções. A grande dificuldade encontrada por usuários ao interagir com estes programas, motivou o desenvolvimento de uma aplicação com interface gráfica, a qual disponibiliza ao usuário diversas metodologias para a resolução do problema do planejamento da expansão das linhas de transmissão de energia elétrica. Espera-se que software como este, agregado ao sistema de ensino tradicional que normalmente ´e utilizado num curso de engenharia elétrica, possa fortalecer o processo de aprendizagem do aluno. Assim, o software educacional Transmission Expansion Planning (TEP 1.0) está sendo desenvolvido visando propiciar um ambiente agradável para a realização de simulações e testes e favorecer a aprendizagem dos conceitos que envolvem o problema do planejamento da expansão da transmissão. É possível através deste software fazer simulações para os sistemas: Garver (6 barras/ 15 ramos), Sul brasileiro (46 barras/79 ramos) e Norte-Nordeste brasileiro (87 barras/179 ramos). O software se beneficia de recursos oferecidos por programas que são executados em background, bem como da utilização de meta-heurísticas e do ambiente de processamento de máquinas paralelas virtuais, as quais podem ser selecionadas para realização dos testes em determinado sistema / This work proposes the development of a computational tool aimed at solving the problem of the transmission expansion planning, which uses programs in the background to obtain optimal solutions or good solutions. The great difficulty for users to interact with these programs, motivated the development of an application with a graphical interface, which provides the user with various methodologies for solving the problem of expansion planning of transmission lines of electricity. It is expected that software like this, added to the traditional school system which is normally used in electrical engineering courses, can strengthen the process of student learning. Thus, the educational software Transmission Expansion Planning (TEP 1.0) is being developed to provide a pleasant environment for simulations and testing and promote the learning of concepts involving the issue of transmission expansion planning. It is possible using this software to do simulations for the systems: Garver (6 nodes / 15 branches), South Brazilian (46 nodes / 79 branches) and North-Northeast Brazilian (87 nodes / 179 branches). The software takes advantage of capabilities offered by programs that run on background, and using meta-heuristics and the processing environment, parallel virtual machine, which can be selected to test on a system

Os processos industriais de produção exigem uma programação da produção efetiva. Essa atividade consiste da alocação dos recursos produtivos, a fim de executar tarefas determinadas por um período de tempo definido. Programar a produção é uma das atividades mais complexas do Planejamento da Produção, pois existem diferentes tipos de recursos a serem administrados simultaneamente. E também a quantidade de possíveis soluções aumenta exponencialmente com o aumento da quantidade de tarefas e máquinas presentes no sistema. A proposta deste trabalho é apresentar um método heurístico construtivo para a solução de problemas flow shop permutacional. A função-objetivo utilizada é a minimização do tempo total da programação (makespan). O algoritmo foi desenvolvido com base no melhor algoritmo construtivo presente na literatura, e os resultados obtidos são discutidos e analisados com base na porcentagem de sucesso, desvio relativo médio e tempo médio de computação. / Industrial productive processes demand an effective production scheduling. These activities consist in allocating the productive resources in order to execute determined jobs for a established period of time. Scheduling the production is one of the most complex activities involved in Planning the Production because there are different kinds of resources to be managed simultaneously. Furthermore, the amounts of feasible solutions increase exponentially as the number of jobs and machines in large systems. This dissertation presents a constructive heuristic method to solve the permutational flow shop problem. The evaluation criterion is the total production elapsed time (makespan). The developed algorithm was based on the best algorithm found in the literature, the results are analysed based on the success rate, mean relative deviation and computing time.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-01-06T14:13:40Z No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) / Approved for entry into archive by Diamantino Mayra (mayra.diamantino@ufjf.edu.br) on 2017-01-31T11:27:02Z (GMT) No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) / Made available in DSpace on 2017-01-31T11:27:02Z (GMT). No. of bitstreams: 1 isabelamirandademendonca.pdf: 2220110 bytes, checksum: 5dc0f4e3929098da2984e16872a06681 (MD5) Previous issue date: 2016-08-19 / Este trabalho apresenta uma nova estratégia visando à redução do espaço de busca e à inicialização do processo de otimização multimodal para resolução do problema de planejamento estático da expansão de sistemas de transmissão de energia elétrica. Para tanto, a metodologia proposta faz uso de um algoritmo heurístico construtivo baseado em índices de sensibilidade, no qual as decisões de expansão são relaxadas e representadas através da função tangente hiperbólica. Através da consideração de diferentes inclinações da função tangente hiperbólica, dentro de um intervalo previamente determinado, associadas aos principais índices de sensibilidade existentes na literatura é possível extrair um conjunto reduzido de alternativas de expansão. Sendo assim, com base nas informações heurísticas obtidas, é utilizado um algoritmo bioinspirado visando obter de um plano final de expansão para sistemas de transmissão de energia elétrica. A rede de transmissão de energia elétrica é representada por um modelo linearizado de fluxo de carga. Os planos finais de expansão obtidos pela metodologia proposta foram satisfatórios, mostrando que a utilização da função tangente hiperbólica agregada às heurísticas adotadas resultaram em uma estratégia eficiente de decisão. Foram analisados os sistemas Garver, IEEE 24 barras, Sul Brasileiro de 46 barras, e o Colombiano de 93 barras. Os resultados obtidos pela a metodologia proposta foram satisfatórios e de excelente qualidade. / This thesis presents a new strategy aimed at the search space reduction and initialization of the multimodal optimization process to solve the problem of static expansion planning of electric power transmission systems. The proposed methodology uses a constructive heuristic algorithm based on sensitivity indices, in which the expansion decisions are relaxed and represented through the hyperbolic tangent function. By considering different slopes of the hyperbolic tangent function, within a predetermined range, associated with the main existing sensitivity indices in the literature, it is possible to extract a reduced set of expansion alternatives. Thus, based on the heuristic information obtained, a bio-inspired algorithm is used to obtain a final expansion plan for electric power transmission systems. The electric power transmission network is represented by a linear load flow. The final expansion plans obtained by the proposed methodology were satisfactory, showing that the use of the hyperbolic tangent function added to the adopted heuristics yielded an effective decision strategy. The Garver system, IEEE 24 bus system, real equivalent system in southern Brazil 46 bus and real Colombian system 93 bus were analyzed. The results obtained by the proposed method were satisfactory with excellent quality.

O problema de programação de operações em ambiente no-wait flow shop tem sido abordado desde a década de 60. Por se tratar de um ambiente em que as tarefas devem ser processadas continuamente e sem interrupções entre uma máquina e outra, um tempo de espera entre o início da tarefa anterior e o início da tarefa atual deve ser determinado na primeira máquina. Neste sentido, uma vez que a tarefa inicia seu processamento, as máquinas devem estar disponíveis para que atendam a restrição de no-wait. Portanto, operações de manutenção preventiva são necessárias para que a programação seja atendida sem maiores problemas. Este trabalho aborda dois problemas: no-wait flow shop e no-wait flow shop com operações de manutenção preventiva. O critério de desempenho adotado foi a duração total da programação (makespan). Por meio de uma revisão de literatura, mecanismos de construção de soluções foram identificadas e classificadas e, baseando-se em tais, novos métodos heurísticos construtivos simples e compostos foram propostos para o problema no-wait flow shop e uma heurística composta foi desenvolvida considerando as operações de manutenção preventiva. Experimentações computacionais para os dois problemas foram realizadas para fins de comparação e avaliação dos métodos propostos com os métodos heurísticos construtivos da literatura. Para o problema Fm|no - wait|Cmax resultados evidenciaram que as heurísticas propostas H4GPSLLS e MH4GPSLLS superaram as heurísticas da literatura em qualidade de solução, com diferença estatisticamente significativa no nível de 5% de significância. Para o problema Fm|no - wait, m(k)|Cmax, pode-se constatar que a heurística BIHLS e as heurísticas H4GPSLLS e MH4GPSLLS apresentaram desempenho superior com diferença estatística significativa no nível de 5% de significância em comparação as heurísticas da literatura. / The no-wait flow shop scheduling problem has been studied since 60\'s. In this environment, jobs must be processed continuously without interruption between one machine and another, and because of this, a delay between the start time of the previous job and the start time of the current job must be determined in the first machine. In this sense, since a job starts its processing, the machines must be available to respect the no-wait constraint. Therefore, preventive maintenance operations are needed. This work adresses two problems: the m machine no-wait flow shop and the m machine no-wait flow shop with preventive maintenance operations. The performance measure adopted was the makespan. By means of a literature review, mechanisms of solution construction were identified and classified. New simple and composite constructive heuristics were proposed to the no-wait flow shop problem and a new composite constructive heuristic was developed considering the preventive maintenance operations. Computational experiments and their respective analyses for both problems were carried out to compare and evaluate the performance between the proposed methods and the constructive heuristics of the literature. Regarding Fm|no - wait|Cmax problem, results show that the proposed heuristics H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature in quality of the solution and is statistically significative to 5% of significance level. To the Fm|no - wait, m(k)|Cmax problem it can be seen that the proposed heuristic BIHLS and H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature and is statistically better to 5% of significance level.

O problema de programação de operações em ambiente no-wait flow shop tem sido abordado desde a década de 60. Por se tratar de um ambiente em que as tarefas devem ser processadas continuamente e sem interrupções entre uma máquina e outra, um tempo de espera entre o início da tarefa anterior e o início da tarefa atual deve ser determinado na primeira máquina. Neste sentido, uma vez que a tarefa inicia seu processamento, as máquinas devem estar disponíveis para que atendam a restrição de no-wait. Portanto, operações de manutenção preventiva são necessárias para que a programação seja atendida sem maiores problemas. Este trabalho aborda dois problemas: no-wait flow shop e no-wait flow shop com operações de manutenção preventiva. O critério de desempenho adotado foi a duração total da programação (makespan). Por meio de uma revisão de literatura, mecanismos de construção de soluções foram identificadas e classificadas e, baseando-se em tais, novos métodos heurísticos construtivos simples e compostos foram propostos para o problema no-wait flow shop e uma heurística composta foi desenvolvida considerando as operações de manutenção preventiva. Experimentações computacionais para os dois problemas foram realizadas para fins de comparação e avaliação dos métodos propostos com os métodos heurísticos construtivos da literatura. Para o problema Fm|no - wait|Cmax resultados evidenciaram que as heurísticas propostas H4GPSLLS e MH4GPSLLS superaram as heurísticas da literatura em qualidade de solução, com diferença estatisticamente significativa no nível de 5% de significância. Para o problema Fm|no - wait, m(k)|Cmax, pode-se constatar que a heurística BIHLS e as heurísticas H4GPSLLS e MH4GPSLLS apresentaram desempenho superior com diferença estatística significativa no nível de 5% de significância em comparação as heurísticas da literatura. / The no-wait flow shop scheduling problem has been studied since 60\'s. In this environment, jobs must be processed continuously without interruption between one machine and another, and because of this, a delay between the start time of the previous job and the start time of the current job must be determined in the first machine. In this sense, since a job starts its processing, the machines must be available to respect the no-wait constraint. Therefore, preventive maintenance operations are needed. This work adresses two problems: the m machine no-wait flow shop and the m machine no-wait flow shop with preventive maintenance operations. The performance measure adopted was the makespan. By means of a literature review, mechanisms of solution construction were identified and classified. New simple and composite constructive heuristics were proposed to the no-wait flow shop problem and a new composite constructive heuristic was developed considering the preventive maintenance operations. Computational experiments and their respective analyses for both problems were carried out to compare and evaluate the performance between the proposed methods and the constructive heuristics of the literature. Regarding Fm|no - wait|Cmax problem, results show that the proposed heuristics H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature in quality of the solution and is statistically significative to 5% of significance level. To the Fm|no - wait, m(k)|Cmax problem it can be seen that the proposed heuristic BIHLS and H4GPSLLS and MH4GPSLLS outperformed the heuristics of the literature and is statistically better to 5% of significance level.

Made available in DSpace on 2017-07-10T17:11:48Z (GMT). No. of bitstreams: 1 Dissertacao Willian Douglas F Mendonca.pdf: 2130607 bytes, checksum: ef5e681d6a8d26e8c6fe5324e3cf0c03 (MD5) Previous issue date: 2014-07-04 / In this Master's Dissertation is presented the development of a specialized algorithm for planning the expansion of pole networks of distribution systems. The technique used for solution is the Constructive Heuristics that has been used together with mathematical optimization models to solve the problem. However the presented algorithm does not employ a mathematical optimization model, in other words, a model compound of objective function and constraints. So, instead of working with variables, we seek to work with parameters, with the objective of providing greater speed to the research process, simplifying the search process for the final topology always keeping committed to finding a solution of good quality. Despite not having a guarantee that the solution is the global optimum, the solutions obtained by this type of algorithm solutions are almost always of excellent quality and can be used as a starting point for algorithms that use techniques or more complex mathematical models. To assist the Constructive Heuristic Algorithm in the search for the final topology is used a specialized routine for the calculation of AC power flow The methodology used by the subroutine for these calculations is based on the Backward Forward Sweep algorithm. / No presente trabalho é apresentado o desenvolvimento de um algoritmo especializado para o planejamento da expansão de redes aéreas de sistemas de distribuição. A técnica utilizada para solução é a Heurística Construtiva que tem sido utilizada em conjunto com modelos matemáticos de otimização para resolver o problema. No entanto o algoritmo apresentado não emprega um modelo matemático de otimização, em outras palavras, um modelo composto de função objetivo e restrições. Assim, em vez de trabalhar com variáveis, procura-se trabalhar com parâmetros, com o objetivo de proporcionar uma maior velocidade ao processo de pesquisa, simplificando o processo de busca para a topologia final sempre buscando manter o compromisso de encontrar uma solução de boa qualidade. Apesar de não ter a garantia de que a solução seja a ótima global, as soluções obtidas por este tipo de algoritmo são quase sempre soluções de excelente qualidade e podem ser usadas como ponto de partida para os algoritmos que usam técnicas ou modelos matemáticos mais complexos. Para auxiliar o Algoritmo Heurístico Construtivo na busca para a topologia final é usada uma rotina especializada para o cálculo do fluxo de potência CA. A metodologia utilizada pela subrotina para estes cálculos está baseada no algoritmo de varredura Backward Forward Sweep.