Problemas de escalonamento cuja função objetivo é o consumo de energia tem sido cada vez mais estudados. Neste trabalho, estudamos o problema conhecido, em inglês, por Dynamic Speed Scaling, um problema de escalonamento de tarefas bem definidas em processadores de velocidade variável, cujo consumo de energia é função da velocidade. Além disso, relacionamos este problema com outro conhecido como MOSP, sigla em inglês para Multi-Organization Scheduling Problem. Neste, queremos escalonar tarefas de múltiplas organizações independentes respeitando certas restrições individuais. Provamos, neste trabalho, que este novo problema é NP-Completo e desenvolvemos várias heurísticas eficientes cujos testes experimentais mostram economia de energia significativa. / We studied, in this work, the problem of scheduling a set of well-defined tasks in a variable speed processor with the objective of minimizing the energy consumption, that is given as a function of the processor\'s speed, field known as Dynamic Speed Scaling. Also, we relate this problem to another known as MOSP (Multi-Organization Scheduling Problem), problem in which several independent organizations share tasks and resources to achieve a better global solution, but also respecting selfish restrictions. For the combined problem, we show that it is NP-Complete and designed several efficient heuristics that achieves good results in a experimental setup.

Orientador: André Victor Lucci Freitas / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Biologia / Made available in DSpace on 2018-08-18T19:14:01Z (GMT). No. of bitstreams: 1 Ribeiro_DaniloBandini_D.pdf: 21049242 bytes, checksum: aa5d5c4cafb6f3c74669788c029701d9 (MD5) Previous issue date: 2011 / Resumo: A Amazônia representa mais da metade da área de todas as florestas tropicais do mundo, e vem sendo ameaçada por diversas atividades antrópicas, incluindo vários tipos de extração de madeira. O corte seletivo de impacto reduzido (em inglês "Reduced Impact Logging - RIL") é considerado um método menos destrutivo de exploração madeireira que promove uma menor alteração na estrutura da floresta comparado com métodos convencionais. No entanto, existem poucas informações sobre os efeitos do RIL em invertebrados, incluindo borboletas. Desta forma, investigamos o efeito do RIL na estrutura da vegetação florestal e sobre as borboletas frugívoras, comparando a fauna do dossel e do sub-bosque entre uma área explorada (RIL) e uma área não explorada (controle). Devido à pouca informação disponível sobre protocolos de amostragem para as borboletas tropicais, alguns aspectos metodológicos relativos à amostragem dos ninfalídeos frugívoros foram investigados. Analisamos como a detectabilidade varia entre diferentes espécies, habitats (Amazônia x Mata Atlântica), estratos da floresta e também qual o esforço adequado de amostragem para detectar uma certa quantidade espécies em uma determinada área, no prente estudo esta quantidade foi estabelecida como 25% do total de espécies estimado no local. Implicações biológicas Uma floresta não explorada apresenta árvores adultas e juvenis maiores do que as de uma floresta explorada (RIL). O número de plântulas e mudas é maior na floresta explorada (RIL) e a distribuição de freqüências de tamanhos (SDFslope) não foi diferente entre as áreas de RIL (-2,61) e não explorada (-2,31). A abertura do dossel foi maior na floresta não explorada, provavelmente devido a um aumento das plantas do sub-bosque na floresta RIL. A área basal e altura das árvores foram maiores na floresta não explorada. Em relação às borboletas frugívoras, a fauna do dossel é diferente e significativamente mais rica do que a fauna do sub-bosque, mostrando que amostrar apenas o estrato mais baixo pode subestimar a diversidade de borboletas. Os efeitos do RIL foram detectados principalmente na assembleia de borboletas do sub-bosque, onde foram observadas diferenças significativas na composição de espécies entre as áreas. Os impactos do RIL, que incluem o corte de árvores, a abertura de trilhas de arraste e de estradas, são mais intensos no sub-bosque do que no dossel. Estas diferentes intensidades de impacto no dossel e no sub-bosque podem explicar os diferentes efeitos do RIL nas borboletas presente nesses estratos. Considerando o grande potencial das borboletas frugívoras para prever as respostas de vários outros grupos taxonômicos à perturbação da floresta na Amazônia, esperamos que padrões semelhantes sejam encontrados em outros táxons. No entanto, apesar dos efeitos detectáveis do RIL em borboletas frugívoras, não pudemos perceber espécies que foram excluídas ou que invadiram a área de RIL, os nossos resultados mostram principalmente diferenças nas abundâncias das espécies entre as áreas. Este resultado é similar ao encontrado em estudos feitos com outros taxa mostra que o RIL em geral não altera a diversidade de espécies podendo ser uma alternativa para preservar uma parcela significativa da fauna em áreas com este tipo de exploração. A criação de áreas protegidas na Amazônia apesar de desejável é bastante complicada e nem sempre é efetiva na preservação da cobertura vegetal, assim sendo o corte seletivo de impacto reduzido pode ser considerado uma boa alternativa para preservar borboletas frugívoras na floresta amazônica e, certamente, muitos outros táxons. Além disso, devido ao alto valor da madeira produzida neste sistema, esta poderia ser uma alternativa econômica desejável para a região. Implicações metodológicas Quase todas as borboletas e mariposas amostrados no presente estudo foram mais facilmente amostradas em um estrato específico (dossel ou sub-bosque). No presente estudo, mesmo as espécies mais comuns do dossel raramente foram amostradas no subbosque. Assim, fazer uso de um protocolo de amostragem que não utiliza armadilhas em ambos os estratos irá aumentar os erros de detecção de muitas borboletas e pode conduzir a inferências incorretas sobre a riqueza e diversidade em uma determinada área. As diferenças na detectabilidade entre os meses no conjunto de dados da Amazônia mostraram que mesmo quando as borboletas são amostradas durante o período do ano com maior probabilidade de captura, existem diferenças importantes na detectabilidade entre os meses. A baixa detectabilidade e a grande variação entre os estratos e meses nos levam a propor que, para borboletas frugívoras, a amostragem deve ser feita na época correta e em florestas altas os diferentes estratos devem ser considerados de modo a reduzir os erros de detecção e possíveis vieses nos resultados. O esforço amostral mínimo para a detecção de 25% das espécies presentes nas florestas tropicais é de 130 armadilhas / dia para a Mata Atlântica e 510 dias para Amazônia Central. Além disso, a amostragem deve ser feita com réplicas temporais em um curto espaço de tempo para aumentar o poder de interpretação dos dados coletados / Abstract: The Amazon region represents more than half of the area of all tropical forests in the world, and has been threatened by many anthropogenic activities, including several kinds of timber harvesting. Reduced-Impact Logging (RIL) is considered a less destructive method of timber harvesting that promotes a smaller change in forest structure than conventional logging. However, there is a general lack of information about the effects of RIL on Amazonian invertebrates, including butterflies. We therefore investigated the effect of RIL on forest vegetation structure and on fruit-feeding butterflies by comparing their distribution on canopy and understory between an area under RIL and a control area without RIL. Because of the relative lack of information about sampling protocols for tropical butterflies, some methodological aspects of fruit-feeding Nymphalidae sampling were investigated. We analyzed the variation in detectability among species, habitats (Amazon x Atlantic Forest), layers and the adequate sampling effort need for detect an specific amount of species in a given area were analyzed in this thesis, in the present study this amount was established as 25% of the total estimated species richness. Biological implications An unlogged forest has bigger juveniles and adult trees, and less seedlings and saplings than a RIL forest, and the Size Frequency Distribution (SDF) slope was not different from those of logged (-2.61) and unlogged (-2.31) areas. The canopy openness was greater in the unlogged forest, probably due to an increase of understory plants in the RIL forest. The basal area was wider and the height was taller in unlogged forest trees. In relation to the fruit-feeding butterflies, the canopy fauna is different and significantly richer than the understory fauna, showing that sampling only the lower strata underestimates the diversity of fruit-feeding butterflies. The effects of RIL were mainly detected in the understory butterfly assemblage, as significant differences were observed in species composition within this stratum. Effects of the RIL regime, which include tree cutting, skid trails and road openings, are stronger in the understory than in the canopy, explaining the reported differences. Despite the detectable effects of RIL on the composition of fruit-feeding butterfly's assemblages the overall diversity was not affected, this pattern is very similar for many other taxa indicating that a noticeable part of the diversity of many taxa could be preserved in areas under RIL management. Given the problems of creating protected areas in the Amazon, RIL is a good alternatives to preserve fruit-feeding butterflies and surely many other taxa, and it might be a desirable economic alternative for the region. Methodological implications Almost all butterflies and moths sampled in the present study were more readily trapped in one specific stratum. Indeed, in the present study, even the most common canopy species were rarely sampled in the understory. Thus, using a sampling protocol that does not locate traps in both layers will increase the imperfect detection of many butterflies and could lead to incorrect inferences about the richness and diversity in a given area. The differences in detectability between months in the Amazon dataset showed that even with an experimental design planned for sampling butterflies during the period that enhances capture probability, there are important differences in butterfly detectability across months. The low detectability and great variation among strata and months in fruit-feeding butterflies lead us to assume that sampling designs must address sampling effort to the correct season and strata reducing imperfect detections and biases in the results. The minimal sampling effort for detecting 25% of the species present in tropical forests is 130 trap/days in Atlantic Forest and 510 days in Central Amazon. Additionally, such sampling should use temporal replication over a short period to improve the interpretability of the data collected / Doutorado / Doutor em Ecologia

Problemas de escalonamento cuja função objetivo é o consumo de energia tem sido cada vez mais estudados. Neste trabalho, estudamos o problema conhecido, em inglês, por Dynamic Speed Scaling, um problema de escalonamento de tarefas bem definidas em processadores de velocidade variável, cujo consumo de energia é função da velocidade. Além disso, relacionamos este problema com outro conhecido como MOSP, sigla em inglês para Multi-Organization Scheduling Problem. Neste, queremos escalonar tarefas de múltiplas organizações independentes respeitando certas restrições individuais. Provamos, neste trabalho, que este novo problema é NP-Completo e desenvolvemos várias heurísticas eficientes cujos testes experimentais mostram economia de energia significativa. / We studied, in this work, the problem of scheduling a set of well-defined tasks in a variable speed processor with the objective of minimizing the energy consumption, that is given as a function of the processor\'s speed, field known as Dynamic Speed Scaling. Also, we relate this problem to another known as MOSP (Multi-Organization Scheduling Problem), problem in which several independent organizations share tasks and resources to achieve a better global solution, but also respecting selfish restrictions. For the combined problem, we show that it is NP-Complete and designed several efficient heuristics that achieves good results in a experimental setup.

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines. / Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.

Submitted by Elton Lever (elton@icomp.ufam.edu.br) on 2018-08-23T20:26:01Z No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-08-23T20:35:20Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-08-24T13:35:27Z (GMT) No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) / Made available in DSpace on 2018-08-24T13:35:28Z (GMT). No. of bitstreams: 1 DissertacaoMestradoElton Lever-ProfRosiane-PPGI-VF.pdf: 2475783 bytes, checksum: 57e9ed5c603736311bd6f477643ff425 (MD5) Previous issue date: 2017-06-22 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation addresses the class of job scheduling problems with precedence constraints and unit execution times, in identical parallel processors. Such a class of problems is of great importance in computational complexity theory, since small varia- tions in the conditions involved in scheduling make an easy problem very difficult. Two major problems involve the condition of the number of processors, where, if the number of processors is variable, given as input, such problem is proved to be NP-complete, but if the number of processors is fixed, the problem is still open. In this context, the focus of the research involves the problem already proven to be NP-complete, where for which we investigated the main approximation algorithms in the literature and their proofs of approximation ratio of the optimal, such as of the Garey & Jonhson’s 2-approximation algorithm, of the Hu, of the Coffman & Graham, and of the Gangal & Ranade with 2 − (7/(3P + 1)), the best approximation ratio in the literature. The approximation ratio proofs of such algorithms were detailed. As the main contribution of this research, were proved the optimality for specific classes of acyclic directed graphs involving trees (prece- dence trees, such as in-tree and out-tree) for the best approximation algorithms literature. / Esta dissertação aborda a classe de problemas de escalonamento de tarefas com restrições de precedências e tempos unitários em processadores paralelos idênticos. Tal classe de problemas tem uma grande importância em teoria da complexidade computacional, uma vez que pequenas variações nas condições envolvidas no esca- lonamento, fazem com que um problema fácil se torne muito difícil. Dois grandes problemas envolvem a condição do número de processadores, onde, se o número de processadores for variável, dado como entrada, tal problema é provado ser NP-completo, mas, se o número de processadores for fixo, o problema ainda está em aberto. Neste contexto, o foco da pesquisa envolve o problema já provado ser NP-completo, onde para qual se investigou os principais algoritmos aproximativos existentes na literatura e suas provas de razão de aproximação do ótimo, tais como o algoritmo 2-aproximativo de Garey & Jonhson e as melhorias de Hu, Coffman & Graham e de Gangal & Ranade (GR) com 2 −(7/(3P+1)), o de melhor razão de aproximação da literatura. As provas de razão de aproximação de tais algoritmos foram detalhadas. Como principal contribuição da pesquisa, foram determinados casos especiais ótimos, para classes específicas de grafos direcionados acíclicos que envolvem arborescências (árvores de precedência, como in-tree e out-tree) para o melhor algoritmos aproximativo da literatura. / Compreender o que querem em alguns momentos.