Spelling suggestions: "subject:"queueing"" "subject:"gueueing""
221 |
Limit theorems for limit order booksPaulsen, Michael Christoph 21 August 2014 (has links)
Im ersten Teil der Dissertation wird ein diskretes stochastisches zustandsabhängiges Modell eines zweiseitigen Limit Orderbuchs als bestehend aus den Zustandsgrößen bester Bidpreis (Geldkurs), bester Askpreis (Briefkurs) und vorhandener Kauf- bzw. Verkaufsdichte definiert. Für eine einfache Skalierung mit zwei Zeitskalen wird ein Grenzwertsatz bewiesen. Die Veränderungen der besten Bid- und Askpreise werden im Sinne des Gesetzes der großen Zahlen skaliert und dies entspricht der langsameren Zeitskala. Das Platzieren bzw. Stornieren der Limitorder findet auf der schnelleren Zeitskala statt. Der Grenzwertsatz besagt, dass die fundamentalen Zustandsgrößen, gegeben Regularitätsbedingungen der einkommenden Order, fast sicher zu einem stetigen Limesmodell konvergieren. Im Limesmodell sind der beste Bidpreis und der beste Askpreis die eindeutigen Lösungen von zwei gekoppelten gewöhnlichen DGLen. Die Kauf- und Verkaufsdichten sind jeweils als eindeutige Lösungen von linearen hyperbolischen PDGLen, die anhand der Erwartungswerte der einkommenden Orderparameter festgelegt sind, gegeben. Die Lösungen sind in geschlossener Form erhältlich. Im zweiten Teil wird ein funktionaler zentraler Grenzwertsatz d.h. ein Invarianzprinzip für ein vereinfachtes Modell eines Limitorderbuches bewiesen. Unter einer natürlichen Skalierung konvergiert der zweidimensionale Preisprozess (Bid- und Askpreis) in Verteilung zu einer Semimartingal reflektierten Brownschen Bewegung in der zugelassenen Preismenge. Gleichzeitig konvergieren die Kauf- und Verkaufsdichten im schwachen Sinn zum Betrag einer zweiparametrischen Brownschen Bewegung. Es wird weiterhin anhand eines Beispiels gezeigt, wie man für das Modell im ersten Teil eine stochastiche PDGL, unter einer starken Stationaritätsannahme für die Orderplatzierungen und -stornierungen, herleiten kann. Im dritten Teil wird ein Mittelungs- bzw. ein Invarianzprinzip für diskrete Banach- bzw. Hilbertraumwertige stochastische Prozesse bewiesen. / In the first part of the thesis, we define a random state-dependent discrete model of a two-sided limit order book in terms of its key quantities best bid [ask] price and the standing buy [sell] volume density. For a simple scaling that introduces a slow time scaling, that is equivalent to the classical law of large numbers, for the bid/ask prices and a faster time scale for the limit volume placements/cancelations, that keeps the expected volume rate over the considered price interval invariant, we prove a limit theorem. The limit theorem states that, given regularity conditions on the random order flow, the key quantities converge in the sense of a strong law of large numbers to a tractable continuous limiting model. The limiting model is such that the best bid and ask price dynamics can be described in terms of two coupled ODE:s, while the dynamics of the relative buy and sell volume density functions are given as the unique solutions of two linear first-order hyperbolic PDE:s with variable coefficients, specified by the expectation of the order flow parameters. In the second part, we prove a functional central limit theorem i.e. an invariance principle for an order book model with block shaped volume densities close to the spread. The weak limit of the two-dimensional price process (best bid and ask price) is given by a semi-martingale reflecting Brownian motion in the set of admissible prices. Simultaneously, the relative buy and sell volume densities close to the spread converge weakly to the modulus of a two-parameter Brownian motion. We also demonstrate an example how to easily derive an SPDE for the relative volume densities in a simple case, when a strong stationarity assumption is made on the limit order placements and cancelations for the model suggested in the first part. In the third and final part of the thesis, we prove an averaging and an invariance principle for discrete processes taking values in Banach and Hilbert spaces, respectively.
|
222 |
Algorithmic contributions to bilevel location problems with queueing and user equilibrium : exact and semi-exact approachesDan, Teodora 08 1900 (has links)
No description available.
|
223 |
Reglerentwurf zur dezentralen Online-Steuerung von Lichtsignalanlagen in StraßennetzwerkenLämmer, Stefan 05 November 2007 (has links) (PDF)
Die Dissertationsschrift widmet sich einer systemtheoretischen Untersuchung zur verkehrsabhängigen Steuerung von Lichtsignalanlagen in Straßennetzwerken. Aus einem mathematischen Modell für den Verkehrsablauf auf Knotenzufahrten wird ein Verfahren abgeleitet, mit dem sich Umschaltzeitpunkte und Phasenwechsel flexibel an das tatsächliche Verkehrsgeschehen anpassen lassen. Der Ansatzpunkt ist, die einzelnen Knotenpunkte des Netzwerks lokal zu optimieren. Eine "Grüne Welle" soll sich von selbst einstellen, und zwar genau dann, wenn dadurch lokal Wartezeiten eingespart werden. Indem die lokale Optimierung in ein lokales Stabilisierungsverfahren eingebettet wird, können Instabilitäten aufgrund netzwerkweiter Rückkopplungen ausgeschlossen werden. Das vorgestellte Verfahren setzt sich aus drei Teilen zusammen: (i) einem lokalen Prognoseverfahren zur Bewertung von Schaltzuständen und Phasenübergängen bezüglich zukünftig entstehender Wartezeiten, (ii) einem lokalen Optimierungsverfahren, das jeder Phase einen dynamischen Prioritätsindex zuweist und die Phase mit höchster Priorität zur Bedienung auswählt und (iii) einem lokalen Stabilisierungsverfahren, das zum Einhalten einer mittleren und einer maximalen Bedienperiode korrigierend in die lokale Optimierung eingreift. Indem die Knotenpunkte ausschließlich über die Verkehrsströme gekoppelt sind, ergeben sich die Umschaltzeitpunkte unmittelbar aus den Ankunftszeitpunkten der Fahrzeuge selbst. Die Phasenwechsel stellen sich somit von selbst bedarfsgerecht ein. Simulationsergebnisse machen deutlich, dass sich aufgrund der höheren Flexibilität sowohl die Wartezeiten als auch der Kraftstoffverbrauch senken lassen.
|
224 |
IEEE 802.16 Mesh Mode分散式排程之數學模型建立 / Modeling the Distributed Scheduler of IEEE 802.16 Mesh Mode陳彥賓, Chen, Yan-Bin Unknown Date (has links)
IEEE 802.16 是一支援都會型無線網路的協定,IEEE 802.16支援PMP模式(點對多點)和網狀模式兩種。在網狀模式中,所有節點的構成仿如ad-hoc方式,並依據在控制性子框中的排程資訊來計算下次遞送時間。在資料傳送之前,會有一段設定連線的時間。這段時間,每一個節點都必須跟鄰節點競爭,以取得廣播它的排程資訊給鄰節點的機會。這樣的行為跟它過去的歷史無關。換句話說,它具有”時間同質性”而適合以隨機程序來模擬。在這篇論文中,我們將用排隊程序來建立排程行為的模型,然後以馬可夫鏈來估計它的平均延遲時間,也就是一節點持續地競爭直到贏為止的這段等待時間。 / The IEEE 802.16 standard is a protocol for wireless metropolitan networks. IEEE 802.16 MAC protocol supports both of PMP (point to multipoint) and Mesh mode. In the mesh mode, all nodes are organized in a fashion similar ad-hoc and calculate their next transmission time based on the scheduling information performed in the control subframe. Before data transmission for a certain node, there is a period of time to setup the connection. During this period, each node has to compete with each other for the opportunity to advertise scheduling messages to its neighbors. This behavior does not depend on past history. In other words, it is a “Time Homogeneous” and suitable for being modeled by stochastic process. In this thesis, we will model this scheduling behavior by queuing process, and apply the Markov Chain to estimate its average delay time which a node keep waiting until it win the competition.
|
225 |
Σχεδόν πλήρως αναλυόμενα στοχαστικά συστήματα και εφαρμογές / Nearly completely decomposable stochastic systems and applicationsΝικολακόπουλος, Αθανάσιος Ν. 11 June 2013 (has links)
Το θέμα της παρούσας μεταπτυχιακής διπλωματικής εργασίας είναι η εφαρμογή της θεωρίας των Σχεδόν Πλήρως Αναλυόμενων Στοχαστικών Συστημάτων (Nearly Completely Decomposable) σε μία σειρά προβλημάτων στα οποία παραδοσιακές προσεγγίσεις αποδεικνύονται ερμηνευτικά στείρες και υπολογιστικά κοστοβόρες. Στο πρώτο μέρος της διπλωματικής αφού κάνουμε μία διαισθητικού τύπου παρουσίαση της ιδέας της decomposability και συνοψίσουμε τα απαραίτητα στοιχεία του θεωρητικού υποβάθρου που χρησιμοποιούμε στα πλαίσια της εργασίας, παραθέτουμε τονπυρήνα της θεωρίας της decomposability, όπως αυτή θεμελιώνεται μαθηματικά από τον Courtois στην κλασική του μονογραφία. Τέλος, παραθέτουμε και μία υλοποίηση του KMS αλγορίθμου Συσσωμάτωσης/Αποσυσσωμάτωσης, για τη λύση NCD συστημάτων.
Το δεύτερο μέρος του συγγράμματος, είναι αφιερωμένο στην εφαρμογή της NCD σε δύο ενδιαφέροντα προβλήματα εκτίμησης απόδοσης υπολογιστικών συστημάτων. Συγκεκριμένα, μελετούμε μία ιδιότυπη ουρά που εξυπηρετεί πελάτες διαφορετικών κλάσεων, με τις ανά κλάση αφίξεις να χαρακτηρίζονται από εναλλαγές μεταξύ περιόδων ηρεμίας και κινητικότητας και την εξυπηρέτηση να γίνεται σε δέσμες πελατών της ίδιας κλάσης. Το κίνητρο για τη μελέτη αυτής της ουράς εντοπίζεται στη bursty φύση της μεταγωγής πακέτων στα σύγχρονα δίκτυα αλλά και στους reassembly buffers των multicluster πολυεπεξεργαστικών συστημάτων. Η ανάλυση της ουράς με παραδοσιακές τεχνικές οδηγεί αναπόφευκτα σε μαρκοβιανή αλυσίδα πολύ μεγάλου χώρου κατάστασης. Εμείς, ξεκινάμε από το πλήρες στοχαστικό μητρώο και αφού διαμερίσουμε κατάλληλα το χώρο καταστάσεων, αποδεικνύουμε ικανές συνθήκες υπό τις οποίες το αρχικό σύστημα είναι δυνατόν να αναλυθεί σε πολλαπλά επίπεδα υποσυστημάτων, η αυτόνομη ανάλυση των οποίων δίνει μία πολύ καλή προσέγγιση της στάσιμης κατανομής του αρχικού συστήματος. Επίσης, παραθέτουμε και αποδεικνύουμε μία ικανή συνθήκη για μηδενικό σφάλμα προσέγγισης και την ερμηνεύουμε σε όρους προδιαγραφών του προβλήματος. Τέλος, θεωρούμε μία ειδική συμμετρική εκδοχή για την οποία καταφέρνουμε να δώσουμε μία κλειστή έκφραση της κατανομής πληρότητας της ουράς συναρτήσει της λύσης των υποσυστημάτων.
Για να δείξουμε την απλοποίηση της ανάλυσης που επιφέρει η χρήση του NCD μοντέλου θεωρούμε ένα σενάριο για το οποίο προχωρούμε την ανάλυση σε βάθος και καταφέρνουμε να εξάγουμε χρήσιμες μετρικές στις οποίες, σε αντίθετη περίπτωση, θα ήταν ιδιαίτερα επίπονο να καταλήξει κανείς. Συγκεκριμένα, υπολογίζουμε την πιθανότητα blocking και δείχνουμε πως αυτή μειώνεται σχεδόν εκθετικά με το μέγεθος της ουράς. Βλέπουμε τελικά πως η εκμετάλλευση της NCD ιδιότητας από τη μία διευκολύνει την ανάλυση και από την άλλη παρέχει ανεκτίμητη διαίσθηση σχετικά με τη μεταβατική συμπεριφορά του συστήματος προς την κατάσταση στατιστικής ισορροπίας.
Το δεύτερο μέρος της διπλωματικής κλείνει με τη μελέτη κριτηρίων υπό τα οποία, πολυεπεξεργαστικά συστήματα που χωρίζονται σε ομάδες ισχυρά αλληλεπιδρώντων επεξεργαστών, μπορούν να αναλυθούν με χρήση της θεωρίας NCD. Είναι γνωστό πως στα δίκτυα ουρών αναμονής συγκρίσιμων ρυθμών εξυπηρέτησης, η NCD του μητρώου πιθανοτήτων δρομολόγησης συνεπάγεται την NCD του δικτύου. Εμείς, θεωρούμε μία ειδική περίπτωση τέτοιων συστημάτων για την οποία δείχνουμε ένα, εύκολο να ελεγχθεί, κριτήριο για NCD. Τέλος, εξετάζουμε βαθύτερα το σφάλμα της προσέγγισης, και χρησιμοποιώντας ένα πρόσφατο αποτέλεσμα της θεωρίας των σχεδόν ασύζευκτων μαρκοβιανών αλυσίδων δίνουμε έναν επιπλέον ποιοτικό περιορισμό που πρέπει να ικανοποιούν τα εν λόγω συστήματα για να πάρει κανείς ικανοποιητική προσέγγιση από την ανάλυσή τους σε ανεξάρτητα block.
Στο τρίτο μέρος της παρούσας εργασίας, εξετάζουμε την εφαρμογή της NCD στο πρόβλημα της κατάταξης ιστοσελίδων. Η πρόσφατη έρευνα έχει σχολιάσει την ειδική δομή του στοχαστικού μητρώου που προκύπτει από το γράφο του διαδικτύου· συγκεκριμένα, οι τοπολογικές ιδιότητες της αυτοoργάνωσης του Ιστού φαίνεται να παράγουν ένα στοχαστικό μητρώο με NCD δομή. Εμείς, αφού παραθέσουμε μία σύνοψη των μαθηματικών πίσω από τον αλγόριθμο PageRank, σχολιάζουμε και δικαιολογούμε διαισθητικά την NCD δομή του Ιστού αλλά και τη φύση των υποσυστημάτων. Τέλος, προτείνουμε έναν νέο αλγόριθμο κατάταξης με το όνομα NCDawareRank, o οποίος εκμεταλλεύεται την NCD ιδιότητα για να πετύχει ποιοτικότερο και ταχύτερο ranking. Μάλιστα, δίνουμε δύο εκδοχές του αλγορίθμου, μία σειριακή και μία παράλληλη, η οποία εκμεταλλεύεται την NCD του Ιστού και υπολογιστικά. Τα οφέλη που υπόσχεται ο NCDawareRank τα επιβεβαιώνουμε και πειραματικά εκτελώντας μία σειρά από πειράματα τόσο σε τεχνητά όσο και σε πραγματικά δεδομένα, αντιπαραβάλλοντας τα αποτελέσματα μας με αυτά του αλγορίθμου PageRank. O NCDawareRank φαίνεται μάλιστα να δίνει λύση σε ένα γνωστό πρόβλημα του PageRank: αυτό της μεροληψίας εναντίον νεοεισερχομένων σελίδων. Άλλο ένα, τέλος, παράπλευρο όφελος του αλγορίθμου NCDawareRank είναι αυτό της Levelwise κατάταξης, η οποία εκτός της σημασίας που έχει αφεαυτής, μπορεί να υποδείξει εξυπνότερο crawling ή ακόμα και αποδοτικότερα σχήματα ευρετηριοποίησης του Ιστού.
Στο τέταρτο και τελευταίο μέρος της διπλωματικής εφαρμόζουμε την NCD στην εύρεση των στοχαστικά ευσταθών καταστάσεων μίας κατηγορίας εξελικτικών παιγνίων στα οποία εμφανίζονται πολυεπίπεδες στρατηγικές δυναμικές. Αφού παραθέσουμε κάποιες πρόσφατες παρατηρήσεις από τη βιβλιογραφία της οικονομετρίας σχετικά με την αξιοποίηση της NCD στην προσεγγιστική ανάλυσή τους, αποδεικνύουμε συνθήκες υπό τις οποίες είναι δυνατόν να πετύχει κανείς ακριβή ανάλυση. / The purpose of this master’s thesis is the application of the theory of Nearly Completelely
Decomposable stochastic systems to a number of interesting problems for which tra-
ditional techniques turn out to be both intuitively unappealing and computationally in-
tractable.
In the first part of this work, after introducing, the concept of decomposability in
an intuitive way and summarizing the essential elements of the theoretical background
that is necessary to follow the rest of the text, we present the fundamental mathematical
principles of NCD as established by Courtois in his classic monograph. Finally, we give
an implementation of the KMS iterative aggregation/disaggregation algorithm which is
commonly used for the solution of NCD systems.
The second part of the dissertation is devoted to the application of NCD to two inter-
esting problems of Computer Systems Performance Evaluation. Specifically, we study an
uncommon discrete time queue that serves customers from different classes, with the ar-
rivals of each class characterized by alternating busy and idle periods. The service is done
in batches of customers of the same class. The motivation behind the study of this queue,
lies in the bursty nature of packet switching, as well as in the modern reassembly buffers
of multicluster multiprocessor systems. The traditional analysis techniques of this queue
inevitably lead to Markov chains with very large state space. We begin with the complete
stochastic matrix and after careful partitioning of the state space, we give sufficient condi-
tions under which the original system can be analysed through multi level decomposition
into subsystems, the autonomous analysis of which results in a very good approximation
to the stationary distribution of the original system. Furthermore, we present and prove a
sufficient condition for an error-free approximation and we give an interpretation of this
condition in terms of the specifications of the problem. Finally, we consider a special sym-
metric version of the problem, for which we manage to derive a closed-form expression
for the queue’s occupancy distribution as a function of the steady state probabilities of the
subsystems.
To demonstrate the simplification of the analysis brought by the NCD model, we con-
sider a scenario in which we proceed to an in depth analysis and we manage to extract
useful metrics the derivation of which, would be considerably harder without exploiting
13
Abstract
14
NCD. Specifically, we calculate the blocking probability and we show that it decreases
almost exponentially with the size of the queue. From our analysis, it is clear that the
exploitation of the NCD model increases significantly our ability to understand the dy-
namics of our system and to interpret aspects of its transient behaviour towards statistical
equilibrium.
The second part of this work ends with the study of criteria under which multipro-
cessing systems, that can be divided into groups of strongly interacting processors, can be
analysed using the theory of NCD. It is known that in queueing networks with servers of
comparable service rates, the NCD of the routing probability matrix implies the NCD of
the network. We consider a special case of such systems and we derive an easy to check
criterion for NCD. Finally, we look deeper into the error analysis of this approach, and
using a recent result from the theory of nearly uncoupled Markov chains, we give an addi-
tional qualitative constrain to be met by these systems in order to get a good approximation
of their analysis into independent blocks.
In the third part of this paper, we examine the application of NCD to the problem of
ranking websites. Recent research has commented on the special structure of the stochastic
matrix which corresponds to the web-graph. In particular, the topological properties of the
Web seems to produce a NCD stochastic matrix. Here, after presenting briefly the mathe-
matical basis of PageRank, we give a linear algebraic as well as an intuitive justification of
the NCD Web structure and we discuss the nature of the subsystems. Finally, we propose
a new ranking algorithm named NCDawareRank, which exploits NCD in order to achieve
a fairer and faster ranking. Indeed, we give two versions of the algorithm, one serial and
one parallel, in which we take advantage of the computational benefits of NCD as well.
The advantages of NCDawareRank are then confirmed experimentally through a series of
tests on both, artificial and real data. NCDawareRank seems to solve a known problem of
PageRank: the bias against new websites. Finally, another side benefit of our algorithm is
that it makes it easy to extract a level-wise ranking, which besides its importance in itself,
may indicate smarter crawling or even more sophisticated and efficient indexing schemes
of the Web.
Finally, in the fourth part of this work we apply NCD to the problem of finding
the stochastically stable states of a class of evolutionary games which involve multilevel
strategic dynamics. After presenting some interesting recent results coming from the lit-
erature of econometrics, we give conditions under which it is possible to get the exact
stochastically stable states through the use of NCD.
|
226 |
Aplicação de modelos de redes de filas abertas no projeto e planejamento de sistemas discretos de manufatura. / Application of open queueing network models for the design and planning of discrete manufacturing systems.Silva, Claudio Rogerio Negri da 29 April 2005 (has links)
Made available in DSpace on 2016-06-02T19:50:27Z (GMT). No. of bitstreams: 1
TeseCRNS.pdf: 1772351 bytes, checksum: 17b2dc82dae0e985204bfa2fd68f873b (MD5)
Previous issue date: 2005-04-29 / Universidade Federal de Minas Gerais / The management of manufacturing systems have become more complex, once that new
products are arising, product demands are uncertain, life cycles get shorter, and a wide
variety of products compete for common resources. This thesis deals with the design
and planning of discrete manufacturing systems, based on open queueing network
models to support the decision making of capacity allocation. As manufacturing systems
may be represented by generalized queueing networks, and there are no exact solution
methods, here is employed the decomposition approximate method to evaluate the
performance of systems under different configurations. It is shown in the thesis how
these approximations are suitable and effective to estimate the work-in-process (WIP)
and the production leadtime of an actual metallurgical industry queueing network. It is
also shown that discrete capacity allocation models, based on the approximations, are
effective to evaluate and optimize the performance of the case study under different
configurations. Trade-off curves between capacity investment and WIP are generated
and are useful not only to support a manager to estimate how much capacity he/she
should allocate, but also to decide where it should be allocated in the queueing network.
These curves also support the decision making in terms of capacity, if the variability of
the external arrivals, the product mix and/or the throughput for the network change.
Besides adding capacity, partitioning the facility is another alternative to reduce the
system complexity. This thesis also approaches the focused factory design problem,
involving the partition of the facility into smaller shops and the capacity allocation in
each shop. Again, the decomposition approximations were employed to evaluate the
system performance. Despite its importance, this problem has rarely been reported in
the literature. In this thesis, the goal is to reduce the system complexity either from the
product management point of view or from the workstation management point of view.
From the product management point of view, a model whose complexity constraint is na
upper limit on the production leadtime variance of the products passing through the
network was studied. From the workstation management point of view, the complexity
constraint of the model keeps constant the expected waiting time of a product at a
workstation, once it waits for being served. It is shown through these models for some
instances that the partition of the facility into smaller shops decreases the complexity
system without necessary capacity additional investments. Futhermore, sometimes it is
possible to keep the network performance (or even to improve it), partitioning the
network into smaller shops which need less capacity than the original configuration with
a single shop. / A gestão de sistemas de manufatura tem se tornado mais complexa na medida em que
novos produtos estão surgindo, a demanda de produtos é incerta, os ciclos de vida são
mais curtos e uma grande variedade de produtos competem pelos mesmos recursos. Esta
tese trata o projeto e planejamento de sistemas discretos de manufatura, baseados em
modelos de redes de filas abertas, para auxiliar no processo de tomada de decisões.
Porque sistemas de manufatura podem ser representados por redes de filas genéricas, e
não existem métodos exatos de solução, aqui é empregado o método aproximado de
decomposição para avaliar o desempenho dos sistemas em diferentes configurações.
Mostra-se nesta tese que estas aproximações são adequadas e efetivas para estimar os
estoques em processo (WIP) e o leadtime de produção de uma rede de manufatura real
de uma indústria metal-mecânica. Mostra-se ainda que os modelos de alocação de
capacidade discreta, baseados nestas aproximações, também são efetivos para avaliar e
otimizar o desempenho da rede do estudo de caso em diferentes configurações. Curvas
de trade-off entre investimento em capacidade e WIP são geradas e são úteis não
somente para auxiliar um gerente a estimar quanto alocar de capacidade, mas também
para decidir onde alocá-la na rede de filas. As curvas também auxiliam a tomada de
decisões em termos de capacidade, se a variabilidade das chegadas externas, o mix de
produtos e/ou a taxa de produção da rede mudam. Além de adicionar capacidade, a
partição da instalação é outra alternativa para reduzir a complexidade do sistema. Esta
tese também aborda o problema de projeto de fábrica focalizada, envolvendo a partição
da instalação em subplantas e a alocação de capacidade em cada estação das subplantas.
Novamente, as aproximações por decomposição foram utilizadas para avaliar e otimizar
o desempenho do sistema. Apesar de sua importância, este problema tem sido muito
pouco reportado em literatura. Nesta tese, o objetivo é reduzir a complexidade do
sistema do ponto de vista da gestão do produto, ou do ponto de vista da gestão da
estação. Do ponto de vista da gestão do produto, é apresentado um modelo cuja
restrição de complexidade é um limitante superior para a variância do leadtime dos
produtos na rede. Do ponto de vista da gestão da estação, a restrição de complexidade
do modelo fixa o tempo médio de espera de um produto na estação, quando há espera.
Mostra-se, por meio destes modelos para alguns casos que, a partição da instalação em
subplantas reduz a complexidade do sistema, sem necessidade de investimentos
adicionais em capacidade. Além disso, algumas vezes, é possível manter (ou até
melhorar) o desempenho da rede, particionando-a em subplantas que necessitam de
menos capacidade do que a configuração original com uma planta única.
|
227 |
Estudo comparativo das aproximações baseadas no método de decomposição paramétrico para avaliar redes de filas de manufatura utilizando planejamento de experimentos / A comparative study of approximations based on the parametric decomposition method to evaluate manufacturing queueing networks using designing of experimentsCamorim, José Eduardo Vieira 29 February 2008 (has links)
Made available in DSpace on 2016-06-02T19:51:35Z (GMT). No. of bitstreams: 1
1770.pdf: 2888839 bytes, checksum: 18c57ba21e9192d597b74f8d1d0fc997 (MD5)
Previous issue date: 2008-02-29 / Universidade Federal de Minas Gerais / This is a study of approximations based on parametric decomposition methods
used in open queueing networks for modeling discrete job-shop manufacturing systems. These
approximations play an important role in evaluating the performance of productive systems and
have proved effective in many situations. Besides, these approximations are relatively easy to
apply requiring fewer data compared to other methods because they use the average rate and SCV
(square coefficient of variation) as the only parameters to characterize the network arrival and
service processes. This work is aimed at analyzing and comparing several approximations since
they are not yet available in the literature. Hence, several network situations were tested in order
to identify the most adequate approximation for each situation. Firstly, a two-station network was
analyzed followed by the analysis of a five-station network and lastly, a real example of a
semiconductor plant, analyzed by Bitran e Tirupati (1988), was used. In order to reach these
goals, the state of the art of approximation methods to evaluate the performance of open queueing
networks was studied, and the approximations were compared using the experiment planning
technique, important factors for building network configuration and data analysis The findings of
this work demonstrate that approximations can be highly efficient to evaluate the performance of
discrete job-shop manufacturing systems. Regardless of the configurations studied, it is worth
mentioning that approximations 3 and 2, in general, showed the best results if compared to the
other values obtained from simulations to evaluate the performance of open queueing networks,
OQN,. The other approximations tended to overestimate E(Lj) when the number of stations is
higher. This study intends to contribute to the development of computing systems in order to
support project decisions and the planning and control of discrete manufacturing systems using
approximations based on the parametric decomposition method / Esta dissertação estuda as aproximações baseadas nos métodos analíticos
paramétricos de decomposição usados em redes de filas abertas que modelam sistemas discretos
de manufatura do tipo job-shop. Estas aproximações possuem um importante papel na avaliação
do desempenho de sistemas produtivos e vem se mostrando eficiente para uma grande
diversidade de situações. Além disso, são aproximações relativamente fáceis de serem
aplicadas, necessitando poucos dados em relação a outros métodos, pois utilizam apenas a
média e o scv (coeficiente quadrático de variação) como parâmetros para caracterizar os
processos de chegadas e os processos de serviço da rede. O foco deste trabalho está em realizar
análises e comparações entre diversas aproximações, pois ainda não existe nenhuma
comparação mais efetiva entre elas na literatura. Para isso, diversas situações de redes foram
exploradas para identificar quais aproximações são mais adequadas para quais situações.
Primeiramente é analisado uma rede com 2 estações, posteriormente uma outra com 5 estações
e por fim usou um exemplo real de uma fábrica de semi-condutores, analisada por Bitran e
Tirupati (1988). Para que seja possível atingir esses objetivos, estudou-se o estado da arte das
aproximações dos métodos de avaliação de desempenho para redes de filas abertas, e comparouse
as aproximações por meio de técnicas de planejamento de experimentos, parte importante na
construção das configurações das redes e análise dos resultados. Os resultados apresentados
nesta dissertação mostram que essas aproximações podem ser bem eficientes ao avaliar o
desempenho de sistemas discretos de manufatura do tipo job-shop. Independente das
configurações analisadas, vale destacar a Aproximação 3 e a Aproximação 2, em geral, obtendo
os melhores resultados, entre as aproximações, em comparação aos valores obtidos pela
simulação para avaliar o desempenho de redes de filas OQN. As outras aproximações
demonstraram certo comportamento em sobreestimar E(Lj), quando o número de estações
aumentam. Este estudo pretende contribuir para o desenvolvimento de sistemas computacionais
13
para apoiar decisões de projeto, planejamento e controle dos sistemas discretos de manufatura,
usando aproximações baseadas em métodos de decomposição paramétrico
|
228 |
Análise de desempenho de sistemas de comunicação OFDM-TDMA utilizando cadeias de Markov e curva de serviço / Performance analysis of OFDM-TDMA wireless systems basedCosta, Victor Hugo Teles 06 December 2013 (has links)
Submitted by Jaqueline Silva (jtas29@gmail.com) on 2014-12-12T17:31:05Z
No. of bitstreams: 1
Dissertação-Victor Hugo Teles Costa-2013.pdf: 20678399 bytes, checksum: a39c778934ebe127bd74f506467fe0a3 (MD5) / Rejected by Jaqueline Silva (jtas29@gmail.com), reason: on 2014-12-12T17:31:57Z (GMT) / Submitted by Jaqueline Silva (jtas29@gmail.com) on 2014-12-12T19:42:30Z
No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação-Victor Hugo Teles Costa-2013.pdf: 20678399 bytes, checksum: a39c778934ebe127bd74f506467fe0a3 (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2014-12-16T09:25:22Z (GMT) No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação-Victor Hugo Teles Costa-2013.pdf: 20678399 bytes, checksum: a39c778934ebe127bd74f506467fe0a3 (MD5) / Made available in DSpace on 2014-12-16T09:25:22Z (GMT). No. of bitstreams: 2
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Dissertação-Victor Hugo Teles Costa-2013.pdf: 20678399 bytes, checksum: a39c778934ebe127bd74f506467fe0a3 (MD5)
Previous issue date: 2013-12-06 / This paper presents a model based on Markov Chains and enhanced with
the use of Kernel Density Estimation and of MMFM (Markov Modulated Fluid
Model) in order to evaluate the performance of the transmission link in OFDMTDMA
systems. For that purpose, traffic models based on the Kernel method and
the MMFM with adjusted autocorrelation function are proposed. From the model
implemented for the OFDM-TDMA system, it was derived equations for estimation
of QoS parameters such as delay and average queue size in the buffer. The
obtained results confirm that the proposed model is efficient in describing the link
performance indicators. The use of MMFM to model the arrival process improves
the QoS parameter estimates of the queueing model making their values very close
to those of the simulation results. It was also developed an equation to the OFDMTDMA
system’s service curve. Through this equation and the concept of Envelope
Process, it was proposed an equation to estimate the probability of buffer overflow
in OFDM-TDMA systems. The results show that the estimates of the overflow probability
based on the system’s service curve are very close to the ones obtained by
simulations and that the computational complexity to obtain them is significantly
reduced compared to the model based on Markov Chains due to the absence of
matrix computation. / Este trabalho apresenta um modelo baseado em Cadeias de Markov e aprimorado
com o uso do método de Kernel de estimação não-paramétrica e de MMFM
(Markov Modulated Fluid Model) com o objetivo de avaliar e descrever o desempenho
do enlace de transmissão em sistemas OFDM-TDMA. Para tal, modelos de tráfego
baseados no Método de Kernel e em MMFM com ajuste da função de autocorrelação
são propostos. A partir do modelo implementado para o sistema OFDM-TDMA,
foram obtidas equações para estimação de parâmetros de QoS como retardo e tamanho
médio da fila no buffer. Os resultados obtidos confirmam que o modelo proposto
é bastante eficiente ao descrever os indicadores de desempenho do sistema. O uso de
MMFM para modelar o processo de chegada de pacotes aprimora os estimadores de
parâmetros de QoS tornando as estimativas bem próximas dos valores obtidos com
as simulações. Também deduziu-se uma equação para a curva de serviço de Sistemas
OFDM-TDMA. Em seguida, utilizando-se desta curva de serviço e do conceito de
Processo Envelope foi proposta uma equação para estimação de probabilidade de
transbordo do buffer em sistemas OFDM-TDMA. Os resultados obtidos mostram
que as estimativas de probabilidade de transbordo baseadas na curva de serviço do
sistema se aproximam bem dos resultados da simulação e a complexidade computacional
do cálculo necessário para obtê-los é significativamente reduzida em relação
ao modelo definido utilizando Cadeias de Markov.
|
229 |
Adaptive traffic management in heterogeneous communication networksJutila, M. (Mirjami) 07 March 2017 (has links)
Abstract
Communication networks are experiencing a significant growth of data traffic posing new challenges to the overall systems that should become more reactive and adaptive towards dynamically changing traffic, connections and network conditions. This thesis examines adaptive traffic management solutions within heterogeneous communication networks, which can be utilized to improve network performance, provide Quality of Service (QoS) for traffic paths and share resources in a fair way. The developed adaptive methods include solutions for fuzzy flow scheduling (AWFQ, FWQ) and regressive admission control (REAC) to provide stable network performance and efficient resource control. Such techniques for adaptive traffic management continuously balance and control traffic usage and recover from network faults and attacks. The results utilize traffic monitoring for estimating the overall network conditions, applying cognition to learn from previous actions, and adapting to the current traffic conditions for resource optimization. The thesis researches how to distribute these computing mechanisms towards network edges closer to the actual application users for more efficient resource usage, and to provide better performance for delay-sensitive applications. The methods developed have been applied to vehicular communications to assess and improve the messaging between vehicles and vulnerable road users (VRUs). These mechanisms are able to react faster to data traffic changes and guarantee better quality for prioritized traffic and users while at the same time they preserve fairness to other flows compared to traditional control and scheduling methods without adaptive characteristics. The overall system reacts to changes in the network QoS by determining decision-making procedures on possible flow rejection, marking, or allowed bandwidth weight assignment, thus bringing cognition to the network path. / Tiivistelmä
Merkittävä liikennemäärien kasvu aiheuttaa tietoverkoille uusia haasteita, minkä vuoksi niiden täytyy tukea reaktiivisuutta ja adaptiivisuutta vastatakseen muuttuviin liikenne- sekä verkko-olosuhteisiin että yhteyksiin. Väitöskirjassa kehitetään heterogeenisten tietoverkkojen adaptiivisia liikenteenhallintaratkaisuja, joita voidaan hyödyntää verkon suorituskyvyn parantamiseen, tarjoamaan liikenteen palvelunlaatua (QoS) sekä tasapuolista resurssien jakoa. Kehitetyt adaptiiviset menetelmät sisältävät ratkaisuja sumeaan logiikkaan perustuvaan skedulointiin sekä regressiiviseen verkon pääsynhallintaan pohjautuen, jotka takaavat vakaamman verkon suorituskyvyn ja resurssien hallinnan. Nämä menetelmät tasapainottavat ja kontrolloivat liikennettä sekä pyrkivät palautumaan verkon häiriöistä ja hyökkäyksistä. Tulokset hyödyntävät liikenteen monitorointia verkon tilan arviointiin, soveltavat kognitiivisuutta oppiakseen aiemmista toiminnoista sekä adaptoituvat nykytilanteeseen resurssien optimoimiseksi. Väitöskirja tutkii, miten kyseisiä laskentamenetelmiä voidaan hajauttaa verkon reunoille lähemmäksi sovellusten käyttäjiä resurssien käytön tehostamiseksi sekä tarjoamaan parempaa suorituskykyä viiveherkille sovelluksille. Kehitettyjä menetelmiä sovelletaan autoverkkoihin autojen sekä suojattomien tienkäyttäjien viestinnän määrittämiseen sekä parantamiseen. Nämä menetelmät reagoivat nopeammin dataliikenteen muutoksiin, takaavat paremman laadun priorisoidulle liikenteelle sekä samalla tasapuolisuutta muulle liikenteelle verrattuna perinteisiin kontrollointi- ja skedulointimenetelmiin. Kehitetty järjestelmä reagoi verkon palvelunlaadun muutoksiin määrittelemällä päätöksentekomalleja mahdolliseen tietovuon hylkäämiseen, merkitsemiseen tai kaistankäytön painokertoimen määrittämiseen, täten luoden kognitiivisuutta verkon reitille.
|
230 |
Garanties de performance pour les flots IP dans l'architecture Flow-Aware Networking / Flow-level performance guarantees for IP traffic in the Flow-Aware Networking architectureAugé, Jordan 27 November 2014 (has links)
La thèse s'intéresse à la réalisation d'une architecture de Qualité de Service en rupture avec les approches classiques, permettant d'offrir des garanties de bout en bout pour le trafic. L'approche Flow-Aware Networking considère le trafic au niveau des flux applicatifs, pour lesquels des modèles de trafic simples mais robustes conduisent à une relation fondamentale entre ressources offertes par le réseau, la demande générée, et la performance obtenue. En particulier, l'architecture de routeur Cross-Protect propose la combinaison d'un ordonnancement fair queueing et d'un contrôle d'admission afin d'assurer de manière implicite la performance des flots streaming et élastique, sans nécessiter ni marquage ni procotole de signalisation. Dans un tel contexte, nous considérons le dimensionnement des buffers au sein des routeurs, l'introduction d'un ordonnancement de type fair queueing dans le réseau et son impact sur la performance des protocoles TCP, ainsi que la réalisation d'un algorithme de contrôle d'admission approprié. Pour terminer, une déclinaison de cette architecture pour le réseau d'accès est proposée. / The thesis deals with the realization of a Quality of Service architecture that breaks with traditional approaches, and allows end-to-end performance guarantees for the traffic. The Flow-Aware Networking approach considers the traffic at the flow level, for which simple but robust traffic models lead to a fundamental relationship between the resources offered by the network, the demand and the obtained performance. In particular, the Cross-Protect router architecture proposes the combination of a fair queueing scheduler, and an admission control so as to implicitly ensure the performance of both streaming and elastic flows, without the need for any marking nor signalization protocol. In such a context, we consider the sizing of router buffers, the introduction of fair queueing scheduling inside the network and its impact on the performance of TCP protocols, as well as the realization of a suitable admission control algorithm. Finally, a declination of this architecture for the access network is proposed.
|
Page generated in 0.0697 seconds