Dado un conjunto de requerimientos lineales y un número ilimitado de barras de metal (u otro material) de tamaño estándar, con dimensión mayor a la de los requerimientos. El Problema de Cortes consiste en realizar cortes sobre las barras de tamaño estándar, de tal manera que se obtengan todos los requerimientos con el menor número de barras de tamaño estándar y el menor desperdicio posible. El problema es NP-Difícil, y presenta diversas aplicaciones en los diversos sectores de la industria, tales como la maderera, metal, plástico, etc. La presente Tesis, muestra un Procedimiento de Búsqueda Aleatoria, Adaptativa y Golosa (GRASP), para la resolución del problema de cortes. Experimentos numéricos realizados del algoritmo propuesto sobre 100 problemas-test, reportan una eficiencia, promedio del 95.4% para un parámetro de relajación de 0.5 y 2000 iteraciones. El software implementado consta de 4 módulos importantes: ingreso de datos necesarios para la realización de los cortes, Algoritmos Golosos FFD (First Fit Decreasing) y BFD (Best Fit Decreasing), GRASP y Reportes. / Given a group of lineal requirements and a limitless number of metal bars (or another material) of standard size, with more dimension to that of the requirements. The Cutting Stock Problem consists on carrying out courts on the bars of standard size, in such a way that all the requirements are obtained with the smallest number of bars of standard size and the minor waste possible. The problem is NP-hard, and it presents several applications in the different sectors of the industry, such as the lumberman, metal, plastic, etc. The present Thesis shows a Procedure of Random Search, Adaptive and Greedy to solve the Cutting Stock Problem. Carried out numeric experiments of the algorithm proposed on 100 problem-tests, they report efficiency, average of 95.4% for a parameter of relaxation of 0.5 and 2000 iterations. The implemented software consists of 4 important modules: entrance of necessary data for the realization of the cuts, Greedy Algorithms FFD (First Fit Decreasing) and BFD (Best Fit Decreasing), GRASP and Reports.

Definición de un grafo. Implementación de un grafo. Problemas resueltos con grafos. Algoritmos de la ruta más corta. Algoritmo de Dijkstra.

Algoritmo Ford Fulkerson para Flujo Máximo en un grafo.

Estructuras de datos de diccionario y técnica de memoization.

Tesis (Maestro en Ciencias, Especialidad en Sistemas Inteligentes) -- Tecnológico de Monterrey, Campus Monterrey. / Título tomado de la pantalla de presentación [como fue visto el 29 de agosto de 2006] Incluye referencias bibliográficas. También disponible en formato impreso.

Made available in DSpace on 2013-08-07T18:42:16Z (GMT). No. of bitstreams: 1 000418921-Texto+Completo-0.pdf: 1274519 bytes, checksum: 8981beef3de1308b9b81b49d455f1623 (MD5) Previous issue date: 2009 / An efficient distribution of tasks in computational grids has major challenges that have to be overcomed by a scheduling algorithm. These challenges are related to the characteristics of the environment, such, scalability, heterogeneity, dynamicity, among others. Most of the existing scheduling algorithms use information obtained from the environment or the replication of tasks in order to achieve a satisfactory performance in the execution of applications. Algorithms that rely on resource information to accomplish their task are restricted to environments in which such information is available and reliable all across the grid. On the other hand, algorithms that use replication could be used in any environment but they introduce a significant overhead to the scheduling. However, although reliable information is usually not available across the Grid because of the dynamicity of the resources, it’s possible to have updated resource information inside a local site. This motivates the development of algorithms that use a hybrid technique. In this case the information is used to perform the scheduling when available - for example in the local site - and only when it’s not available the scheduler uses replication, thus reducing its overhead. This work proposes such an hybrid algorithm called TMRorR - Task More Reliable or Replicate for the Ourgrid middleware. The algorithm was simulated with GridSim and implemented in OurGrid to perform the experiments. Obtained results showed a better performance of TMRorR in comparison to the Ourgrid scheduler in several scenarios and a reduction in the overhead of creating replica. / A distribuição de tarefas de forma eficiente em grades computacionais possui grandes desafios que devem ser considerados por um algoritmo de escalonamento. Esse desafios estão relacionados com as características das grades, como a escalabilidade, heterogeneidade, dinamicidade, entre outros. Dentre as diversas propostas de algoritmos de escalonamento existentes, grande parte utilizam da informação obtida do ambiente ou da replicação de tarefas como forma de atingir um desempenho satisfatório na execução das aplicações dentro da grade. Os algoritmos de escalonamento que dependem somente das informações para realizar o escalonamento estão restritos a ambientes em que as mesmas estejam disponíveis e sejam confiáveis. Já os algoritmos que utilizam somente de replicação não dependem de nenhuma informação. A existência de ambientes em que a presença de informação não é totalmente confiável ou não atende a todos os recursos da grade, motiva o surgimento de algoritmos que utilizam uma técnica híbrida. Neste caso a informação, quando disponível, é utilizada para realizar o escalonamento, porém, quando não, utiliza-se da replicação de tarefas. Este trabalho realiza um estudo acerca do escalonamento de tarefas realizado pelo WQR do OurGrid e apresenta um novo algoritmo para escalonamento de aplicações Bag-of-Tasks aqui denominado TMRorR (Task for More Reliable or Replicate).Este algoritmo utiliza uma técnica híbrida e, considera sempre que um recurso que possui informação é sempre mais confiável do um que não possui e, também, faz uma distinção entre recursos pertencentes ao domímio local e recursos pertencentes a outros domínios, tendo regras de escalonamento com algumas diferenças para ambos os casos. O algoritmo foi simulado utilizando o GridSim e implementado no OurGrid para realizar os experimentos. Comparando os resultados obtidos, eles mostraram um desepenho melhor do TMRorR em relação WQR na maioria dos casos, como também, uma redução no desperdício de ciclos de CPU com a realização de um controle maior na criação de réplicas.

Made available in DSpace on 2013-08-07T18:42:36Z (GMT). No. of bitstreams: 1 000448655-Texto+Completo-0.pdf: 3228559 bytes, checksum: af4e73cef74eca9bd8a7fea60aae927f (MD5) Previous issue date: 2013 / Several new applications are composed by heterogeneity of tasks implying high complexity degree, and requiring high processing and communicating rate. Multiprocessor System-on-Chip (MPSoC) based on Network-on-Chip (NoC) is a promising targeting architecture to fulfill these requirements, due to its high computation and communication parallelism that enables several tasks executed at the same time. Furthermore, these applications requirements are better fulfilled by MPSoC composed by different types of processors – heterogeneous MPSoC. One challenge in current heterogeneous MPSoC design is partitioning of application tasks, aiming energy consumption minimization and fair load balance. This work contribution is twofold: (i) analysis and comparison of partitioning algorithms; and (ii) the evaluation of partitioning as a pre-mapping task. This work analyzes and compares stochastic and new heuristic partitioning algorithms for obtaining low energy consumption and efficient load balance when applied to tasks partitioning onto heterogeneous MPSoC. In addition, performance results obtained from simulations indicate that the static partitioning technique can be used on application tasks before mapping activities to improve the quality on the static or dynamic mapping and also for minimizing processing time. / Várias aplicações novas são compostas por uma heterogeneidade de tarefas implicando alto grau de complexidade, e requerendo grande capacidade de processamento e comunicação eficiente. Multiprocessor System-on-Chip (MPSoC) baseado em Network-on-Chip (NoC) é uma arquitetura alvo promissora com capacidade de atender diversos requisitos de uma aplicação alvo, devido à alta capacidade de computação e grande paralelismo de comunicação que possibilitam a execução de diversas tarefas simultaneamente. Além disso, requisitos de diversas aplicações embarcadas são melhores atendidos por um MPSoC composto por vários tipos de processadores – MPSoC heterogêneo. Um desafio atual no projeto de MPSoC heterogêneo é particionar tarefas, almejando minimizar consumo de energia e ter balanceamento de carga apropriado. Este trabalho contribui duplamente em: (i) análise e comparação de algoritmos de particionamento; e (ii) avaliação do particionamento como uma atividade pré-mapeamento. Este trabalho analisa e compara algoritmos de particionamentos estocásticos e heurísticos, elaborados para obter baixo consumo de energia e balanceamento de carga eficiente quando aplicados a particionamento de tarefas em um MPSoC heterogêneo. Além disto, resultados de desempenho, obtidos através de simulações, indicam que a técnica de particionamento estático de tarefas pode ser previamente aplicada à atividade de mapeamento de grupos de tarefas em processadores da arquitetura alvo, aprimorando a qualidade do mapeamento estático ou dinâmico, e ainda, minimizando o tempo de processamento.

Made available in DSpace on 2013-08-07T18:42:51Z (GMT). No. of bitstreams: 1 000448654-Texto+Completo-0.pdf: 3794673 bytes, checksum: 27e1f6f68c147a8709c4d67ce49eed05 (MD5) Previous issue date: 2013 / The growing number of manufactured transistors in embedded systems follows the trend of Moore’s Law, which states that every eighteen months the number of transistors on integrated circuits doubles, while its cost remains constant. Another important issue in embedded systems is that applications with more than one processor are increasingly present in market. These devices with several processing elements are named MPSoCs (Multiprocessor System-on-Chip). MPSoCs enables the development of complex systems, together with high performance. Applications executing in MPSoC have constraints to be respected. To meet these constraints, management techniques and resources adaptability should be researched and developed. This work presents the development and evaluation of adaptive management techniques that enable applications executing in MPSoCs to meet their performance requirements. The MPSoC management uses monitoring techniques, which evaluate applications constraints, as throughput and latency. When violations are detected by the monitoring infrastructure, adaptive techniques are executed. In the scope of this work, two techniques were developed: dynamic change in the priority scheduling of tasks and task migration. The evaluation of the proposed techniques is carried out using the HeMPS MPSoC, with centralized and distributed resource management. Results show that, regardless the resource management technique adopted, the proposed adaptive techniques decrease latency and jitter, without affecting the total execution time of applications. With performed adaptive techniques the total execution time wasn’t penalized, in presented experiments increased 7%. / A capacidade de integração em sistemas embarcados acompanha a tendência da Lei de Moore, a qual prevê que a cada dezoito meses o número de transistores em circuitos integrados dobra, enquanto seu custo permanece constante. Outra observação importante em sistemas embarcados é que aplicações com mais de um processador estão cada vez mais presentes no mercado. Estes dispositivos com diversos elementos de processamento são denominados MPSoCs (do inglês, Multiprocessor Sytem-on-Chip). Os MPSoCs permitem o desenvolvimento de sistemas complexos, com alto desempenho. Para que um MPSoC atenda às restrições das aplicações nele executadas, técnicas de gerência e adaptabilidade de recursos devem ser pesquisadas e desenvolvidas.O presente trabalho apresenta o desenvolvimento e avaliação de técnicas de controle adaptativo para atendimentos a requisitos de aplicações executando em MPSoCs. Para efetuar o controle do MPSoC utiliza-se o mecanismo de monitoramento das aplicações. A técnica de monitoramento analisa os requisitos das aplicações, em tempo de execução, verificando possíveis violações nestes requisitos, como vazão e latência. O monitoramento é o gatilho para a execução das técnicas adaptativas desenvolvidas no escopo deste trabalho: alteração dinâmica na prioridade de escalonamento de tarefas e migração de tarefas. Para avaliar as técnicas propostas, foi utilizado a plataforma HeMPS com gerência de recursos centralizada e distribuída. Os resultados mostram que, independente da gerência de recursos que se utiliza, centralizada ou distribuída, as técnicas de adaptabilidade proveem redução de latência e jitter, sem comprometimento do tempo total de execução das aplicações. Com a execução das técnicas de adaptabilidade, o tempo total de execução da aplicação principal não é penalizado, nos casos de teste, melhorando-se em até 7%.

Resumo: Uma linha de produto de software (LPS) pode ser definida como um conjunto de sistemas que compartilham um conjunto comum de características e que satisfazem os requisitos específicos de um determinado domínio. O desenvolvimento de software em linha de produto propõe soluções para os problemas causados pela rápida evolução e complexidade das aplicações. Metodologias de desenvolvimento de LPS têm como base alguns artefatos como, por exemplo, o modelo de características. Este modelo representa como as características são utilizadas durante a criação dos produtos, e também pode ser utilizado durante a atividade de teste, que se torna mais crítica e complexa quando comparada ao processo tradicional. O teste de todas as combinações de características, produtos, é impraticável devido à complexidade crescente das aplicações, e somente um subconjunto destes produtos pode ser testado. As técnicas existentes para seleção de produtos a partir do diagrama de características são geralmente baseadas em teste combinatorial, requerendo a combinação de pares de características do diagrama (teste pair-wise). Essas técnicas não consideram possíveis defeitos que estes diagramas podem conter. A aplicação de uma abordagem baseada em defeitos pode aumentar a probabilidade de encontrar defeitos e a confiança de que os produtos de uma LPS estão de acordo com os seus requisitos. Considerando esse fato, esse trabalho introduz uma abordagem baseada em teste de mutação para auxiliar na seleção de produtos para o teste de LPS. Para isso, são introduzidos operadores de mutação juntamente com um processo de teste e uma ferramenta de automatização. Por fim, são apresentados resultados experimentais, e uma comparação com o teste pair-wise, que demonstra que diferentes tipos de defeitos podem ser revelados pela abordagem introduzida.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Mecânica, 2008. / Submitted by wesley oliveira leite (leite.wesley@yahoo.com.br) on 2009-09-22T19:07:03Z No. of bitstreams: 1 2008_TarsiloBezerraInacio.pdf: 2154422 bytes, checksum: 306ee4d49b6961866bc76702abd813fd (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2009-10-01T17:04:40Z (GMT) No. of bitstreams: 1 2008_TarsiloBezerraInacio.pdf: 2154422 bytes, checksum: 306ee4d49b6961866bc76702abd813fd (MD5) / Made available in DSpace on 2009-10-01T17:04:40Z (GMT). No. of bitstreams: 1 2008_TarsiloBezerraInacio.pdf: 2154422 bytes, checksum: 306ee4d49b6961866bc76702abd813fd (MD5) Previous issue date: 2008-12-01 / Critérios para avaliação da resistência em fadiga baseados em modelos de plano crítico são eficientes quando utilizados em componentes metálicos submetidos a altos ciclos de carregamento. Contudo, existe um elevado custo associado ao processo de busca pelo plano crítico, que é o plano que contém a máxima amplitude de tensão cisalhante. Neste sentido, a proposta deste trabalho é desenvolver uma ferramenta numérica capaz de reduzir significativamente o tempo computacional associado ao processo de busca pelo plano crítico. Inicialmente implementou-se a rotina para avaliar a tensão cisalhante e normal em “todos” os planos de corte de um ponto material em corpos submetidos a condições de flexão e torção. Na etapa seguinte, o processo foi otimizado com a utilização de um Algoritmo Genético. O código resultante fornece a orientação do plano crítico, a máxima amplitude de tensão cisalhante equivalente, a máxima tensão normal e o tempo total no processo de busca. Os resultados revelaram que o método do Algoritmo Genético foi capaz de provocar uma forte redução no custo computacional para determinar o plano crítico material. Além disso, é um método simples de ser implementado e sempre converge para o máximo global com bons níveis de precisão. Neste sentido, a rotina proposta constitui uma ferramenta poderosa e importante que pode ser combinada com um método de elementos finitos para desenvolver componentes reais submetidos a carregamentos complexos de fadiga. _______________________________________________________________________________ ABSTRACT / Critical plane approaches are efficient methods to estimate the resistance of metallic components submitted to high-cycle fatigue. However, there is a high cost associated to the searching for the critical plane, which is the plane that contains the largest shear stress amplitude. In this setting, the aim of this work is to develop a numerical tool capable to significantly reduce the computational cost associated to process the critical plane search. Initially, a routine was implemented to evaluate shear and normal stresses in all material planes of a material point of bodies submitted to bending and torsion conditions. In the next step, the process was optimized using a Genetic Algorithm. The final code finds the critical plane orientation, the maximum equivalent shear stress amplitude, maximum normal stress and total time of search process. The results revealed that the Genetic Algorithm method was capable to provoke a strong reduction in the computational cost to find the material critical plane. Further, it is simple to implement and always find the global maximum with very good levels of accuracy. In this setting, the proposed routine constitutes an important and powerful tool that can be combined with the finite element method to design real components under complex fatigue loadings.