Orientador: Jorge Stolfi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-11-01T12:54:45Z (GMT). No. of bitstreams: 1 Rosi_RoberMarcone_M.pdf: 3761476 bytes, checksum: b4531d082767a3cfb532a9610fb88352 (MD5) Previous issue date: 1995 / Resumo: Um complexo celular bidimensional é uma subdivisão de uma superfície num número fi­nito de elementos - faces (discos abertos), arestas (curvas abertas) e vértices (pontos). Descreve-se aqui um programa que, dada apenas a estrutura topológica de um complexo celular (ou seja, as relações de incidência e adjacência entre seus elementos), determina uma representação geométrica do mesmo (uma superfície subdividida), que é "bonita" e permite visualizar facilmente a topologia do complexo / Abstract: A two-dimensional cell complex is a partition of a surface into a finite number of elements faces (open discs), edges (open curves) and vertices (points). Here, is described a program which given only the topological structure of a cell complex (that is, the incidence and adjacency relationships between its elements), constructs a geometric representation of it - a subdivided surface - which is "nice looking" and allows one to clearly visualize the topology of the complex / Mestrado / Mestre em Ciência da Computação

Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-21T08:33:25Z (GMT). No. of bitstreams: 1 Scheidt_JoaoEduardoCardoso_M.pdf: 2581014 bytes, checksum: c1f985e905d424059b556edf8774af28 (MD5) Previous issue date: 1996 / Resumo: Túneis de congelamento são equipamentos utilizados pela industria alimentícia para o condicionamento térmico de produto tais como iogurte, sorvete, leite, carne e derivados. Assim, geralmente estão no fim do processo de produção de produtos altamente perecíveis. Quando um túnel representa m gargalo do processo, ele causa transtornos à produção que podem até interrompê-la. Este trabalho visa a abordagem do problema de operação eficiente e túneis de congelamento quanto ao aspecto de carregamento. Primeiramente abordamos o problema estático e suas relaxações e restrições. No problema estático determinístico, o instante de chegada das bandejas de produtos e o tempo de exposição necessário para seu condicionamento são conhecidos de antemão. Deve-se, então, programar por completo o carregamento do refrigerador definindo, para cada bandeja, em que nível do túnel deve ser colocada ou se deve ser rejeitada. Resultados teóricos são obtidos, particularmente para o caso (relaxado) do refrigerador de gavetas. Várias possibilidades de abordagem do problema estático são discutidas. Em seguida abordamos o problema dinâmico, onde não se dispõe do conhecimento prévio dos parâmetros de cada bandeja. Estes só ficam definidos a partir da chegada de cada bandeja, quando então a decisão quanto ao carregamento ou rejeição da bandeja deve ser tomada. Para o problema dinâmico são apresentadas várias políticas, que são testadas num caso real e em cenários hipotéticos nele baseados. Para avaliação de desempenho das políticas usamos limites' inferiores calculados com base no desenvolvimento teórico do problema estático. Os resultados são muito satisfatórios para uma classe de políticas a que chamamos de encadeamento. / Abstract: Freezing tunnels are food industry facilities for conditioning of meat, ice-cream, milk, yogurt, etc. They are very unwished botlenecks because they are positioned at the end of the production process of highly perishable items (low in-process inventory). The freezing tunnel loading problem is that of maximizing its production in terms of the amount of frozen trays of products. The purpose of this study is to model this problem and develop methods for solving its static and dynamic versions. In the static problem, the arrival time and the conditioning time of each tray are known in advance for the entire loading period. One should then completely schedule the loading of the tunnel. Each tray must be assigned to a position in the tunnel or be rejected. . We discuss several approaches and show some theoretical results for relaxed problems. In the dynamic problem, the arrival and the demand of trays are not known in advance. In this case, the decisions must take place at the arrival times. Several policies are developed. Some real case based scenarios are used for testing the policies. The study shows the potential gains with the application of some policies, mainly those ofthe class we named 'chain policies'. / Mestrado / Mestre em Matemática Aplicada

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

Orientador : Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T19:54:03Z (GMT). No. of bitstreams: 1 Rodrigues_MaikolMagalhaes_M.pdf: 4069676 bytes, checksum: b0b8e4bc9cdbe5bfc3fb90f34a46b43e (MD5) Previous issue date: 2001 / Resumo: Este trabalho de mestrado procurou estudar e resolver o problema de planejamento de viagens de linhas de ônibus da região metropolitana de São Paulo. Para tanto foi proposta uma ferramenta computacional capaz de gerar automaticamente as programações de viagens para uma linha de ônibus urbano. A programação de viagens tem um grande impacto não só na qualidade do serviço prestado aos passageiros da linha mas também no custo operacional das empresas de transporte. Portanto, o problema aqui estudado é de grande relevância prática e social. Os dados de entrada incluem uma curva com a demanda horária de passageiros da linha e um conjunto de restrições operacionais relativas à frota e aos funcionários. Na saída, deve-se produzir uma tabela com os horários das viagens além da escala de serviço completa dos carros e dos funcionários que irão operar na linha. Os algoritmos propostos por essa dissertação concentram-se no desenvolvimento de heurísticas baseadas em modelos de Programação Linear Inteira para resolver o problema de programação de viagens. Estes algoritmos foram implementados como parte de uma ferramenta computacional e os resultados são comparados com as soluções adotadas atualmente pelas empresas de transportes urbano. A análise dos resultados computacionais mostra que é possível obter reduções substanciais nos custos da operação sem que com isso haja uma redução na qualidade de serviço / Abstract: This dissertation aimed at studying and solving a real world trip planning problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of São Paulo, in Brazil. In this work we present a software that automatically generates a planning for the trips of a urban bus line. The trip planning has an enormous impact not only on the quality of the service offered to the passengers but also on the operational cost of the transportation companies. Therefore, the problem tackled here is of great importance for practical and social reasons. The input data includes the hourly demand of passengers and a set of operational constraints related to the vehicles and the employees. In the output, the trip time table as well as the vehicle and the crew schedules are produced. All the proposed algorithms in this work focus on the design of heuristics based on Integer Linear Programming models for the problem. The algorithms are implemented as part of a software whose results are compared with the solutions adopted in the bus companies nowadays. The analysis of our experiments indicates that it was possible to achieve a substantial cost reduction without loss in the quality of service / Mestrado / Mestre em Ciência da Computação

Orientador: Eduardo Candido Xavier / Dissertação (mestrado) - Universidade Estadual de Campinas, Insituto de Computação / Made available in DSpace on 2018-08-17T16:49:45Z (GMT). No. of bitstreams: 1 DelValle_AlineMarques_M.pdf: 1217777 bytes, checksum: 66f10d1b6b4533727cbe82431f97660d (MD5) Previous issue date: 2010 / Resumo: Nesta dissertação, estudamos problemas de empacotamento com itens irregulares. Estamos particularmente interessados no Problema da Mochila Bidimensional: dados um recipiente de tamanho W x H e uma lista de itens bidimensionais, o objetivo é empacotar um subconjunto dos itens de forma a maximizar a área dos itens empacotados. Existem diversos trabalhos que lidam com problemas para itens e recipientes bidimensionais com forma regular (retangular). No entanto, são poucos os estudos que tratam de itens com formas irregulares. Nós propomos algoritmos de empacotamento para itens irregulares em recipientes limitados baseados no uso de No-Fit-Polygon (NFP). Este trabalho apresenta uma heurística GRASP para a versão restrita do Problema da Mochila: uma solução inicial gulosa é gerada e, em seguida, utiliza-se um algoritmo de busca local para melhorar solução atual. Uma estratégia híbrida também foi proposta para versão irrestrita do Problema da Mochila. Ela divide-se em passos de empacotamento de itens irregulares e empacotamento de itens regulares. Testamos os algoritmos com instâncias adaptadas do problema de Strip Packing. O GRASP obteve empacotamentos ótimos para várias instancias testadas e, mesmo para as instâncias em que o algoritmo não obteve resultados ótimos, os empacotamentos obtidos tiveram boa taxa de ocupação, com valores relativamente próximos do ótimo. O tempo de execução do algoritmo foi razoável. Na estratégia híbrida, obtiveram-se empacotamentos bons para a maioria das instâncias, com taxa de ocupação acima de 90% e tempos de execução relativamente baixos / Abstract: In this work, we study packing problems dealing with two dimensional irregular items. We are particularly interested in the knapsack version of the problem: given a container with size W x H and a list of two dimensional items, the goal is to pack a subset of items such that the total area of packed items is maximized. There are several works that deal with problems for the case where items and containers have regular shapes (rectangular). However, only a few studies deal with items with irregular shapes. We propose algorithms for packing irregular items in limited containers based on the use of No-Fit-Polygon (NFP). This work presents a GRASP algorithm for the restricted version of the Knapsack Problem: first, a greedy initial solution is generated, then, the local search algorithm is used to improve the current solution. A hybrid strategy has also been proposed for the unrestricted version of the Knapsack Problem. It is divided into steps of packing irregular items and packing regular items. We tested the algorithms using adapted instances for the Strip Packing problem. The GRASP algorithm achieved optimal packings for several of the tested instances, and, even for those that the algorithm did not, the obtained packings had a good occupancy rate, with values relatively close to the optimum. The runtime of the algorithm was reasonable. In the hybrid strategy, we obtained good packings for most of the instances, with occupancy rates above 90% and relatively low execution times / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

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-21T16:19:09Z (GMT). No. of bitstreams: 1 Yamashita_DeniseSato_M.pdf: 17113576 bytes, checksum: 521aa681cb74631854ad49e388dd8145 (MD5) Previous issue date: 1996 / Resumo: Esta dissertação trata de problema de programar n tarefas em m máquinas paralelas idênticas, com o objetivo de minimizar o atraso médio em relação às datas de entrega. Para resolver o problema, propõe-se uma aplicação de busca tabu e duas estratégias de diversificação. O desempenho das heurísticas foi comparado através de testes computacionais gerados para 900 problemas. Foram realizados testes envolvendo até 10 máquinas e 150 tarefas. Para 540 problemas os resultados são comparados com limitantes inferiores gerados por relaxação lagrangeana. Em mais 65% desses problemas, os resultados dos métodos propostos chegaram a menos de 1% do limitante inferior / Abstract: This thesis deals with the problem of scheduling n jobs on m parallel identical machines with the objective of minimizing the mean tardiness. In order to solve this problem, it is proposed a tabu search approach and two diversification strategies. The performance of the heuristics was measured by computacional tests for 900 problems. The tests were made in instances with up to 10 machines and 150 jobs. For 540 problems, the results are compared with lower bounds given by a lagragian relaxation. In more than 65% of these problems, the results of the proposed method are within 1% of the lower bounds. within 1% of the lower bounds / Mestrado / Mestre em Engenharia Elétrica

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T14:02:44Z (GMT). No. of bitstreams: 1 Santos_RafaelFranciscodos_M.pdf: 909075 bytes, checksum: b4d466696cb4f640a50eca288dfccd5c (MD5) Previous issue date: 2006 / Resumo: Nesta dissertação propomos um uso mais geral dos Cortes Canônicos (CCs) introduzidos por Balas e Jeroslow ([2]) no método de Ramificação Local (RamLoc) de Fischetti e Lodi ([6]). A ramificação local é uma heurística de propósito geral para Programação Inteira Mista (MIP) que explora vizinhanças definidas através da adição de inequações lineares ao modelo original. Estas inequações determinam subproblemas que são computados mais rapidamente pelos resolvedores de MIP. Uma análise da execução da RamLoc indicou que, em algumas situações, ela acrescenta cortes de ramificação local muito superficiais (i.e.,que descartam poucas soluções) e que estes cortes ocorrem com grande freqüência. Como os cortes de ramificações locais de Fischetti e Lodi são casos especiais dos CCs para programação inteira 0?1, n'os propomos a incorporação de CCs mais profundos (i.e.,que descartam mais soluções) à RamLoc. Executamos o algoritmo resultante sobre 25 das 29 instâncias testadas em [6] e obtivemos melhores resultados do aqueles alcançado pela RamLoc original e pelo resolvedor comercial de MIP XPRESS com seus parâmetros default. Uma outra investigação que empreendemos foi a inclusão dos CCs na heurística para modelos gerais de programação inteira mista RINS ([3]). Esta heurística surgiu durante o desenvolvimento desta dissertação e apresentou um bom desempenho. Realizamos alguns testes com as mesmas instâncias sobre as quais a RamLoc foi executada e obtivemos resultados promissores. Por fim, além da utilização dos CCs em heurísticas, criamos uma estratégia de ramificação que pode ser embutida nos algoritmos de branch-and-cut dos resolvedores de MIP. Denominamos esta estratégia de dive branching e a implementamos no resolvedor XPRESS. Em experimentos conduzidos com o mesmo conjunto de instâncias anteriores, obtivemos resultados de melhor qualidade do que aqueles produzidos pelo XPRESS com seus parâmetros default / Abstract: In this dissertation we propose a broader usage of the Canonical Cuts (CC) introduced by Balas and Jeroslow ([2]) in the Local Branching method (LB) of Fischetti and Lodi ([6]). The LB is a general purpose heuristic for Mixed Integer Programming (MIP) that explores neighborhoods defined by the addition of linear inequalities to the original model. These inequalities determine subproblems that are computed more quickly by MIP solvers. An analysis of the execution of LB indicated that, in some situations, it adds local branching cuts that are too superficial (i.e., chopping off few solutions) and that these cuts happen very often. Since the local branching cuts of Fischetti and Lodi are special cases of CCs for 0?1 integer programming, we propose to incorporate deeper CCs (i.e, chopping of more solutions) to LB. We executed the resulting algorithm on 25 out of the 29 instances tested in [6] and we obtained better results than those attained by the original LB and by the XPRESS commercial MIP solver under default settings. Another research that we carried out was the inclusion of CC to the RINS heuristics for general mixed integer programs ([3]). This heuristic appeared during the development of this dissertation and showed a good performance. We carried out some tests with the same instances on which LB was tested and the results are promising. Finally, besides using the CCs in heuristics, we created a branching strategy that can be embedded to the branch-and-cut algorithms of the MIP solvers. We called it dive branching and implemented it in the XPRESS solver. In experiments with the same set of instances as before, we obtained results of better quality than those produced by XPRESS with default settings / Mestrado / Mestre em Ciência da Computação

Orientador: Heloisa Vieira da Rocha / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:49:36Z (GMT). No. of bitstreams: 1 Tanaka_EduardoHideki_D.pdf: 5276780 bytes, checksum: 5d96841bbaebe2f4b4e18694a8a7c807 (MD5) Previous issue date: 2009 / Resumo: Para ser mais inclusivo e menos exclusivo, o design de sistemas de informação deve considerar questões de acessibilidade. Atualmente, existem padrões para orientar o design acessível e, também, alguns métodos para avaliação de acessibilidade, voltados principalmente para conteúdo na Web. Dos métodos de avaliação de acessibilidade existentes, os mais adotados hoje em dia são aqueles baseados na verificação de conformidade com guias de design acessível e os testes com usuários com deficiências. Tanto um quanto o outro podem ser considerados métodos caros e que demandam um tempo considerável para aplicação e análise, sendo esta uma das razões para que muitos desenvolvedores simplesmente ignorem a avaliação da acessibilidade durante o ciclo de desenvolvimento de software. Sabendo disto, esta tese de doutorado propõe exatamente um método alternativo para avaliar a acessibilidade em sistemas de informação, baseado em heurísticas. Os resultados obtidos através de dois experimentos mostraram que as heurísticas de acessibilidade propostas são fáceis de aprender, rápidas de aplicar e de baixo custo, o que possibilita sua aplicação a qualquer momento do processo de desenvolvimento de um software / Abstract: To be more inclusive and less exclusive, the design of information systems must take into account accessibility issues. Nowadays, there are standards to guide the accessible design and, also, some accessibility evaluation methods, focused on the assessment of Web content, mainly. From all accessibility evaluation methods available, the most adopted nowadays are guidelines review and tests with users with disabilities. Both of them can be considered expensive methods and require a reasonable time to apply and to analyze so that several developers simply ignore accessibility evaluation during the software development cycle. Knowing these issues, this PhD thesis proposes an alternative method to evaluate accessibility, based on heuristics. The results of two experiments showed that the proposed accessibility heuristics are easy to learn, fast to apply and not expensive, therefore, it could be applied anytime during the software development cycle / Doutorado / Sistemas de Informação / Doutor em Ciência da Computação

Orientador: Antonio Carlos Moretti / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T22:48:39Z (GMT). No. of bitstreams: 1 DalGallo_RodrigoMarchiori_M.pdf: 685835 bytes, checksum: 9e0e8765da2a5926a7a5952b31283ca5 (MD5) Previous issue date: 2008 / Resumo: O trabalho tem como objetivo a implementação de um método heurístico para a resolução de problemas de programação inteira com dimensão completa. Nos atemos aos problemas de corte e empacotamento, mas a aplicação pode ser estendida a qualquer outro problema dessa classe. No problema de programação linear relaxado aplicamos o Método de Gilmore & Gomory e a partir da solução contínua obtida através do método simplex, aplicamos o método heurístico e comparamos os resultados com as soluções exatas obtidas a partir de Branch & Bound / Abstract: The objective of this dissertation is the implementation of a heuristic method to solve integer linear programming problems with complete dimension. We worked specifically with cutting and stock problems, but it can be aplied to any other class of integer problems. We used the Gilmore & Gomory method of column generation and starting by the continuous solution obtained with simplex method, we aplied the heuristic method and made a comparation of results with the exact solutions obtained by the Branch&Bound method / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada