Orientador: Jacques Wainer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T14:02:06Z (GMT). No. of bitstreams: 1 Tampelini_LeonardoGarcia_M.pdf: 834632 bytes, checksum: b0f1d3f3d777417870d8ddd0d317ab8e (MD5) Previous issue date: 2012 / Resumo: Com a disseminação de tecnologias de gerenciamento empresarial, empresas procuram promover serviços mais ágeis e de maior qualidade. Neste contexto, áreas como gerenciamento de workflow vêm contribuindo para uma melhor organização na distribuição de tarefas. A aproximação da área de escalonamento com workflow demonstra um grande potencial para atender tais requisitos; porém, uma escassez de trabalhos voltados ao tratamento de estruturas de roteamento paralelas, comumente encontradas em modelos de workflow, é perceptível na literatura de escalonamento. Este trabalho tem por objetivo aproximar essas duas áreas apresentando três novas abordagens de escalonamento voltadas à ordenação de casos dentro de estruturas de roteamento paralelas (AND). Para alcançar tal objetivo, um conjunto de simuladores foi implementado representando o ambiente dinâmico de workflow, suas incertezas, bem como os diferentes cenários onde estruturas do tipo AND podem ocorrer. O desempenho de tais políticas foi comparado com regras amplamente utilizadas em sistemas de workflow, como FIFO (First In First Out), EDD (Earliest Due Date) e SPT (Shortest Processing Time). A análise dos resultados foi efetivada por meio de uma análise de variância (ANOVA) juntamente com o teste de Tukey. Os resultados mostram que é mais vantajoso utilizar técnicas específicas para estrutura de roteamento AND do que apenas aplicar as técnicas mais utilizadas / Abstract: With the dissemination of business management technologies, companies look for to promoting faster services with higher quality. In this context, areas such as workflow management have contributed to a better organization in the distribution of tasks. The approach between scheduling area and workflow area shows great potential to attend these requirements, but a lack of studies directed to the treatment of parallel routing structures, commonly found in workflow models, is apparent escalation in the literature about scheduling. This work aims to approximate these two areas, presenting three new scheduling approaches, directed to the raging of the cases within routing structures parallel (AND). To reach this objective a set of simulators was implemented, representing the dynamic workflow environment, their uncertainties, as well as the different scenarios where that structures such as AND may occur. The performance of these politics was compared with rules widely used in workflow systems, such as FIFO (First In First Out), EDD (Earliest Due Date) and SPT (Shortest Processing Time). The results show that it is more advantageous to use techniques focused on AND routing structure than only apply the most utilized ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

O problema de escalonamento de veículos com múltiplas garagens (MDVSP, do inglês Multi-Depot Vehicle Scheduling Problem) é um problema clássico de logística e transportes. O MDVSP também é a base para a solução de vários problemas correlatos, tais como o problema de escalonamento de veículos em tempo-real e soluções integradas com o escalonamento de veículos, tais como o escalonamento da tripulação e otimização da tabela de horários. Desta forma, aprimorar a solução deste problema pode ser considerado de grande relevância, a qual permitirá resolver grandes instâncias reais de forma eficiente, bem como permitir a solução de problemas correlatos. O objetivo desta dissertação é verificar a aplicabilidade da utilização da rede tempo-espaço e do método de geração de colunas modificado proposto, para a solução deste problema, e de sua variante com frota heterogênea, considerando grandes instâncias. Diversos testes foram realizados utilizando o gerador de instâncias aleatórias com base na distribuição de demandas proposto. Grandes instâncias, envolvendo milhares de viagens (entre 500-10.000) e dezenas de garagens (4-128) são resolvidas em tempos razoáveis. / The multiple-depot vehicle-scheduling problem (MDVSP) is a classic logistic and transportation problem. The MDVSP is also a subproblem for solving various related problems, such as the real time vehicle scheduling problem, disruption management; and integrated problems such as the vehicle and crew scheduling problems. Although several mathematical and solution method have been developed in the literature, large instances (involving thousands of trips and several depots) are still difficult to solve in a reasonable time. The objective of this research work is to verify the applicability of the use of the space-time network towards obtaining good solutions for large instances in short time. Time-space network was suggested by Kliewer et al (2006), and it is positioned with respect to two-dimensional axes, one representing time and the other one space or stations. The arcs represent deadheading movements; and waiting periods in the same station. Solution methods for the MDVS combining time space with integer linear programming solvers and column generation were developed. Extensive testing was carried out using random generated instances, based on demands distribution. Large instances, involving thousands of trips (between 1,000-10,000) and dozen (4-64) depots, are solved in reasonable times.

Orientadores: Carlile Campos Lavor, Tibérius de Oliveira e Bonates / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T15:11:50Z (GMT). No. of bitstreams: 1 Lima_JorgeFerreiraAlencar_D.pdf: 1109545 bytes, checksum: 086223c23c920a9abe0d3661769a6a7d (MD5) Previous issue date: 2015 / Resumo: Geometria de Distâncias Euclidianas (GDE) é o estudo da geometria euclidiana baseado no conceito de distância. É uma teoria útil em diversas aplicações, onde os dados consistem em um conjunto de distâncias e as possíveis soluções são pontos em algum espaço euclidiano que realizam as distâncias dadas. O problema chave em GDE é conhecido como Problema de Geometria de Distâncias (PGD), em que é dado um inteiro K>0 e um grafo simples, não direcionado, ponderado G=(V,E,d), cujas arestas são ponderadas por uma função não negativa d, e queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Consideramos tanto problemas teóricos quanto aplicações da GDE. Em termos teóricos, demonstramos a quantidade exata de soluções de uma classe de PGDs muito importante para problemas de conformação molecular e, além disso, conseguimos condições necessárias e suficientes para determinar quando um grafo completo associado a um PGD é realizável e qual o espaço euclidiano com dimensão mínima para tal realização. Em termos práticos, desenvolvemos um algoritmo que calcula tal realização em dimensão mínima com resultados superiores a um algoritmo clássico da literatura. Finalmente, mostramos uma aplicação direta do PGD em problemas de escalonamento multidimensional / Abstract: Euclidean distance geometry (EDG) is the study of Euclidean geometry based on the concept of distance. This is useful in several applications, where the input data consists of an incomplete set of distances and the output is a set of points in some Euclidean space realizing the given distances. The key problem in EDG is known as the Distance Geometry Problem (DGP), where an integer K>0 is given, as well as a simple undirected weighted graph G=(V,E,d), whose edges are weighted by a non-negative function d. The problem consists in determining whether or not there is a (realization) function that associates the vertices of V with coordinates of the K-dimensional Euclidean space, in such a way that those coordinates satisfy all distances given by d. We considered both theoretical issues and applications of EDG. In theoretical terms, we proved the exact number of solutions of a subclass of DGP that is very important in the molecular conformation problems. Moreover, we described necessary and sufficient conditions for determining whether a complete graph associated to a DGP is realizable and the minimum dimension of such realization. In practical terms, we developed an algorithm that computes such realization, which outperforms a classical algorithm from the literature. Finally, we showed a direct application of DGP to multidimensional scaling / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Paulo Sérgio Martins Pedro, Edson Luiz Ursini / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-27T04:51:09Z (GMT). No. of bitstreams: 1 MassaroJunior_FlavioRubens_M.pdf: 3302871 bytes, checksum: aa117bbaac53f7ead30d1a21700e03aa (MD5) Previous issue date: 2015 / Resumo: Modos de operação e mudanças de modo são uma abstração útil para permitir que sistemas de tempo real sejam flexíveis e configuráveis. Trabalhos prévios em escalonamento preemptivo com prioridades fixas permitem que as tarefas passem de um modo de operação para outro provendo garantias de tempo real. No entanto, a configuração adequada dos parâmetros críticos, tais como o offset de uma tarefa, apesar de trabalhos anteriores terem abordado este assunto, permanece uma lacuna a ser explorada. Sem um método que automatize esta etapa do processo, garantindo ao mesmo tempo que os requisitos básicos sejam atendidos, a adoção plena de mudanças de modo em sistemas de tempo real permanece limitada a sistemas relativamente simples, com um conjuntos de tarefas limitado. Propomos um método para atribuir offsets às tarefas em uma mudança modo, através de uma abordagem Metaheurística (algoritmos genéticos). Este método permite a configuração e/ou a minimização da latência de pior caso de uma mudança modo. A latência de uma mudança de modo é um parâmetro crítico para ser minimizado, uma vez que durante a mudança de modo o sistema oferece funcionalidade limitada, uma vez que o conjunto de tarefas está parcialmente em operação. Também elaboramos uma classificação das mudanças de modo de acordo com as necessidades das aplicações. Esta classificação, quando aplicada a uma série de estudos de casos, permitiu validar a abordagem de minimização/configuração, estender a classificação anteriormente existente e demonstrar que o método é flexível, já que pode acomodar uma ampla variedade de tipos de mudanças de modo / Abstract: Modes of operation and mode-changes are a useful abstraction to enable configurable, flexible real-time systems. Substantial work on the fixed priority preemptive scheduling approach allowed tasks across a mode-change to be provided with real-time guarantees. However, the proper configuration of critical parameters such as task offsets, despite initial work, remains a gap in research. Without a method that automates this design step, while assuring that the basic requirements are met, the full adoption of mode-changes in real-time systems remains limited to relatively simple systems with limited task sets. We propose a method to assign offsets to tasks across a mode-change, using a metaheuristic approach (genetic algorithms). This method allows the configuration and/or the minimization of the worst-case latency of a mode-change. The latency of a mode change is a critical parameter to be minimized, since during the mode change the system offers limited functionality due to the fact that the task set is still incomplete. We also provide a classification of mode changes according to applications¿ requirements. This classification was useful, once applied to a number of case studies, both to validate the configuration approach and to a greater extent to show that the method is flexible in that it can accommodate a wide variety of types of mode-changes / Mestrado / Mestre em Tecnologia

Um melhor escalonamento em simulação distribuída é fundamental para uma execução mais rápida e eficiente. O projeto desenvolvido tem como objetivo a avaliação de desempenho de políticas de escalonamento convencionais e específicas para Simulação Distribuída (SD), apresentando uma comparação do desempenho destas duas abordagens. Análises das pesquisas feitas na área mostram que não existe avaliação semelhante. Assim, este trabalho tem a importante contribuição de demonstrar as vantagens e desvantagens do uso de políticas tradicionais em relação às específicas em SD. Para execução das simulações foi utilizada a ferramenta Warped, que está descrita nesta dissertação. Foram desenvolvidas e implementadas novas técnicas de escalonamento que utilizam os resultados da simulação em execução, assim executam um melhor balanceamento de carga. Para o desenvolvimento deste projeto foi necessária uma revisão bibliográfica envolvendo conceitos de simulação distribuída com seus respectivos protocolos de sincronização, escalonamento de processos específicos para programas de SD e políticas tradicionais. Com este estudo soma-se como contribuição deste trabalho uma nova classificação das políticas específicas para SD que utilizam protocolo otimista / A bestter scheduling in distributed simulation is fundamental to a fast and efficient execution. The developed project has as objective the evaluation of performance of conventional and specific politics of scheduling for Distributed Simulation (DS), presenting a comparison of the performance of these two boardings. Analyses of the research done in the area show that similar evaluation does not exists. Thus, this work has the important contribution to demonstrate to the advantages and disadvantages of the use of traditional politics in relation to the specific ones in DS. For execution of the simulations the Warped tool was used, that is described in this work. They had been developed and implemented new techniques of scheduling that use the results of the simulation in execution, thus they execute one better load balancing. For the development of this project a bibliographical revision was necessary involving concepts of simulation distributed with its respective protocols of synchronization, traditional scheduling of specific processes for DS programs and politics. With this study a new classification of the specific politics for DS is added as contribution of this work that use optimistical protocol

Em relação aos significativos resultados em Qualidade de Serviço (QoS) para servidores Web, existem ainda muitos problemas não resolvidos. Enquanto as abordagens atuais se limitam a prover QoS relativa através de diferenciação de serviço, este projeto apresenta e compara três modelos que tem por objetivo prover QoS absoluta para um array de servidores Web heterogêneos por meio de uma arquitetura de escalonamento ortogonal: A Multiple Queue (MQ), a Single Queue (SQ) e a Dynamic Single Queue (DSQ). A MQ consiste em receber a requisição HTTP e enviá-la para o servidor escolhido do array de servidores através do balanceamento de carga. A SQ e a DSQ possuem uma única fila gerenciada de forma centralizada. Enquanto a SQ envia a requisição somente quando o servidor esta livre, a DSQ seleciona o servidor com mais curto tempo de término mediante o uso de filas virtuais. Os modelos foram simulados considerando diferentes parâmetros e configurações para o ambiente. A avaliação de desempenho da arquitetura ortogonal demonstra que a mesma provê um bom desempenho na provisão de QoS absoluta com relação as mudanças instantâneas das cargas de trabalho no ambiente Web. Esta pesquisa estende os resultados da politica de escalonamento chamada EBS, concebida para provisão de garantias de tempo de resposta estocásticas em ambientes interativos online, especificamente para os servidores Web. Os resultados demonstram que a combinação da EBS na política de fila com a disciplina de recurso proposta neste trabalho é superior às outras combinações examinadas. Um modelo de política adaptativa é também introduzido / Despite the significant body of results in Quality of Service (QoS) for Web-Servers, many real-world problems are not easily supported. While the current approaches limit to provide relative QoS through service differentiation, this work presents and compares three models aiming at providing absolute QoS to Web Server on heterogeneous cluster by means of an Orthogonal Scheduling Architecture: The Multiple Queue (MQ), the Single Queue (SQ) and the Dynamic Single Queue (DSQ). The MQ consists in receiving the HTTP requests and delivering them for the selected processor in the server array to balance the load. SQ and DSQ have only one queue being managed by a central server. While SQ sends requests to the first free processors, the DSQ selects the processor with the minimun completion time with the aid of a virtual queue. The models were simulated considering different parameters and configurations for the environment. Performance evaluation of the Orthogonal Architecture demonstrates that it performs well in providing absolute QoS in face of instantaneous changes in the workloads. This work extends the results of a scheduling policy named EBS, tailored for providing stochastic response-time guarantees in online interactive systems, specifically for Web servers. Results show that the combination of EBS as the queue discipline with the resource discipline proposed in this work outperforms the other studied. An adaptive policy model is also introduced

Este trabalho apresenta o projeto e a implementação da política de escalonamento com suporte à migração de processos JUMP. A migração de processos é uma ferramenta importante que complementa a alocação inicial realizada pela política de escalonamento em um ambiente paralelo distribuído, permitindo um balanceamento de carga dinâmico e mais refinado, resultando em um melhor desempenho do ambiente e menor tempo de resposta das aplicações paralelas distribuídas. A nova política unifica a alocação inicial e migração de processos em um único algoritmo, de forma a compartilhar decisões para o objetivo comum de prover um melhor desempenho para aplicações de uso intensivo de processamento em clusters heterogêneos. A política é implementada sobre o ambiente de escalonamento flexível e dinâmico AMIGO, adaptado para o suporte à migração de processos. A avaliação de desempenho mostrou que a nova política oferece ganhos expressivos nos tempos de resposta quando comparada às outras duas políticas de escalonamento implementadas no AMIGO, em quase todos os cenários, para diversas aplicações e diversas situações de carga do ambiente / This work presents the project and implementation of the scheduling policy with process migration support JUMP. Process migration is an important tool that complements the initial placement performed by the scheduling policy in a distributed parallel environment, allowing for dynamic and more refined load balancing, resulting in better performance of the environment and shorter response time for distributed parallel applications. The new policy unifies initial placement and process migration in a single algorithm, enabling the sharing of decisions for the common goal of providing a better performance for CPU-bound applications in heterogeneous clusters. The policy is implemented over the dynamical and flexible environment AMIGO, adapted in order to support process migration. Performance evaluation showed that the new policy offers expressive gains in response times when compared to other two scheduling policies implemented in AMIGO in almost all scenarios, for different applications and different environment load situations

Recentes pesquisas têm investigado modelos de garantia de desempenho baseados em restrições temporais, parametrizadas pela especificação de limites superiores de tempo médio de resposta. Este trabalho estende o desenvolvimento da política de escalonamento de temporeal EBS, aplicável a esse problema, apresentando um mecanismo de controle de admissão de requisições em aplicações com tais requisitos. A abordagem baseia-se em um método adaptativo capaz de administrar o nível de degradação do sistema, de forma a isolar o efeito do comportamento de um usuário sobre a qualidade de serviço oferecida aos demais usuários. Também é proposta uma modificação na implementação do algoritmo originalmente definido para a EBS, de forma a diminuir sua complexidade temporal. Resultados de simulação demonstram a efetividade dos mecanismos propostos / In recent research works performance guarantee models based on temporal constraints with specified response-time upper bounds have been investigated. This work extends the development of the EBS real-time scheduling policy, applicable to this problem, by proposing an admission control mechanism. The introduced approach is based on an adaptive model which, based on the system degradation level, tries to isolate the impact of the behavior of a given user upon the quality of service offered to the other users. Its also proposed a new algorithm to reduce the complexity order of the original EBS implementation. Simulation results illustrate the effectiveness of proposed methods

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura. / The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.

Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA), um algoritmo de aproximação para o problema de escalonamento de processos orientado a sistemas. Esse algoritmo foi baseado em um modelo de otimização matemática proposto no contexto desta tese. Esse modelo considera os comportamentos de processos e recursos a fim de quantificar a qualidade de soluções de escalonamento. O funcionamento do MHSA envolve a construção de uma árvore min-heap, em que os nós representam computadores e as chaves de ordenação correspondem aos tempos de fila, i.e., ocupação dos computadores. Apesar de esse algoritmo primordialmente reduzir o tempo de execução (ou makespan) de aplicações, essa estrutura em árvore permite que qualquer computador que ocupe o nó raiz receba cargas, o que favorece a ocupação de recursos e, portanto, sua orientação a sistemas. Esse algoritmo tem complexidade assintótica de pior caso igual a O(\'log IND. 2 m\'), em que m corresponde ao número de computadores do sistema. Sua razão de aproximação foi estudada para ambientes distribuídos heterogêneos com e sem a presença de comunicação entre processos, o que permite conhecer, a priori, o nível mínimo de qualidade alcançado por suas soluções. Experimentos foram conduzidos para avaliar o algoritmo proposto e compará-lo a outras propostas. Os resultados confirmam que o MHSA reduz o tempo dispendido na obtenção de boas soluções de escalonamento / One of the most important challenges involved in the design of grid computing systems is process scheduling, which maps applications into the available computers in attempt to reduce the application execution time, or maximize resource utilization. The literature of Distributed Systems usually deals with these two objectives separately, supporting the application-centric and the resourcecentric scheduling, respectively. More recently, a third approach referred to as system-centric scheduling has emerged which attempts to optimize both objectives in conjunction. Heuristic-based and approximation-based algorithms have been proposed to address this third type of scheduling. Heuristics aim to find good solutions at acceptable time constraints, without guaranteeing solution quality. On the other hand, approximation-based algorithms provide optimal solution bounds, however they are more difficult to design what makes them available only to simple scenarios. The need for approximation-based algorithms to support system-centric scheduling has motivated this thesis which presents Min Heap-based Scheduling Algorithm (MHSA). This approximation algorithm is based on a mathematical optimization model, also proposed in this work, which considers process and resource behaviors to measure the quality of scheduling solutions. MHSA builds a min-heap data structure in which tree nodes represent computers and sorting keys correspond to queuing times, i.e., computer workloads. Besides this algorithm primarily reduces application execution times (also referred to as makespan), its data structure allows any computer assume the root node and, consequently, receive workloads, what favors resource utilization. This algorithm has the worst-case time complexity equals to O(\'log IND. 2 m\'), in which m represents the number of system computers. Its approximation ratio was analyzed to heterogeneous distributed systems considering bag-of-tasks and communication-intensive applications. Having this ratio, we know the minimum quality level provided by every scheduling solution. Experiments were performed to compare MHSA to others. Results confirm MHSA reduces the time spent to obtain good quality scheduling solutions