Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T07:54:32Z (GMT). No. of bitstreams: 1 Mazzini_Renata_D.pdf: 12936662 bytes, checksum: 581f180b73d247423b83bd197041667d (MD5) Previous issue date: 1998 / Resumo: Neste trabalho estuda-se a aplicação de meta-heurísticas populacionais em problemas de programação da produção. O problema abordado consiste da minimização do atraso total na programação de tarefas em máquinas paralelas idênticas onde se consideram tempos de preparação de máquina dependentes da seqüência de processamento e datas de entregas distintas. São apresentadas duas implementações de Algoritmos Genéticos e quatro implementações de Busca por Espalhamento. Testes computacionais extensos foram realizados com essas implementações sobre um conjunto de problemas gerados aleatoriamente. Os resultados obtidos possibilitaram a realização de análises comparativas do desempenho e do comportamento das versões implementadas dessas duas meta-heurísticas quando aplicadas ao problema de programação da produção estudado / Abstract: The application of population-based meta-heuristics on scheduling problems is studied in this work. The problem which is addressed is the minimization of total tardiness when jobs are scheduled on identical parallel machines with sequence dependent set-up times and distinct due dates. Two implementations of Genetic Algorithms and four implementations of Scatter Search are presented. These implementations were extensively tested over a set of randomly generated problems. The obtained results were used to compare the performance and the behavior of the implemented versions of these two meta-heuristics when applied to the scheduling problem studied. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T09:04:57Z (GMT). No. of bitstreams: 1 Peixoto_HelvioPereira_M.pdf: 4847864 bytes, checksum: 5c12c6f491a25c85cdd5a524c7aa92e8 (MD5) Previous issue date: 1995 / Resumo: Times Assíncronos perfazem uma nova técnica de resolução aproximada de problemas, baseada na utilização simultânea de diversos algoritmos heurísticos, que cooperam entre si de maneira sinérgica, encontrando soluções ótimas ou quase ótimas, as quais não seriam encontradas pelos mesmos algoritmos quando executados isoladamente. Esta nova técnica tem sido aplicada com sucesso a problemas combinatórios de grande porte. O tema central deste trabalho é o desenvolvimento de uma metodologia de especificação de TImes Assíncronos, em particular para os problemas de Otimização Combinatória de uma única função objetivo, tendo em vista a não existência de trabalhos neste sentido. O objetivo é fornecer uma seqüência de passos e sugestões que venham a facilitar e agilizar a concepção e implementação de Times Assíncrono&. Como um exemplo de aplicação da metodologia proposta, abordou-se o problema clássico de escalonamento de tarefas Flow Shop Problem de permutação, para o qual foram especificados e implementados Times Assíncronos. Os resultados obtidos por esses Times Assíncronos sobre as instâncias testadas foram tão bons quanto ou superiores às melhores soluções conhecidas. Esses testes foram efetuados de forma paralela, mostrando uma aceleração linear na obtenção dos resultados, conforme o número de processadores utilizados. Além dos Times Assíncronos para o Flow Shop Problem, desenvolveram-se novas fórmulas para cálculo de limites inferiores, demonstrando, assim, a otimalidade de algumas soluções obtidas e melhorando os limites inferiores conhecidos de dezenas de outras instâncias. / Abstract: Asynchronous Teams (A-Teams) are a new problem resolution technique that uses simultaneously various heuristic algorithms. These algorithms cooperate synergically one with the other to find optimal or nearly optimal solutions that would not be found through isolated algorithms. This technique has been successfully applied to large combinatorial problems. The main objective of this work is the development of a methodology to specify Asynchronous Teams to Combinatorial Optimization Problems with one objective function, since there is no literature about that. The purpose is to generate a sequence of steps and suggestions making the conception and implementation of Asyncbronous Teams easy and quick. As an example of the proposed methodology, Asynchronous Teams were specified and implemented to the classical permutation Flow Shop Problem. The results obtained by these A- Teams over the tested instances were equivalent or better than those published as the best known values. These A- Teams were executed in a parallel computer, showing linear speed up in the number of processors. Not on1y were the A- Teams to FSP developed, but do were two new formulas to calculate lower bounds. These lower bounds proved the optimally of two instances and improved the lower bounds of many others. / Mestrado / Mestre em Ciência da Computação

Orientador: Pedro Sergio de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-20T09:57:07Z (GMT). No. of bitstreams: 1 Cavalcante_VictorFernandes_M.pdf: 2124078 bytes, checksum: 931a0a025284734a0bdaf335669442c5 (MD5) Previous issue date: 1995 / Resumo: Times Assíncronos consistem numa nova técnica para solução aproximada de problemas que tem sido aplicada com sucesso a problemas de Otimização Combinatória. Esta técnica faz uso de diversos algoritmos heurísticos que cooperam entre si e conseguem encontrar soluções que não seriam encontradas pelos mesmos algoritmos quando executados isoladamente. Este trabalho tem como objetivo averiguar a adequabilidade de Tunes Assíncronos como metodolqgia para solução do problema de escalonamento de tarefas conhecido por Job Shop Scheduling Problem (JSP). Este problema é considerado um dos mais complexos dentro da Otimização Combinatória e tem recebido crescente atenção nas últimas décadas devido, principalmante, à sua aplicabilidade a processos industriais. Especificamente, o cerne do presente trabalho foi a elaboração de TImes A"síncronos centrados fundamentalmente em heurísticas de construção para oJob Shop Scheduling Problem. Foram concebidas e testadas novas heurísticas para o ISP e novos fluxos de dados que podem ser facilmente acoplados à arquitetura de um Time Assíncrono. Os Times Assíncronos desenvolvidos foram submetidos a diversas instâncias do JSP. Os bons resultados obtidos, não somente atestaram a viabilidade da nova técnica como ferramenta para solução do ISP, como revelaram a competitividade destes resultados com aqueles produzidos por outros métodos aproximados para o problema. / Abstract: Asynchronous Teams (or A-Teams) are a new problem resolution technique that has been succesfully applied to Combinatorial Optimization problems. This technique uses several heurisJic algorithms that cooperate simultaneously with each other and find solutions that would not be found through isolated algorithms. The objective of this work is to verify the suitability of Asynchronous Teams methodology solving the combinatorial problem known by Job Shop Scheduling Problem (JSP). This problem has been appointed as one of the most complex problem of Combinatorial Optimization and has been received special attention due to your industrial applicability. Specifically, the kemel of this work was the implementation of A-Teams based on construction heuristics for the Job Shop Scheduling Problem. New heurisncs for the JSP were developed and new data flows that can be easily incorporated in an A-Team architecture were elaborated.. Several JSP instances were used to test the A-Teams developed.. The good results obtained by these A-Teams not onIy showed the feasibility of such technique solving the JSP, but also revealed that this results are competitive with others one obtained by good aproximated approachs for the JSP. / Mestrado / Mestre em Ciência da Computação

Orientadores : Vinicius Amaral Armentano, Alistair Richard Clark / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-18T08:58:03Z (GMT). No. of bitstreams: 1 Carvalho_Adrianode_M.pdf: 4522560 bytes, checksum: 83bffed54a6d717a70da083f9511e293 (MD5) Previous issue date: 1993 / Resumo: Neste trabalho considera-se o problema multi-estágio de dimensionamento de lotes com horizonte rolante de planejamento para sistemas de produção do tipo Material Requirements Planning. Heurísticas para sistemas de montagem são generalizadas para sistemas com estrutura geral, e a seguir comparadas sob condições estáticas e de horizonte rolante. Além disso, são lmplementadas e comparadas técnicas para redução de instabilidade dos planos de produção. Experimentos computacionais são apresentados e analisados / Abstract: This work considers the multi-stage lot-sizing problem with Tolling planning horizon for use in Material Requirements Planning production systems. Heuristic methods for assembly systems are generalized for general structure systems and then compared under static and rolling planning horizon conditions. Moreover, techniques for dealing with nervousness of production plans are implemented and compared. Computacional experiments are reported and analysed. / Mestrado / Mestre em Engenharia Elétrica

Orientador : Luiz Roberto Monzani / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Filosofia e Ciencias Humanas / Made available in DSpace on 2018-07-18T10:13:25Z (GMT). No. of bitstreams: 1 Milidoni_CarmenBeatriz_D.pdf: 89130710 bytes, checksum: 95bb8ae68a4f08995034c3d0cd52a3e7 (MD5) Previous issue date: 1993 / Resumo: Não informado / Abstract: Not informed. / Doutorado / Doutor em Filosofia

O Problema de Minimização do Número Máximo de Pilhas Abertas (MOSP, do inglês minimization of open stacks problem) é um problema de otimização combinatória da família NP-Difícil que vem recebendo grande atenção na literatura especializada. Este trabalho apresenta novas contribuições em termos de modelos e técnicas de resolução para o problema. A primeira parte deste trabalho lidou com modelos matemáticos, sendo analisados os modelos existentes que se baseiam em programação inteira mista. Variações de um modelo da literatura foram propostas, com o objetivo de tentar diminuir o tempo de execução necessário para se obter uma solução exata com a utilização de pacotes comerciais. Os resultados mostraram que as propostas são capazes de acelerar a solução de algumas classes de instâncias mas, que de maneira geral, métodos baseados em relaxação linear encontram dificuldade em provar a otimalidade devido à baixa qualidade dos limitantes inferiores. Uma outra contribuição deste trabalho foi o desenvolvimento de um modelo conjunto para o problema MOSP e para o problema de minimização da duração de pedidos (MORP, do inglês minimization of order spread problem). Este modelo propõe um framework unificado em que os dois problemas podem ser resolvidos ao mesmo tempo, tendo suas funções objetivo individuais ponderadas através de pesos definidos pelo usuário. A segunda parte do trabalho voltou-se para o desenvolvimento de métodos heurísticos para o MOSP. Duas estratégias de solução foram desenvolvidas. O primeiro método propõe uma transformação heurística entre o problema MOSP e o clássico problema do caixeiro viajente (TSP, do inglês traveling salesman problem). A partir de uma representação em grafo do MOSP, o TSP é definido por meio de uma regra de atribuição de distâncias baseadas nos graus dos nós. Nos testes computacionais, a estratégia proposta mostrou-se eficiente em relação às heurísticas específicas para o MOSP, obtendo a solução ótima do MOSP em 80,42% das instâncias testadas e sendo competitiva em termos de tempo computacional com algumas das melhores heurísticas da literatura. O segundo método heurístico proposto utilizou a ideia de decomposição. De fato, neste método, um corte no grafo associado ao problema original divide-o em problemas menores, que são resolvidos. A solução global é obtida através da junção das soluções dos subproblemas e, em alguns casos, é possível demonstrar a otimalidade da solução obtida. Testes computacionais indicam a validade da proposta e apontam caminhos para pesquisas futuras / The minimization of open stacks problem (MOSP) is a well known NP-hard combinatorial optimization problem that has been extensively discussed in the specialized literature. This study presents some new contributions in terms of models and solution methods for this problem. The first part of this thesis dealt with mathematical models. The existing mixedinteger models have been analyzed and variants of a well known model have been proposed, with the goal of reducing the time needed by commercial packages to obtain proved-optimal solutions. The results of computational tests on a widely used set of instances have indicated that the modifications proposed are able to reduce the time needed to obtain optimal solutions for some classes of instances. Nevertheless, a conclusion has been the fact that mixed-integer programming models have difficulty in obtaining convergence due to the low quality linear relaxation bounds. Another contribution of this thesis is the proposal of a single model that is able to deal with both the MOSP and with the Minimization of Order Spread Problem (MORP). This unified framework allows both problems to be jointly solved, by using a weighted objective function that included both original objectives. The second part of this thesis dealt with the development of heuristic strategies. Two solution strategies have been proposed. The first method proposes a heuristic conversion between MOSP and Traveling Salesman Problem (TSP) instances. This conversion relies the assignment distances to the TSP instance based on the degree of the vertices of the associated MOSP graph. Computational tests have shown that the proposed methodology is efficient, both in terms of solution quality (optimal solutions were obtained for 80.42% of the tested instances) and computational effort. The second method uses a decomposition idea. A cut is made in the graph associated with the original MOSP problem, yielding two smaller problems, which are solved. In some cases, the obtained combined solution can be prover optimal. Computational tests have shown the validity of the proposal and indicate new research opportunities

Los tableros losa de hormigón pretensado son una tipología habitualmente empleada en España para resolver estructuras de pasos superiores. Su optimización presenta un gran interés para conseguir diseños más económicos, que permitan un mayor aprovechamiento de los recursos que requieren. Las contribuciones a esta materia son escasas y han adolecido de un carácter extemadamente teórico que ha dificultado su aplicación por parte de ingenieros proyectistas. El objetivo de este trabajo ha sido el de aplicar técnicas de optimización estructural a esta tipología. Se han empleado técnicas metaheurísticas, puesto que permiten plantear el problema de un modo más complejo, aprovechando par una definición completa de tablero y de todos sus componentes, al tiempo que ha permitido imponer todas las comprobaciones que la normativa exige para este tipo de estructuras. Para definir las características del problema ha sido necesario distinguir entre los tableros aligerados y los macizos, dado que ha resultado imposible considerar a uno un caso particular del otro. Se ha implementado un programa informático que incluye las siguientes funciones: generación aletatoria de un tablero, comprobación automática de un tablero, evaluación de su coste a partir de las mediciones completas de todos sus componentes y tres algoritmos de optimización heurística implementados basados en tres metaheurísticas, pertenecientes a los denominados algoritmos de mejora local. Para la calibración de los algoritmos se han efectuado pruebas con diferentes parametrizaciones. La comparación de los resultados ha permitido descartar el algoritmo OBA pormostrar una menor eficacia para las parametrizaciones ensayadas. Los algoritmos SA y TA, por el contrario, muestran resultados muy similares, por lo que han efectuado pruebas de inferencia estadística consistentes en diferentes test de hipótesis. Los resultados no han sido capaces de determinar la heurística más eficaz de las dos. / Alcalá González, J. (2010). Optimización heurística económica de tableros de puentes losa pretensados [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/7441 / Palancia

Presenta una propuesta del uso de dos metaheurísticas: optimización basada en colonia de hormigas y metaheurística golosa, los que permitirán la generación automática de casos de prueba para test sobre una GUI (Graphical User Interface) con el objetivo de que sean aplicados al producto final (pruebas funcionales) y detecten en qué puntos el producto no cumple sus especificaciones. Esto facilitará a las empresas de software la modificación de algún artefacto o componente del sistema por cambios en el negocio, y la generación de nuevos casos de prueba asociados al cambio realizado. / Tesis

Orientador: Carlos Alberto Bandeira Guimarães / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-19T08:42:56Z (GMT). No. of bitstreams: 1 Vecchini_DaltonCherubim_M.pdf: 2675188 bytes, checksum: c6d42c6c743a4bf310db50ca2ef591df (MD5) Previous issue date: 2011 / Resumo: Os problemas dinâmicos de roteirização de veículos com janela de tempo (DVRPTW), derivados dos clássicos problemas de roteirização de veículos (VRP), são conhecidos e estudados há muito tempo. Devido ao barateamento das tecnologias de comunicação, de mapas digitais, a computadores mais rápidos e a sua relevância no dia a dia das empresas de transporte, o interesse da comunidade científica em solucioná-los vem ganhando maior importância e atenção.Este trabalho estuda as características dos DVRPTW e os tipos de abordagem para sua solução.Posteriormente é estabelecida uma estratégia de abordagem e aplicada uma heurística a um caso prático extraído do levantamento em campo em uma empresa de transporte de carga seca e fracionada na cidade de São Paulo, com o objetivo de reduzir o tempo de atendimento das coletas dinâmicas. Finalmente são realizados comparativos entre a prática e o simulado focando na avaliação do tempo de atendimento, distância percorrida e tempo de processamento / Abstract: The problems of dynamic vehicle routing with time window (DVRPTW), derived from the classic vehicle routing problem (VRP), are well known and studied for a long time. Due to cheapening of communication technologies, digital maps, faster computers and its relevance in everyday transport companies, the scientific community's interest in solve them is gaining greater importance and attention. This study shows the characteristics of DVRPTW and the types of approach to its solution. Later it is established a strategy and implemented an heuristic approach to a practical case taken from the field survey in a business of transporting dry cargo and fractionated in São Paulo, aiming to reduce the handling time of dynamics pickups. Finally comparisons are made between the practice and simulated focusing on the evaluation of service time, distance and time processing / Mestrado / Transportes / Mestre em Engenharia Civil

No description available.