Orientadores: Nelson Luis Saldanha da Fonseca, Daniel Macêdo BatistaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: A computação em Grade e em Nuvem são dois importantes paradigmas da computação concebidos para lidar com a complexidade da execução de aplicações e com os requisitos exigentes das aplicações emergentes. Além do mais, ambos paradigmas fornecem infraestruturas de execução compostas por equipamento heterogêneo, distribuído em diferentes pontos geográficos e ligado por enlaces de rede. Enquanto Grades proporcionam informação sobre os recursos físicos disponíveis, Nuvens posicionam o usuário num nível de abstração maior, fornecendo aplicações, plataformas e infraestrutura em forma de serviços sob-demanda. Em Grades e Nuvens, o tempo de execução de aplicações complexas pode ser reduzido através do bom uso dos recursos heterogêneos, isto é, através da escolha da combinação mais apropriada de recursos de rede e de processamento para a execução da aplicaçao. No entanto, este é um problema do tipo NP-difícil. Adicionalmente, tarefas que compõem aplicações complexas podem ter demandas específicas de software, incorporando uma variável adicional à complexidade do problema de escalonamento. Além disso, para determinar a combinação mais apropriada de tais recursos, são implementados algoritmos de escalonamento. Assim, tais escalonadores podem ser implementados, visando produzir escalonamentos com o menor tempo de execução, mínimo uso de recurso ou menores custos de contratação de serviços, entre outros. Esta dissertação propõe três novos escalonadores para Grade e Nuven baseados em Programação Linear Inteira que visam produzir escalonamentos com o menor tempo de execução. Tais escalonadores usam máquinas virtuais com o objetivo de preencher os requerimentos de software das tarefas que fazem parte das aplicações complexas. Adicionalmente, é proposta uma nova técnica de escalonamento com os mesmos objetivos, para redefinir escalonadores tradicionais que não consideram a instanciação de máquinas virtuais, a fim de que possam escalonar este tipo de aplicações. Resultados experimentais demonstram a eficiência de cada abordagem de escalonamento em diferentes cenáriosAbstract: Grid and Cloud are important computing paradigms that cope with the complexity of the execution of emerging applications and requirements. Furthermore, both paradigms provide powerful infrastructure composed of heterogeneous equipment, which are located in different geographical points with fast network links connecting them. However, while Grids supply information regarding the available physical resources, Clouds place users in a higher level of abstraction, providing applications, platforms, and infrastructure as on-demand web services. Even though, in grids and clouds, the execution time of complex applications can be reduced by using the powerful heterogeneous resources, choosing the most appropriate combination of processing and network resources to achieve it is an NP-Hard problem. Furthermore, tasks within complex applications may have specific software demands, incorporating an additional variable to the complexity of the scheduling problem. Implementations of scheduling algorithms, are used in order to determine appropriate combinations of such resources. These schedulers can be implemented with the aim of producing schedules with the lowest execution time, resources usage, and monetary cost, among others. This dissertation proposes three new Grid/Cloud schedulers based on Integer Linear Programming that aim to produce schedules with the lowest execution time. Such schedulers use Virtual Machines with the objective of fulfilling the software requirements of the tasks that compose complex applications. An additional scheduling technique with the same purposes is also proposed, which enhances existing schedulers that do not consider Virtual Machines so that they can also be able to schedule this type of complex applications. Experimental results showed the efficiency of each scheduling approach in diverse scenariosMestradoCiência da ComputaçãoMestre em Ciência da Computação133035/2009-3CNPQ