Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2015-07-03T17:52:39Z No. of bitstreams: 1 Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5) / Made available in DSpace on 2015-07-03T17:52:39Z (GMT). No. of bitstreams: 1 Iris Corrêa das Chagas Linck.pdf: 1456080 bytes, checksum: ea4a6f659a229e845649c58baaf8cb23 (MD5) Previous issue date: 2012 / FINEP - Financiadora de Estudos e Projetos / Neste trabalho é desenvolvido um algoritmo híbrido que simula o comportamento do Codificador/Decodificador de vídeo H.264/AVC, ou simplesmente CODEC H.264, utilizado no Sistema Brasileiro de Televisão Digital. O algoritmo proposto tem a finalidade de buscar a melhor configuração possível de seis dos principais parâmetros utilizados para a configuração do CODEC H.264. Este problema é abordado como um problema de otimização combinatória conhecido como Problema de Seleção de Partes e que é classificado como NP-Difícil. O algoritmo híbrido proposto, denominado Simulador de Metaheurísticas aplicado a um CODEC (SMC), foi desenvolvido com base em duas metaheurísticas: Busca Tabu e Algoritmo Genético. Os seis parâmetros de configuração a serem otimizados pelo SMC são: o bit rate; o frame rate; os parâmetros de quantização de quadros tipo B, tipo P e tipo I e a quantidade de quadros tipo B em um grupo de imagens (GOP – Group of Pictures). Os dois primeiros parâmetros mencionados atuam basicamente sobre a qualidade da imagem do vídeo enquanto que os demais parâmetros atuam diretamente na compressão do vídeo. Experimentos e testes foram feitos utilizandose o CODEC H.264 desenvolvido no Projeto Plataforma de Convergência Digital IPTV/TV Digital (DigConv). Nos experimentos o CODEC tem seus parâmetros configurados de acordo com os resultados obtidos pelo SMC. Um vídeo é codificado no CODEC H.264 para que se possa analisar a sua qualidade de imagem e o seu grau de compressão após o processo de codificação. É feita uma correlação entre esses resultados e a Função Objetivo do SMC. A qualidade da imagem é medida através da métrica mais utilizada na literatura, o PSNR (Peak Signal to Noise Ratio), que é calculada pelo próprio CODEC ao final da codificação de um vídeo. Verificouse que à medida que a Função Objetivo aumenta, o CODEC H.264 consegue obter uma melhor qualidade de imagem e um maior grau de compressão de vídeo. / In this work is developed a hybrid algorithm that simulates the behavior of the H.264/AVC video encoder/decoder, or simply H.264 video CODEC, used in the Brazilian System of Digital Television. The proposed algorithm intends to seek the best possible configuration of the six main parameters used for configuring the H.264 video CODEC. This problem is treated as a combinatorial optimization problem known as the Parties Selection Problem, which is classified as NP-Hard. The proposed hybrid algorithm, called Simulator Metaheuristcs applied to a CODEC (SMC), was developed based on two metaheuristics: Tabu Search and Genetic Algorithm. The six configuration parameters to be optimized by the SMC are the bit rate, frame rate, the parameters of quantization tables of type B, type I and type P and the amount of frames type B in a group of pictures (GOP - Group of Pictures).The first two parameters mentioned, work primarily on the quality of the video image while the other parameters act directly on the video compression. Experiments and tests were done using the video CODEC H.264 developed in Digital Convergence Platform IPTV/Digital TV Project (DigConv). DigConv Project. In the experiments the CODEC has its parameters set according to the results obtained by the SMC. Then, a video is encoded by the CODEC in order to analyze the video image quality and the video compression degree reached after the encoding process. It is made a correlation between these results and the objective function of the SMC. The picture quality is measured by the metric most often used in literature, the PSNR (Peak Signal to Noise Ratio), which is calculated by the CODEC at the end of a video encoding process. It was found that as the objective function has increased, the CODEC reached a better image quality and a higher video compression.

Submitted by Silvana Teresinha Dornelles Studzinski (sstudzinski) on 2016-11-18T11:12:32Z No. of bitstreams: 1 Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5) / Made available in DSpace on 2016-11-18T11:12:32Z (GMT). No. of bitstreams: 1 Robermilton Sant´Anna de Oliveira Rodrigues_.pdf: 3942890 bytes, checksum: cd68235e6f58b7b97f966958f932b60d (MD5) Previous issue date: 2016-06-10 / IFRR - Instituto Federal de Educação Ciência e Tecnologia de Roraima / Com o advento da Internet, aliado à constante evolução das tecnologias de distribuição de Banda Larga, juntamente com um público cada vez mais exigente, surge o IPTV (Internet Protocol Television). Atualmente, existem várias pesquisas sobre como melhorar sua distribuição de conteúdo, através dos mais diversos dispositivos disponíveis no mercado, tais como: TV Digital, Tablets e Smartphones. Este trabalho apresenta uma ferramenta computacional, baseada em um modelo matemático, para otimização dos parâmetros do módulo IPTV de uma Plataforma de Convergência Digital (DIGICONV). Essa ferramenta computacional é baseada em aplicações das metaheurísticas Busca Tabu e Algoritmo Genético, a fim de obter melhorias em todos os segmentos da transmissão, além de identificar os motivos de uma possível sobrecarga do sistema, quando não há banda disponível suficiente para atender a todos os clientes, através de configurações específicas nos parâmetros de entrada que são: a taxa de transmissão (Tt), a qualidade de vídeo (Qv), a qualidade de áudio (Qa), os tipos de clientes (Tc), a largura de banda do cliente (Lb) e a quantidade de banda disponível (Bd). Os resultados obtidos neste trabalho comprovaram que tanto a Busca Tabu quanto o Algoritmo Genético obtiveram resultados satisfatórios e otimizados, conforme o aumento da Função Objetivo, atestando sua eficiência. / With the advent of the Internet, combined with the constant evolution of the broadband distribution technologies, along with the public increasingly demanding, IPTV (Internet Protocol Television) arises. Currently, there are several studies on how to improve the distribution of content through a variety of devices available in the market, such as Digital TV, Tablets and Smartphones. This paper presents a computational tool based on a mathematical model to optimize IPTV module parameters of a Digital Convergence Platform (DIGICONV). This software tool is based on applications of metaheuristics Tabu Search and Genetic Algorithm in order to achieve improvements in all segments of the transmission, and to identify the reasons for a possible system overload, when there is not enough available bandwidth to meet all customers through specific settings in the input parameters are: the transmission rate (Tt), the video quality (Qv), audio quality (Qa), the types of customers (Tc), the bandwidth of client (Lb) and the amount of available bandwidth (BD). The results of this study showed that both the tabu search and the genetic algorithm achieved satisfactory results and optimized, with increasing Objective Function, attesting to its effectiveness.

As technology scales down and CMOS circuits are powered by lower supply voltages, standby leakage current becomes significant. A behavioral level framework for the synthesis of data-paths with low leakage power is presented. There has been minimal work done on the behavioral synthesis of low leakage datapaths. We present a fast architectural simulator for leakage (FASL) to estimate the leakage power dissipated by a system described hierarchically in VHDL. FASL uses a leakage power model embedded into VHDL leafcells. These leafcells are characterized for leakage accurately using HSPICE. We present results which show that FASL measures leakage power significantly faster than HSPICE, with less than a 5% loss in accuracy, compared to HSPICE. We present a comprehensive framework for synthesizing low leakage power data-paths using a parameterized Multi-threshold CMOS (MTCMOS) component library. The component library has been characterized for leakage power and delay as a function of sleep transistor width. We propose four techniques for minimization of leakage power during behavioral synthesis: (1) leakage power management using MTCMOS modules; (2) an allocation and binding algorithm for low leakage based on clique partitioning; (3) selective binding to MTCMOS technology, allowing the designer to have control over the area overhead; and (4) a performance recovery technique based on multi-cycling and introduction of slack, to alleviate the loss in performance attributed to the introduction of MTCMOS modules in the data-path. Finally, we propose two iterative search based techniques, based on Tabu search, to synthesize low leakage data-paths. The first technique searches for low leakage scheduling options. The second technique simultaneously searches for a low leakage schedule and binding. It is shown that the latter technique of unified search is more robust. The quality of results generated bytabu-based technique are superior to those generated by simulated annealing (SA) search technique.

In this thesis, a new tool, named CHESS, is designed and developed for control and data-flow graph (CDFG) extraction and the high-level synthesis of VLSI systems. The tool consists of three individual modules for:(i) CDFG extraction, (ii) scheduling and allocation of the CDFG, and (iii) binding, which are integrated to form a comprehensive high-level synthesis system. The first module for CDFG extraction includes a new algorithm in which certain compiler-level transformations are applied first, followed by a series of behavioral-preserving transformations on the given VHDL description. Experimental results indicate that the proposed conversion tool is quite accurate and fast. The CDFG is fed to the second module which schedules it for resource optimization under a given set of time constraints. The scheduling algorithm is an improvement over the Tabu Search based algorithm described in [6] in terms of execution time. The improvement is achieved by moving the step of identifying mutually exclusive operations to the CDFG extraction phase, which, otherwise, is normally done during scheduling. The last module of the proposed tool implements a new binding algorithm based on a game-theoretic approach. The problem of binding is formulated as a non-cooperative finite game, for which a Nash-Equilibrium function is applied to achieve a power-optimized binding solution. Experimental results for several high-level synthesis benchmarks are presented which establish the efficacy of the proposed synthesis tool.

La superposition de topologies virtuelles à la topologie physique d'un réseau est un des principaux mécanismes de l'ingénierie de trafic. Soit un réseau physique d'une certaine topologie et capacité fixées et une matrice de trafic à véhiculer, il s'agit trouver une topologie logique permettant de mapper de manière optimale la matrice de trafic sur le réseau physique. Lors de l'évolution de la matrice de trafic sur des échelles de temps longues, il faudra agir sur le layout. La première contribution concerne la définition de fonctions de coût mieux adaptées à la réalité d'un opérateur, la deuxième contribution concerne la prise en compte du coût de changement du layout. Il s'avère intéressant d'un point de vue opérateur de réduire la complexité du layout, mesurée comme une fonction du nombre de chemins virtuels. Nous avons donc formulé divers problèmes de minimisation de la complexité du layout sous des contraintes de QoS. Il s'agit d'une modélisation réaliste mais qui engendre des modèles difficiles à résoudre. Nous avons développés des heuristiques qui permet de trouver des solutions approchées pour des réseaux de grande taille. Nous avons montré que la complexité des layouts peut être significativement réduite en comparaison avec celle obtenue suite à l'optimisation des fonctions de coût classiques. Le changement du layout implique d'une part un coût d'opération et d'autre part peut engendrer des coupures de service qui affecteront directement le coût d'opération. Nous avons formulé une famille de problèmes prenant en compte le coût de reconfiguration du layout. L'une des heuristiques citées a été adaptée pour analyser ces nouveaux problèmes.

A spacecraft tour trajectory is a trajectory in which a spacecraft visits a number of objects in sequence. The target objects may consist of satellites, moons, planets or any other body in orbit, and the spacecraft may visit these in a variety of ways, for example flying by or rendezvousing with them. The key characteristic is the target object sequence which can be represented as a discrete set of decisions that must be made along the trajectory. When this sequence is free to be chosen, the result is a hybrid discrete-continuous optimization problem that combines the challenges of discrete and combinatorial optimization with continuous optimization. The problem can be viewed as a generalization of the traveling salesman problem; such problems are NP-hard and their computational complexity grows exponentially with the problem size. The focus of this dissertation is the development of a novel methodology for the solution of spacecraft tour trajectory optimization problems. A general model for spacecraft tour trajectories is first developed which defines the parameterization and decision variables for use in the rest of the work. A global search methodology based on the tabu search metaheuristic is then developed. The tabu search approach is extended to operate on a tree-based solution representation and neighborhood structure, which is shown to be especially efficient for problems with expensive solution evaluations. Concepts of tabu search including recency-based tabu memory and strategic intensification and diversification are then applied to ensure a diverse exploration of the search space. The result is an automated, adaptive and efficient search algorithm for spacecraft tour trajectory optimization problems. The algorithm is deterministic, and results in a diverse population of feasible solutions upon termination. A novel numerical search space pruning approach is then developed, based on computing upper bounds to the reachable domain of the spacecraft, to accelerate the search. Finally, the overall methodology is applied to the fourth annual Global Trajectory Optimization Competition (GTOC4), resulting in previously unknown solutions to the problem, including one exceeding the best known in the literature. / text

Increasing debates over a gasoline independent future and the reduction of greenhouse gas (GHG) emissions has led to a surge in plug-in hybrid electric vehicles (PHEVs) being developed around the world. Due to the limited all-electric range of PHEVs, a daytime PHEV charging infrastructure will be required for most PHEVs’ daily usage. This dissertation, for the first time, presents a mixed integer mathematical programming model to solve the PHEV charging infrastructure planning (PCIP) problem. Our case study, based on the Oak Ridge National Laboratory (ORNL) campus, produced encouraging results, indicates the viability of the modeling approach and substantiates the importance of considering both employee convenience and appropriate grid connections in the PCIP problem. Unfortunately, the classical optimization methods do not scale up well to larger practical problems. In order to effectively and efficiently attack larger PCIP problems, we develop a new MASTS based TS algorithm, PCIP-TS to solve the PCIP. The results from computational experiments for the ORNL campus problem establish the dominant supremacy of the PCIP-TS method both in terms of solution quality and computational time. Additional experiments with simulated data representative of a problem that might be faced by a small city show that PCIP-TS outperforms CPLEX based optimization. Once the charging infrastructure is in place, the immediate problem is to judiciously manage this system on a daily basis. This thesis formally develops a mixed integer linear program to solve the daily the energy management problem (DEM) faced by an organization and presented results of a case study performed for ORNL campus. The results from our case study, based on the Oak Ridge National Laboratory (ORNL) campus, are encouraging and substantiate the importance of controlled PHEV fleet charging and realizing V2G capabilities as opposed to uncontrolled charging methods. Although optimal solutions are obtained, the solver requires practically unacceptable computational times for larger problems. Hence, we develop a new MASTS based TS algorithm, DEM-TS, for the DEM models. Results for ORNL campus data set prove the dominant computational efficiency of the DEM-TS. For the simulated extended sized problems that resemble the complexity of a problem faced by a small city, the results prove that DEM-T not only achieves optimality, but also produces sets of multiple alternate optimal solutions. These could be very helpful in practical settings when alternate solutions are necessary because some solutions may not be deployable due to unforeseen circumstances. / text

Šiame darbe nagrinėjamas patobulintas tabu paieškos metodas, žinomas kaip iteratyvioji tabu paieška (ITP). Pasiūlytos kai kurios ITP metodo modifikacijos, besiremiančios tam tikromis sprendinių mutavimo (pertvarkymo) procedūromis (inversijos, įterpimai ir kt.), kurios įgalina pagerinti gaunamų sprendinių kokybę. Atlikti išsamūs sudaryto ITP algoritmo ir kitų pasiūlytų modifikacijų eksperimentiniai tyrimai, panaudojant testinius KU pavyzdžius iš KU testinių pavyzdžių bibliotekos TSPLIB. Gauti rezultatai patvirtina pasiūlytų modifikacijų pranašumą kitų ITP variantų atžvilgiu. / In this work, one of the heuristic algorithm – the iterated tabu search and its modifications are discussed. The work is organized as follows. Firstly, some basic definitions and preliminaries are given. Then, the iterated tabu search algoritm and its variants based on special type mutations are considered in more details. The ITS algorithms modifications were tested on the TSP instances from the TSP library TSPLIB. The results of this tests (experiments) are presented as well. The work is completed with the conclusions.

Plati tvarkaraščių sudarymo uždavinio sritis yra industrinių, taip vadinamų gamybinių, tvarkarščių sudarymas. Yra trys gaminių tvarkaraščių klasės: darbų fabrikas, atvirasis fabrikas ir srautinis fabrikas. Bendra uždavinio specifikacija gali būti apibrėžta tokiu būdu: yra darbų aibė ir mašinų aibė, kurios tarpusavyje turi sąveikauti tam tikru specifiniu būdu. Paprastai šios problemos yra sunkiai išsprendžiamos tradiciniais (tiksliaisias) metodais. Metaeuristiniai algoritmai dažniausiai pateikia tiktai artimus optimumui sprendinius, tačiau per apibrėžtą laiką. Šiame darbe įgyvendinta keletas metaeuristikų: genetiniai algoritmai (besiskiriantys jų parametrų reikšmėmis) ir tabu paieškos algoritmai (besiskiriantys sprendinio aplinka). Kai kurios genetinio algoritmo strategijos pasiūlytos kaip genetinio algoritmo parametrų tyrimo išvada. Aštuoni algoritmai yra tiriami atsitiktinėms gamybinių tvarkaraščių sudarymo problemoms, lyginant pradinius sprendinius ir minimumus, pasiektus sprendinius ir minimumus, skaičiavimo trukmes ir skirtumą tarp pradinių bei pasiektų sprendinių. Pabaigoje pateikiama išvada apie tai, kad vieno tipo genetiniai parametrai (kryžminimo ir mutacijos lygiai) yra ypač reikalingi algoritmo konvergavimo, diversifikacijos ir intensifikacijos prasme, kito tipo (iteracijų skaičius ir populiacijos dydis) turi priklausyti nuo resursų, trečio tipo (elitizmas) yra geri “buferiai”. Galiausiai, kuomet paprasčiausios formos tabu paieška yra silpnesis konkurentas... [toliau žr. visą tekstą] / A wide area of scheduling problem is industrial so called shop scheduling. There are three classes of shop scheduling: Job Shop, Open Shop and Flow Shop. General problem specification could be specified as follows: there is set of jobs and set of machines, which should interact with each other in some specific way. Typically these problems are hard to solve in traditional (exact) methods. Metaheuristics algorithms mostly produce only nearby-optima, but in proper time. We implemented several metaheuristics: genetic algorithms (separated by values of their parameters) and several Tabu search algorithms (separated by neighborhood of solution). Some strategies of genetic algorithms are suggested as conclusion of genetic algorithm parameter research. Eight algorithms are examined for random shop scheduling problems in terms of initial solutions and minimum, gained solutions and minimum, processing time and difference between initial and gained solutions. In the end, author concludes, that one kind of genetic parameters (crossover and mutation rates) are especially demanding in sense of algorithm convergence, diversification and intensification aspects, other (number of iterations and population size) should depend on resources, third (elitism) is good “buffers”. Finally, while with its simplest form, Tabu search seems to be less competitive in algorithm effectiveness research, its dynamic modification outperforms all proposed genetic algorithms, but both – tabu search with... [to full text]

Thesis (MSc (Logistics))--University of Stellenbosch, 2009. / ENGLISH ABSTRACT: Technological advances made over the past century have had a major impact on traditional wineries. Software solutions for management issues are widely available and give rise to the prospect of computerized decision support systems assisting in various aspects of managing a winery. The most popular applications seem to be concerned with supply chain management or harvest scheduling. Such projects are under way all over the globe and great success has been achieved to this e ect. However, prior to this study no such project has been considered in South Africa. The phrase active cellar scheduling problem refers to the assignment of grape batches to processors inside the cellar where bottlenecks often occur during the busy harvesting period. The phrase harvest scheduling problem, on the other hand, refers to selecting the best possible dates to harvest the respective vineyard blocks in order to preserve grape quality. A mixed integer programming model for the active cellar scheduling problem is derived in this thesis, but proves to be too time consuming to solve exactly via the branch-and-bound method. A meta-heuristic tabu search approach is therefore designed to solve the problem approximately instead. When applied to a small, ctitious cellar, it is found that the tabu search method often solves the problem optimally. The computer processing time associated with the tabu search approach also constitutes a signi cant (often thousand-fold) improvement over that of the branch-and-bound approach for realistically sized problem instances. A generic tabu search is also designed to solve the over-arching harvest scheduling problem for a general winery. This schedule is found by referring to the smaller tabu search of the active cellar scheduling in order to verify the impact that harvesting moves have on activities in the cellar. One harvesting schedule is considered a better schedule than another when it has a lower harvest evaluation score, determined by the placement of the vineyard blocks in the harvesting schedule. The harvest evaluation score takes into account the combination of vineyard blocks selected for harvesting on the same day (and their e ect on the active cellar) as well as the ripeness and quality of the grapes. Both tabu searches are nally included in a exible, computerized decision support system, called VinDSS. This system is found to produce good harvesting schedules when compared to an actual ve day schedule during the 2009 harvesting period at Wamakersvallei, a winery serving as case study for this thesis. / AFRIKAANSE OPSOMMING: Tegnologiese vooruitgang oor die afgelope eeu het 'n groot invloed op tradisionele wynkelders gehad. Sagteware-oplossings wat besluitsteun tot bestuursaangeleenthede bied, is algemeen beskikbaar en het gelei tot die rekenaarmatige implementering van besluitsteunstelsels vir wynkelders. Dit blyk dat die mees popul^ere besluitsteuntoepassings in die wynindustrie te make het met besluite rakende van voorsieningskettings en oes-skedulering. Sulke besluitsteunprojekte is w^ereldwyd onderweg en het alreeds groot sukses behaal. Daar is egter tot dusver geen so 'n projek in Suid-Afrika onderneem nie. Die frase aktiewe kelderskeduleringsprobleem verwys na die toekenning van druifvragte aan masjiene binne die kelder waar bottelnekke algemeen tydens die besige parstydperk voorkom. Die frase oes-skeduleringsprobleem, daarenteen, verwys na die seleksie van bes moontlike oesdatums vir elk van die wingerdblokke om sodoende druifkwaliteit te verseker. 'n Gemengde heeltallige programmeringsmodel is vir die aktiewe kelderskeduleringsprobleem ontwikkel, maar die rekenaaroplossingstyd van hierdie benadering blyk te lank te wees om die probleem eksak deur middel van 'n vertak-en-begrens metode op te los. 'n Meta-heuristiese tabu soektog is dus ontwikkel om die probleem benaderd op te los. Wanneer hierdie benadering op 'n klein, ktiewe kelder toegepas word, word optimale oplossings dikwels verkry. Verder toon die rekenaaroplossingstyd van die tabu soektog 'n groot (in sommige gevalle byna 'n duisendvoudige) verbetering op di e van die eksakte oplossingsmetode. 'n Generiese tabu soektog is ook ontwikkel om die oorkoepelende oes-skeduleringsprobleem vir 'n algemene wynkelder op te los. So 'n oes-skedule word gevind deur na die kleiner tabu soektog vir die aktiewe kelderskedulering te verwys om sodoende die e ekte van veranderinge in die oesskedule op die prosesse binne die aktiewe kelder na te speur. Een oes-skedule word beter as 'n ander skedule beskou wanneer dit met 'n beter oes-evalueringswaarde gepaard gaan, soos deur die plasing van die wingerdblokke in die skedule bepaal. Die oes-evalueringswaarde neem die moontlike kombinasies van wingerblokke wat op dieselfde dag geoes word, in ag (en ook die e ek wat dit op aktiwiteite in die kelder het), asook die rypheid en kwaliteit van die druiwe. Beide tabu soektogte word in 'n plooibare, rekenaar-ge mplementeerde besluitsteunstelsel, bekend as VinDSS, ingesluit. Daar word gevind dat hierdie stelsel goeie oes-skedules lewer wanneer dit vergelyk word met 'n werklike vyf-dag skedule tydens die 2009 parsseisoen van Wamakersvallei, die kelder wat as gevallestudie vir hierdie tesis gedien het.