111 |
Redução do impacto das reservas antecipadas sobre as imediatas em redes de circuito dinâmicoMoura, Diêgo Braga Monteiro de 04 March 2015 (has links)
Submitted by Santos Davilene (davilenes@ufba.br) on 2016-05-30T13:27:29Z
No. of bitstreams: 1
cópia digital.pdf: 1814097 bytes, checksum: 5eecff3c4c86a1bc41ead01296009fea (MD5) / Made available in DSpace on 2016-05-30T13:27:29Z (GMT). No. of bitstreams: 1
cópia digital.pdf: 1814097 bytes, checksum: 5eecff3c4c86a1bc41ead01296009fea (MD5) / As redes de circuito dinâmico fazem parte de uma das tecnologias da Internet do Futuro e são caracterizadas por oferecer uma boa qualidade de serviço a um baixo custo. Através delas é possível aumentar a rapidez no estabelecimento dos circuitos, além de diminuir o custo de gerenciamento. A maioria dessas redes são voltadas para aplicações elásticas e tem os seus recursos alocados no modo de reserva antecipada. Entretanto, é muito provável que alocações de recurso no modo reserva imediata coexistiam com as
reservas antecipadas. Além disso, diferentes tipos de aplicações poderão ser suportadas, o que torna o problema de alocação de banda às requisições altamente desafiador e de fundamental importância para o seu bom desempenho.Até onde se tem conhecimento, o único algoritmo de alocação de largura de banda
da literatura possui dificuldades em permitir uma coexistência entre diferentes tipos de aplicações. Este trabalho concebe um novo algoritmo para alocação de banda em redes
de circuito dinâmico denominado de Balanceamento de Banda Residual (BBR). O BBR explora características específicas de aplicações elásticas e procura balancear a banda residual dentro do intervalo de uma requisição. Adicionalmente se propõe uma estratégia de gerenciamento de recurso intitulada de Particionamento Dinâmico com Preempção com o objetivo de diminuir as diferenças de probabilidade de bloqueio entre as reservas antecipadas e as imediatas. Experimentos através de simulação mostram que o BBR alcança uma menor probabilidade
de bloqueio comparado à heurística comumente utilizada na literatura. Além
disso, o Particionamento Dinâmico com Preempção diminui o impacto que as reservas antecipadas causam sobre as imediatas sem comprometer um boa taxa de utilização da rede.
|
112 |
Propriedades métricas de sistemas multiparamétricos discretosTorrico Chávez, César Abraham January 2008 (has links)
Neste trabalho estudamos propriedades métricas de certas estruturas recentemente descobertas em diagramas de fase, chamadas de conjuntos tipo de Mandelbrot. Tais estruturas (conjuntos) são importantes pois aparecem repetidamente em sistemas dinâmicos, em particular, em equações diferenciais que descrevem lasers e outros modelos físicos. De particular interesse, são escalonamentos (scalings) de codimensão 2, i.e. que dependem da variação simultânea de dois parâmetros físicos para serem observados. Através da obtenção de expressões exatas dos pontos de nascimento de domínios de estabilidade {"fiores de cactus'?, conseguimos demonstrar analiticamente que a velocidade de acumulação dos domínios convergepara um valor limite constante igual à unidade. Outras taxas de convergência tais como, por exemplo, a orientação do eixo dos domínios com respeito à horizontal, a diminuição das alturas e das áreas dos domínios, também convergem para a unidade. Tal convergência foi também por nós encontrada no conjunto de Mandelbrot. Em ambos casos as convergências obedecem uma lei de potência com expoentes inteiros, em forte contraste com a convergência típica de Feigenbaum, que também segue uma lei de potências, porém com expoente fracionário. Por razões discutidas em detalhe dentro do trabalho, conjecturamos ser o escalonamento unitário de carácter geral sempre que se tenham fam{lias de fases periódicas participando de um processo de acumulação com adição de períodos. Observamos que os conjuntos de números racionais (números de rotação) que rotulam as infinitas fam{lias de fiores, (fases periódicas) nos conjuntos tipo-Mandelbrot, também exibem a mesma convergência unitária. Tal fato nos leva a crer que, dum ponto de vista teórico, este "scaling"parece originar-se de propriedades métricas dos racwna%s. Além disto, complementamos o estudo das propriedades métricas dos conjuntos tipo-Mandelbrot com um estudo detalhado da sua estrutura interna, via multiplicadores das órbitas periódicas estáveis, reais e complexas. Observamos que a parte real (imaginária) dos multiplicadores define certos eixos de simetria transversal (longitudinal) em cada fior, que podem ser tomados como uma espécie de "sistema de coordenadas cartesiano". Em tal sistema, observamos um ordenamento simétrico dos números de rotação das fiores, de maneira similar ao ordenamento dos números racionais no círculo unitário. Mostrando desta forma que o interior de cada fior é isomorfo ao círculo unitário. A medida que nos aproximamos das zonas de transição isoperiódica (de órbitas complexas para reais), observamos uma rotação dos eixos transversais locais de cadafior em direção aos eixos longitudinais, até ambosficarem alinhados, no limite da acumulação. Esta mudança não ocorre nos círculos do conjunto de Mandelbrot, onde ambos eixos permanecem perpendiculares até alcançar um tamanho nulo no ponto raiz. Isto parece mostrar que, apesar dos conjuntos Mandelbrot e tipo-Mandelbrot compartilharem várias propriedades métricas, a ausência de conectividade local nestes últimos modifica significativamente sua estrutura interna. / In this work we study scaling proprerties of certain structures recently found in phase diagrams, called as Mandelbrot-like sets. Such structures (sets) are important becausethey appear repeatedly in dinamical systems, particularly, in differentials equations that describe lasers and others physical models. Df particular interest, are scalings of codimension-2, i.e., that depend on the simultaneous variation of two physical parameters to be observed. Through the obtention of exact expressions for the birth points of stability domains ("cactus flowers''), we proved analitically that the accumulation rate of the domains converges to a constant limit value equal to unity. Another convergence rates such as, for example, orientation of the domain axis with respect to the horizontal, the decrease of domains heights and areas, also converge to unity. We also founded this convergence in the Mandelbrot set. In both cases, the convergences obey a power law with integer exponents, in contrast with the typical Feigenbaum convergence, that also follows a power law but with fraccionary exponent. For the reasons discuted in detail along the work, we conjecture this unitary scaling to have a general caracter always that one have families of periodic fases participating in a process of accumulation with period adding. We observed that the rational numbers sets that label the infinity flower's families (periodic phases), in the Mandelbrot-like sets, also exhibit the same rate of convergence. This fact lead us to believe, from a theoretical point of view, that this scaling seems to arise from the metrical properties of rationals. Besides this, we complemented the study of scalings in the Mandelbrot-like sets with a detailed study of their internal structure, via multipliers of the stable periodic orbits, both real and complexo We observed that the real (imaginary) part of multipliers define certain transversal (longitudinal) axis of simetry en each flower, that can be take as a sort of local "cartesian coordinates system". In such system, we observe a symmetric ordering of the rotation numbers of flowers, like the ordering of rational numbers in the unitary circle. Showing of this form that the inner of each flower is isomorphic to the unitary circle. As we aproximate to the isoperiodic transition zones (of complexto realorbits),wefounded a rotationof the transversallocalaxis of each flower toward the longitudinal axis, until both axis stay aligned, at the accumulation limito This rotation does not occur inside the Mandelbrot set circles, where both axis remain perpendicular until they reach a null size at the root point. This seems to show that, in spite of Mandelbrot and Mandelbrot-like sets to share several metric properties, the lack of local conectivity in the latest modifies significantly their internal structure.
|
113 |
Uma Abordagem de escalonamento adaptativo no ambiente Real-Time CORBACervieri, Alexandre January 2002 (has links)
CORBA vem se tornando o middleware padrão no desenvolvimento de aplicações distribuídas, tornando-as independentes de plataforma e linguagem. Ele tem sido utilizado também em aplicações de tempo real através de sua extensão para tempo real, o RT-CORBA. Apesar desta extensão ter conseguido reduzir vários dos problemas do CORBA no que se refere ao não-determinismo e falta de garantias temporais, ainda há muito estudo na área de mecanismos de escalonamento utilizados. Assim, este trabalho tem por objetivo apresentar uma proposta de escalonamento adaptativo no ambiente Real-Time CORBA. Nesta proposta o período das tarefas é controlado, variando dentro de uma faixa pré-estabelecida com o propósito de reduzir o atraso médio das tarefas da aplicação.
|
114 |
Escalonamento adaptativo para o Apache Hadoop / Adaptative scheduling for Apache HadoopCassales, Guilherme Weigert 11 March 2016 (has links)
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Many alternatives have been employed in order to process all the data generated by
current applications in a timely manner. One of these alternatives, the Apache Hadoop,
combines parallel and distributed processing with the MapReduce paradigm in order to
provide an environment that is able to process a huge data volume using a simple
programming model. However, Apache Hadoop has been designed for dedicated and
homogeneous clusters, a limitation that creates challenges for those who wish to use the
framework in other circumstances. Often, acquiring a dedicated cluster can be
impracticable due to the cost, and the acquisition of reposition parts can be a threat to
the homogeneity of a cluster. In these cases, an option commonly used by the
companies is the usage of idle computing resources in their network, however the
original distribution of Hadoop would show serious performance issues in these
conditions. Thus, this study was aimed to improve Hadoop’s capacity of adapting to
pervasive and shared environments, where the availability of resources will undergo
variations during the execution. Therefore, context-awareness techniques were used in
order to collect information about the available capacity in each worker node and
distributed communication techniques were used to update this information on
scheduler. The joint usage of both techniques aimed at minimizing and/or eliminating
the overload that would happen on shared nodes, resulting in an improvement of up to
50% on performance in a shared cluster, when compared to the original distribution, and
indicated that a simple solution can positively impact the scheduling, increasing the
variety of environments where the use of Hadoop is possible. / Diversas alternativas têm sido empregadas para o processamento, em tempo hábil, da
grande quantidade de dados que é gerada pelas aplicações atuais. Uma destas
alternativas, o Apache Hadoop, combina processamento paralelo e distribuído com o
paradigma MapReduce para fornecer um ambiente capaz de processar um grande
volume de informações através de um modelo de programação simplificada. No
entanto, o Apache Hadoop foi projetado para utilização em clusters dedicados e
homogêneos, uma limitação que gera desafios para aqueles que desejam utilizá-lo sob
outras circunstâncias. Muitas vezes um cluster dedicado pode ser inviável pelo custo de
aquisição e a homogeneidade pode ser ameaçada devido à dificuldade de adquirir peças
de reposição. Em muitos desses casos, uma opção encontrada pelas empresas é a
utilização dos recursos computacionais ociosos em sua rede, porém a distribuição
original do Hadoop apresentaria sérios problemas de desempenho nestas condições.
Sendo assim, este estudo propôs melhorar a capacidade do Hadoop em adaptar-se a
ambientes, pervasivos e compartilhados, onde a disponibilidade de recursos sofrerá
variações no decorrer da execução. Para tanto, utilizaram-se técnicas de sensibilidade ao
contexto para coletar informações sobre a capacidade disponível nos nós trabalhadores e
técnicas de comunicação distribuída para atualizar estas informações no escalonador. A
utilização conjunta dessas técnicas teve como objetivo a minimização e/ou eliminação
da sobrecarga que seria causada em nós com compartilhamento, resultando em uma
melhora de até 50% no desempenho em um cluster compartilhado, quando comparado
com a distribuição original, e indicou que uma solução simples pode impactar
positivamente o escalonamento, aumentando a variedade de ambientes onde a utilização
do Hadoop é possível.
|
115 |
Matheurísticas para o problema de custo de disponibilidade de recursos com múltiplos modosProcópio, Lettiery D’Lamare Portela 02 February 2016 (has links)
Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-16T13:17:01Z
No. of bitstreams: 1
arquivototal.pdf: 2304908 bytes, checksum: 271eaf53cd7aa8cf16b5876ac5c7a2e5 (MD5) / Made available in DSpace on 2017-08-16T13:17:02Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 2304908 bytes, checksum: 271eaf53cd7aa8cf16b5876ac5c7a2e5 (MD5)
Previous issue date: 2016-02-02 / This paper discribes the construction of two Matheuristics based on Genetic Algorithm and
Particle Swarm Optimization in order to solve the Availability of Cost Problem Resources
with Multi-Modes. Inspired by the need to balance the use of renawable resources with the
total time (makespan), by scheduling the activities with its various implementations executions modes present in the project. Tests show the effectiveness in te use of mathematical programming adapted to the Genetic Algorithm. / Este trabalho descreve a construção de duas Matheurística baseadas em Algoritmos
Genéticos e na Otimização por Enxame de Partícula, afim de solucionar o Problema de
Custo de Disponibilidade de Recursos com Múltiplos Modos. Inspirado na necessidade
de balancear a utilização de recursos renováveis com o tempo total (makespan), através do
escalonamento das atividades com seus diversos modos de execução presentes no projeto.
Testes revelam a eficácia na utilização da programação matemática adaptada com o Algoritmo
Genético.
|
116 |
Contribui??es em escalonamento e an?lise de desempenho de redes WirelessHARTNobre, Marcelo Henrique Ramalho 23 November 2015 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-07-06T19:34:30Z
No. of bitstreams: 1
MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-07-06T22:04:01Z (GMT) No. of bitstreams: 1
MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5) / Made available in DSpace on 2016-07-06T22:04:01Z (GMT). No. of bitstreams: 1
MarceloHenriqueRamalhoNobre_TESE.pdf: 4355071 bytes, checksum: 05cf1b490e598685ec4e7b682423a8d9 (MD5)
Previous issue date: 2015-11-23 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / A comunica??o sem fios ? uma tend?ncia no ambiente industrial atualmente e nessa tend?ncia temos o WirelessHART como uma das principais tecnologias. Com essa situa??o, ? natural que melhorias no desempenho sejam buscadas e um dos principais caminhos para isso passa pelo desenvolvimento de algoritmos de escalonamento e roteamento. Nesta tese ? apresentado uma revis?o da literatura sobre as principais solu??es em escalonamento e roteamento desenvolvidas especificamente para a tecnologia WirelessHART. Al?m disso prop?e um novo Algoritmo de escalonamento chamando Escalonamento Flow que visa melhorar aspectos de flexibilidade e de utiliza??o do superframe. Para prop?sitos de valida??o, ? desenvolvido e utilizado um m?dulo de simula??o para o Network Simulator 3 (NS-3) que modela aspectos como posicionamento, atenua??o de sinal e consumo de energia al?m de prover simula??es mais exatas por meio de configura??es de erro individuais para cada link. Este m?dulo tamb?m possibilita a gera??o do superframe de escalonamento a partir do grafo de roteamento utilizando os algoritmos Flow e Han. Para a valida??o do novo algoritmo s?o realizados experimentos comparativos entre o algoritmo Han e algoritmo Flow, avaliando crit?rios de aloca??o de links, delay e taxa de ocupa??o de superframe. Para valida??o da camada f?sica do m?dulo de simula??o, o escalonamento e o roteamento s?o configurados estaticamente e s?o desenvolvidos experimentos de confiabilidade e consumo de energia com topologias validadas na literatura e com varia??es de probabilidades de erro. / Wireless Communication is a trend in the industrial environment nowadays and on
this trend, we can highlight the WirelessHART technology. In this situation, it is natural
the search for new improvements in the technology and such improvements can be related
directly to the routing and scheduling algorithms. In the present thesis, we present a
literature review about the main specific solutions for Routing and scheduling for WirelessHART.
The thesis also proposes a new scheduling algorithm called Flow Scheduling
that intends to improve superframe utilization and flexibility aspects. For validation purposes,
we develop a simulation module for the Network Simulator 3 (NS-3) that models
aspects like positioning, signal attenuation and energy consumption and provides an link
individual error configuration. The module also allows the creation of the scheduling superframe
using the Flow and Han Algorithms. In order to validate the new algorithms,
we execute a series of comparative tests and evaluate the algorithms performance for link
allocation, delay and superframe occupation. In order to validate the physical layer of
the simulation module, we statically configure the routing and scheduling aspects and
perform reliability and energy consumption tests using various literature topologies and
error probabilities.
|
117 |
Problema das sequ?ncias justas ponderadasPess?a, Bruno Jefferson de Sousa 15 December 2017 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2018-02-21T21:29:05Z
No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-02-22T22:38:00Z (GMT) No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5) / Made available in DSpace on 2018-02-22T22:38:00Z (GMT). No. of bitstreams: 1
BrunoJeffersonDeSousaPessoa_TESE.pdf: 1029802 bytes, checksum: fb7e1bbf01b30106e4b0a64511f955d1 (MD5)
Previous issue date: 2017-12-15 / Problemas de escalonamento aos quais s?o impostas restri??es relativas ?s dist?ncias
temporais entre sucessivas execu??es de uma mesma tarefa possuem um grande n?mero
de aplica??es, que variam desde o escalonamento de tarefas em sistemas de tempo real ?
produ??o de autom?veis em uma linha de montagem. O presente trabalho apresenta um
novo problema de otimiza??o, denominado de Problema das Sequ?ncias Justas Ponderadas
(PSJP), que faz parte dessa classe de problemas. Al?m do estudo da complexidade
computacional do PSJP, ? apresentada uma formula??o matem?tica baseada em programa??o
linear inteira mista e uma s?rie de cortes que aprimoram sua resolu??o via m?todos
exatos. Para resolv?-lo, foram elaborados um m?todo iterativo que reduz o n?mero de vari?veis
da formula??o proposta e uma solu??o heur?stica desenvolvida a partir da combina??o
de meta-heur?sticas cl?ssicas da literatura. Experimentos computacionais mostram
que, para um dado limite de tempo, as abordagens propostas aumentam significativamente
o n?mero de inst?ncias resolvidas, preservando-se a qualidade das solu??es. / Scheduling problems on which constraints are imposed with regard to the temporal
distances between successive executions of the same task have numerous applications,
ranging from task scheduling in real-time systems to automobile production on a mixedmodel
assembly line. This paper introduces a new NP-hard optimization problem belonging
to this class of problems, namely the Weighted Fair Sequences Problem (WFSP). In
addition to the study of the computational complexity of the WFSP, we present a mathematical
formulation based on mixed-integer linear programming as well as a serie of cuts
that improve the problem resolution via exact methods. To solve the WFSP, we propose
an iterative method that greatly reduces the number of variables in the WFSP formulation
and a heuristic solution developed from the combination of classical metaheuristics from
the literature. Computational experiments show that, for a given time limit, the proposed
approaches significantly increase the number of instances solved, preserving the quality
of the solutions.
|
118 |
Um estudo comparativo do desempenho das disciplinas de escalona-mento WRR e WF²Q no suporte à QoS em ambientes de redes de acesso IEEE 802.16Silva, Wyllian Bezerra da 03 March 2008 (has links)
The incipient technology of wireless access networks of the IEEE 802.16 Standard aggregates to the BWA systems many advantages over concur technologies, such as radio signal wide coverage, even in difficult access regions or needy of conventional infrastructure of network, as the case of some urban and rural areas of Brazil. Moreover, enables access to the Internet in last mile with high transmission rates, attending to the more several requisites of the data, voice and video applications with minor cost in comparison to others available alternatives. Meanwhile, this technology not specifies how the packages or service flows should be the scheduled in the MAC layer. Thus, this study compares the use of mechanisms for scheduling that approximates the ideal GPS scheduler to support the provision of QoS on IEEE 802.16 PMP network. The modeling and simulation based results evidence that the considered mechanisms WRR and WF2Q get good results in the support to the provision of QoS in this network. / A incipiente tecnologia de redes de acesso sem fio do Padrão IEEE 802.16 agrega aos sistemas BWA inúmeras vantagens sobre as tecnologias concorrentes, tais como ampla cobertura do sinal de rádio, mesmo em regiões de difícil acesso ou carentes de infra-estrutura de rede convencional, como é o caso de algumas áreas urbanas e rurais brasileiras. Além disso, permite estabelecer a parte final da infra-estrutura de conexão de banda larga com altas taxas de transmissão, atendendo aos mais diversos requisitos das aplicações de dados, voz e vídeo a um menor custo em comparação com as outras alternativas disponíveis. Entretanto, o Padrão IEEE 802.16 não determina a forma como devem ser escalonados os pacotes ou fluxos de serviço na camada MAC desta tecnologia. Assim, neste trabalho compara-se a utilização de mecanismos de escalonamento que se aproximam do escalonador ideal GPS para o suporte à provisão de QoS em uma rede de acesso IEEE 802.16 PMP. Os estudos comparativos baseados em modelagem e simulação mostraram que os mecanismos WRR e WF2Q conduzem a bons resultados no suporte à provisão de QoS nesta rede. / Mestre em Ciências
|
119 |
Proposta de um esquema para a provisão de QoS no padrão IEEE 802.16 / Proposal of Framework for QoS Provisioning in IEEE 802.16 NetworksRosa, Eduardo Castilho 07 July 2011 (has links)
Fundação de Amparo a Pesquisa do Estado de Minas Gerais / The IEEE 802.16 standard is designed to provide wireless broadband connectivity for
both xed and mobile users in a wide coverage area with high rates of data transfer. The
main feature incorporated by the IEEE 802.16 standard is the quality of service (QoS)
provisioning by means of packets scheduling, trac policing and connection admission
control (CAC). Since the IEEE 802.16 standard does not dene the policies for admission
control and packet scheduling, in this paper we propose a QoS provisioning mechanism
which consists of a novel scheduling algorithm for uplink trac and a dynamic CAC
scheme for IEEE 802.16 networks. The proposed scheduling mechanism serves the requests
queues in a cyclical mode and is based on a static bandwidth reservation mechanism in
order to separate the real-time and non real time ows. The CAC policy is proposed for
the real-time service class with variable rate and is based on a delay prediction scheme
which uses the buer size information in SSs. Through modeling and simulation, we
evaluated various network scenarios in order to test the eciency of CAC and scheduling
mechanism. From the results, it was found that the proposed mechanism is able to meet
the maximum delay requirements of the maximum delay bound for real time ows and
minimum throughput for streams of non-real time. Moreover, it was found that the
proposed mechanism is able to avoid the bandwidth starvation of low priority ows. / O padrão IEEE 802.16 é designado para prover conectividade em banda larga sem
o para usuários xos e móveis em uma ampla área de cobertura com altas taxas de
transferência de dados. A principal característica incorporada por esse padrão é a provis
ão de qualidade de serviço (QoS) aos usuários nais, garantida por meio de algoritmos
para escalonamento de pacotes tanto na estação base como nas estações de assinantes e
também políticas para controle de admissão de conexões (CAC). Pelo fato do padrão não
especicar políticas para a implementação desses mecanismos, propõe-se nesse trabalho
um novo algoritmo de escalonamento uplink na estação base que é capaz de atender as
principais classes de serviços denidas pelo padrão e também uma política de CAC din
âmica baseada em predição de atraso. O mecanismo de escalonamento proposto atende
as las de requisições de forma cíclica e baseia-se em um esquema de reserva estática de
largura de banda para separar os uxos de tempo real, não tempo real com o requisito de
taxa mínima e não tempo real sem requisitos de vazão (tráfego de melhor esforço). Já a
política de CAC foi proposta para a classe de serviço de tempo real com taxa variável e
baseia-se na predição do atraso médio calculado de acordo com o estado de ocupação dos
buers nas estações assinantes. Avaliou-se, por meio de modelagem e simulação, vários
cenários de redes com o intuito de testar a eciência do mecanismo de escalonamento e
CAC. Pelos resultados obtidos, vericou-se que o mecanismo proposto é capaz de atender
os requisitos de atraso máximo limitado para uxos de tempo real e vazão mínima para
uxos de não tempo real. Além disso, constatou-se que o mecanismo proposto é capaz de
evitar o bandwidth starvation dos uxos de baixa prioridade. / Mestre em Ciências
|
120 |
Essays on urban bus transport optimizationGuedes, Pablo Cristini January 2017 (has links)
Nesta tese, nós apresentamos uma compilação de três artigos de otimização aplicados no contexto de transporte urbano de ônibus. O principal objetivo foi estudar e implementar heurísticas com base em Pesquisa Operacional para otimizar problemas de (re)escalonamento de veículos off-line e on-line considerando várias garagens e frota heterogênea. No primeiro artigo, foi proposta uma abordagem heurística para o problema de escalonamento de veículos múltiplas garagens. Acreditamos que as principais contribuições são o método de geração de colunas para grandes instâncias e as técnicas de redução do espaço de estados para acelerar as soluções. No segundo artigo, adicionamos complexidade ao considerar a frota heterogênea, denotada como multiple depot vehicle type scheduling problem (MDVTSP). Embora a importância e a aplicabilidade do MDVTSP, formulações matemáticas e métodos de solução para isso ainda sejam relativamente inexplorados. A principal contribuição desse trabalho foi o método de geração de colunas para o problema com frota heterogênea, já que nenhuma outra proposta na literatura foi identificada no momento pelos autores. Na terceira parte desta tese, no entanto, nos concentramos no reescalonamento em tempo real para o caso de quebras definitivas de veículos. A principal contribuição é a abordagem eficiente do reescalonamento sob uma quebra. A abordagem com redução de espaço de estados, solução inicial e método de geração de colunas possibilitou uma ação realmente em tempo real. Em menos de cinco minutos, reescalonando todas as viagens restantes. / In this dissetation we presented a three articles compilation in urban bus transportation optimization. The main objective was to study and implement heuristic solutions method based on Operations Research to optimizing offline and online vehicle (re)scheduling problems considering multiple depots and heterogeneous fleet. In the first paper, a fast heuristic approach to deal with the multiple depot vehicle scheduling problem was proposed. We think the main contributions are the column generation framework for large instances and the state-space reduction techniques for accelerating the solutions. In the second paper, we added complexity when considering the heterogeneous fleet, denoted as "the multiple-depot vehicle-type scheduling problem" (MDVTSP). Although the MDVTSP importance and applicability, mathematical formulations and solution methods for it are still relatively unexplored. We think the main contribution is the column generation framework for instances with heterogeneous fleet since no other proposal in the literature has been identified at moment by the authors. In the third part of this dissertation, however, we focused on the real-time schedule recovery for the case of serious vehicle failures. Such vehicle breakdowns require that the remaining passengers from the disabled vehicle, and those expected to become part of the trip, to be picked up. In addition, since the disabled vehicle may have future trips assigned to it, the given schedule may be deteriorated to the extent where the fleet plan may need to be adjusted in real-time depending on the current state of what is certainly a dynamic system. Usually, without the help of a rescheduling algorithm, the dispatcher either cancels the trips that are initially scheduled to be implemented by the disabled vehicle (when there are upcoming future trips planned that could soon serve the expected demand for the canceled trips), or simply dispatches an available vehicle from a depot. In both cases, there may be considerable delays introduced. This manual approach may result in a poor solution. The implementation of new technologies (e.g., automatic vehicle locators, the global positioning system, geographical information systems, and wireless communication) in public transit systems makes it possible to implement real-time vehicle rescheduling algorithms at low cost. The main contribution is the efficient approach to rescheduling under a disruption. The approach with integrated state-space reduction, initial solution, and column generation framework enable a really real-time action. In less than five minutes rescheduling all trips remaining.
|
Page generated in 0.0171 seconds