1 |
Analysis and Approximations of Time Dependent Queueing ModelsNasr, Walid 26 February 2008 (has links)
Developing equations to compute congestion measures for the general G/G/s/c queueing model and networks of such nodes has always been a challenge. One approach to analyzing such systems is to approximate the model-specified general input processes and distributions by processes and distributions from the more computationally friendly family of phase-type processes and distributions. We develop numerical approximation methods for analysis of general time-dependent queueing nodes by introducing new approximations for the time-dependent first two moments of the number-in-system and departure-count processes. / Ph. D.
|
2 |
Departure processes from MAP/PH/1 queuesGreen, David Anthony January 1999 (has links)
A MAP/PH/1 queue is a queue having a Markov arrival process (MAP), and a single server with phase-type (PH -type) distributed service time. This thesis considers the departure process from these type of queues. We use matrix analytic methods, the Jordan canonical form of matrices, non-linear filtering and approximation techniques. The departure process of a queue is important in the analysis of networks of queues, as it may be the arrival process to another queue in the network. If a simple description were to exist for a departure process, the analysis of at least feed-forward networks of these queues would then be analytically tractable. Chapter 1 is an introduction to some of the literature and ideas surrounding the departure process from MAP/PH/1 queues. Chapter 2 sets up the basic notation and establishes some results which are used throughout the thesis. It contains a preliminary consideration of PH -type distributions, PH -renewal processes, MAP s, MAP/PH/1 queues, non-linear filtering and the Jordan canonical form. Chapter 3 is an expansion of "The Output process of an MMPP/M/1 queue", where the question of whether a MAP description can exist for the departure process of a non-trivial MAP/M/1 queue is considered. In a 1994 paper, Olivier and Walrand conjectured that the departure process of a MAP/PH/1 queue is not a MAP unless the queue is a stationary M/M/1 queue. This conjecture was prompted by their claim that the departure process of an MMPP/M/1 queue is not MAP unless the queue is a stationary M/M/1 queue. We show that their proof has an algebraic error, which leaves open the above question of whether the departure process of an MMPP/PH/1 queue is a MAP or not. In Chapter 4, the more fundamental problem of identifying stationary M/M/1 queues in the class of MAP/PH/1 queues is considered. It is essential to be able to determine from its generator when a stationary MAP is a Poisson process. This does not appear to have been discussed in the literature prior to the author's paper, where this deficiency was remedied using ideas from non-linear filtering theory, to give a characterisation as to when a stationary MAP is a Poisson process. Chapter 4 expands upon "When is a MAP Poisson". This investigation of higher order representations of the Poisson process is motivated by first considering when a higher order PH -type distribution is just negative exponential. In Chapter 5, we consider the related question of minimal order representations for PH -type distributions, an issue which has attracted much interest in the literature. A discussion of other authors' ideas is given and these ideas are then inter-related to the work presented in Chapter 4 on the PH -type distributions. The MAP/M/1 queue is then considered in Chapter 6 from the perspective of whether having an exact level and phase independent stationary distribution of the geometric form [Formula - Not available: see pdf version of the abstract] implies that the MAP is Poisson. The answer is in the affirmative for this question, but the converse is not strictly true. Apart from showing the ubiquitous asymptotic form of level and phase independence exhibited by all stable MAP/M/1 queues, we prove that a very large class of stable queues, exhibits what we have termed shift-one level and phase independence. Stable MAP/M/1 queues exhibiting shift-one level and phase independence, are characterised by a stationary distribution of the following form: [Formula - Not Available: see pdf version of the abstract] In Chapter 7, a family of approximations is proposed for the output process of a stationary MAP/PH/1 queue. To check the viability of these approximations, they are used as input to another single server queue. Performance measures for the second server are obtained analytically in both the tandem and approximation cases, thus eliminating the need for simulation to compare results. Comparison of these approximations is also made against other approximation methods in the literature. In Chapter 8, we show that our approximations from Chapter 7 have the property of exactly matching the inter-departure time distribution. Our kth approximation also accurately captures the first k-1 lag-correlation coefficients of the stationary departure process. The proofs of this direct association between lag-correlation coefficients and the level of complexity k are given. / Thesis (Ph.D.)--School of Applied Mathematics, 1999.
|
3 |
Departure processes from MAP/PH/1 queuesGreen, David Anthony January 1999 (has links)
A MAP/PH/1 queue is a queue having a Markov arrival process (MAP), and a single server with phase-type (PH -type) distributed service time. This thesis considers the departure process from these type of queues. We use matrix analytic methods, the Jordan canonical form of matrices, non-linear filtering and approximation techniques. The departure process of a queue is important in the analysis of networks of queues, as it may be the arrival process to another queue in the network. If a simple description were to exist for a departure process, the analysis of at least feed-forward networks of these queues would then be analytically tractable. Chapter 1 is an introduction to some of the literature and ideas surrounding the departure process from MAP/PH/1 queues. Chapter 2 sets up the basic notation and establishes some results which are used throughout the thesis. It contains a preliminary consideration of PH -type distributions, PH -renewal processes, MAP s, MAP/PH/1 queues, non-linear filtering and the Jordan canonical form. Chapter 3 is an expansion of "The Output process of an MMPP/M/1 queue", where the question of whether a MAP description can exist for the departure process of a non-trivial MAP/M/1 queue is considered. In a 1994 paper, Olivier and Walrand conjectured that the departure process of a MAP/PH/1 queue is not a MAP unless the queue is a stationary M/M/1 queue. This conjecture was prompted by their claim that the departure process of an MMPP/M/1 queue is not MAP unless the queue is a stationary M/M/1 queue. We show that their proof has an algebraic error, which leaves open the above question of whether the departure process of an MMPP/PH/1 queue is a MAP or not. In Chapter 4, the more fundamental problem of identifying stationary M/M/1 queues in the class of MAP/PH/1 queues is considered. It is essential to be able to determine from its generator when a stationary MAP is a Poisson process. This does not appear to have been discussed in the literature prior to the author's paper, where this deficiency was remedied using ideas from non-linear filtering theory, to give a characterisation as to when a stationary MAP is a Poisson process. Chapter 4 expands upon "When is a MAP Poisson". This investigation of higher order representations of the Poisson process is motivated by first considering when a higher order PH -type distribution is just negative exponential. In Chapter 5, we consider the related question of minimal order representations for PH -type distributions, an issue which has attracted much interest in the literature. A discussion of other authors' ideas is given and these ideas are then inter-related to the work presented in Chapter 4 on the PH -type distributions. The MAP/M/1 queue is then considered in Chapter 6 from the perspective of whether having an exact level and phase independent stationary distribution of the geometric form [Formula - Not available: see pdf version of the abstract] implies that the MAP is Poisson. The answer is in the affirmative for this question, but the converse is not strictly true. Apart from showing the ubiquitous asymptotic form of level and phase independence exhibited by all stable MAP/M/1 queues, we prove that a very large class of stable queues, exhibits what we have termed shift-one level and phase independence. Stable MAP/M/1 queues exhibiting shift-one level and phase independence, are characterised by a stationary distribution of the following form: [Formula - Not Available: see pdf version of the abstract] In Chapter 7, a family of approximations is proposed for the output process of a stationary MAP/PH/1 queue. To check the viability of these approximations, they are used as input to another single server queue. Performance measures for the second server are obtained analytically in both the tandem and approximation cases, thus eliminating the need for simulation to compare results. Comparison of these approximations is also made against other approximation methods in the literature. In Chapter 8, we show that our approximations from Chapter 7 have the property of exactly matching the inter-departure time distribution. Our kth approximation also accurately captures the first k-1 lag-correlation coefficients of the stationary departure process. The proofs of this direct association between lag-correlation coefficients and the level of complexity k are given. / Thesis (Ph.D.)--School of Applied Mathematics, 1999.
|
4 |
Processutveckling: en konceptmodell för arbetsmetodiken vid utveckling av resenärsprocesser : En fallstudie på Swedavia, Arlanda flygplatsJakobsson, Sandra, Strömberg, Joakim January 2017 (has links)
Flygplatser utgör en nyckelroll i dagens samhälle. De fungerar inte enbart som ett centrum för samverkan mellan transportmedel, utan även som en mötesplats för resenärer. Trängsel i terminalerna har blivit ett betydande problem för de som flyger regelbundet och i flera fall har minskad kötid blivit synonymt med hög kvalitet för resenären. En effektivare hantering av resenären är nödvändig och kräver tillförlitliga processer. Att arbeta med processer är inget nytt, det har länge varit centralt för verksamhetsprocesser och arbetsflöden, främst inom tillverkningsindustrin men den omfattande litteraturgenomgången påvisar att det finns få processorienterade modeller som specifikt tillämpas på en resenärsprocess. Fallföretaget, Swedavia, arbetar aktivt med resenärsprocessen inom flygbranschen. De har utvecklat en viss metodik men denna är inte effektiv nog då de upplever problematik på grund av det ökade antalet resenärer. Syftet med studien är därför att skapa en konceptmodell för arbetsmetodiken vid utveckling av resenärsprocessen på flygplatser, med avsikt att tillföra en ny tillämpning till området för processutveckling. Modellen avser även hjälpa fallföretaget Swedavia att bli effektivare i sin processutveckling. Studiens metod har en abduktiv forskningsansats. Först genomfördes en utförlig litteraturgenomgång vilken utmynnade i ett första utkast av en konceptmodell med tolv nyckelfaktorer för processorientering kopplade till resenärsprocessen. Därefter genomfördes åtta semistrukturerade intervjuer med berörd personal på fallföretaget. Valet av fallföretag motiveras av deras generaliserbarhet, då samtliga respondenter arbetar med utveckling av Sveriges största flygplats, Arlanda. Avsikten med intervjuerna var att tydliggöra hur arbetet med utvecklingen av resenärsprocessen ser ut idag samt avgöra hur processorienterade de är. Slutligen analyserades konceptmodellen utifrån empirin, vilket resulterade i korrigeringar och en slutgiltig modell. Det vetenskapliga bidraget är utvecklingen av en konceptmodell för resenärsprocesser. Den slutliga konceptmodellen består av fem nyckelfaktorer, vilka är; processägare och -beskrivningar, stöd och engagemang, mätverktyg, organisation samt ständiga förbättringar. Den framtagna modellen är ett visuellt stöd för att hjälpa organisationer att bli effektivare i deras utveckling av en resenärsprocess. Den fungerar som ett verktyg för att förbättra processer och att utvärdera företag. / Airports have come to be one of the key elements in today’s society. They do not only serve as a center for interoperability, but also as a meeting place for travelers. Congestion in the terminals has become a significant problem for those who fly regularly and in many cases reduction of queue time has become synonymous with high quality travelling. Therefore, more efficient handling of the traveler is necessary and requires reliable processes. Working with processes has been central to business procedures and workflows for a long time, mainly in the manufacturing industry but the comprehensive literature review indicates that there are few process-oriented models specifically applied to the passenger departure process. The case company, Swedavia, is actively working with passenger departure processes in the aviation industry. They have developed a certain methodology, but it is not effective enough as they have experienced problems due to the increased number of travelers. For that reason, the aim of the study is to create a conceptual model for the work methodology when developing the passenger departure process at airports, with the intention of introducing a new application to process development. The model also aims to help Swedavia become more efficient in its process development. The study's method has an abductive research approach. First, a detailed literature review was conducted, which resulted in a first draft of a conceptual model with twelve key factors for process orientation linked to the traveler process. Eight semi-structured interviews were then conducted with relevant personnel at the case company. The choice of case company is motivated by their generalizability, as all respondents work with the development of Sweden's largest airport, Arlanda. The purpose of the interviews was to clarify what their work on developing the traveler process looks like and also to what extent they are process oriented. Finally, the conceptual model was analyzed based on empirical findings, resulting in corrections and a definitive model for developing the passenger departure process. The scientific contribution is the development of a conceptual model for passenger departure processes. The final conceptual model consists of five key factors, which are: process owners and descriptions, support and commitment, measurement tools, organization and continuous improvement. The proposed and identified model works as a visual support to help organizations become more efficient in their development of a passenger departure process. It is a useful tool to improve processes and to evaluate businesses.
|
5 |
Developing an integrated method of controlling the flow of departing passengers : a study of passenger departure processes at Abu Dhabi International AirportAl-Dhaheri, Abdulla January 2015 (has links)
Today, airports form a key part of global infrastructure in an increasingly globalised world. There is great competition between them to attract passengers and serve airlines in their role of transporting people regionally and internationally. Abu Dhabi International Airport is one such airport. Terminal 3 is the home of Abu Dhabi’s major carrier, Etihad Airways, one of the world’s fastest-growing international airlines. The research described in this thesis focuses on applying the Lean methodology to the passenger departure process in Terminal 3. The essential essence of ‘Lean’ is doing more with fewer resources by adopting a programme of continuous process improvement resulting in continually declining costs, mistakes and work-in-progress. The special environment of any airport, especially a major international hub made applying Lean principles difficult. This resulted from the large presence of Class I wastes or muda which could potentially change, perhaps dramatically, at short notice. This made this research significantly different from previous applications of Lean philosophy. Also, large, cumulative variations in demand set in an environment where rapid expansion of the airport is taking place also created major difficulties because of the shifting flow of passengers. Despite this, the research succeeded in achieving its aim and developed various rules from parameters based on the acronym SERVICE and an associated implementation methodology based on the Lean philosophy. Together these will help airline managers and staff to eliminate the waste of available resources and so increase passenger flow through various stages of the process in line with Lean philosophy. The research makes several important contributions to knowledge, especially in the field of Lean improvements. The contribution of this work arises from its systematic examination of the passenger departure process. The research has facilitated developing a detailed model which addresses both particular process groups and the effects of passenger class on the allocation and use of resources. This research has shown that large differences exist between the operating environment of a major international airport and those processes to which Lean principles have previously been applied. Nevertheless, despite these differences, this research has proved the Lean philosophy may be usefully applied to airport operations. Operating conditions within the passenger departure process mean that understanding the special operating environment of airports is vital. This research resulted in a discrete event simulation model of the airport much more accurate and detailed than those described in previous studies of passenger departure processes. The research then proved an improved model, which may be used experimentally to support conclusions reached from the broader application of Lean philosophy. The research observed and analysed the effects of large and cumulative peaks and troughs in demand against a background of rapid development of Abu Dhabi Airport. The researcher also evaluated the special internal and external effects on the processes, often at short notice. Consequently, there is no single ‘universal’ solution because of the major need for operational flexibility and for a close correlation between operational and strategic need. Despite these many difficulties the results of this research are a practical and straightforward series of improvements, which may be applied by airport staff themselves without need for complex computer models, simulation or dedicated experts. This will create conditions for continuously improving process performance during the passenger departure process. It will also help managers accurately identify critical areas where more radical action of increasing physical resources is needed. Finally, based on findings, the research makes several recommendations for further work.
|
6 |
E_m/E_k/1 輸出之相關結構 / Correlation Structure of An Output Process in Em/Ek/1簡熾華 Unknown Date (has links)
在本文中,我們主要研究的目標是Em/Ek/1模型的離去過程之相關性。
在此之前,不少學者作了很多有關M/G/1模型和G/M/1模型離去過程的相關性研究,但當等候理論中的“失憶性”(memoryless)這個重要的性質不再適用後,會產生什麼結果呢?
為了解Em/Ek/1的相關性,我們引入N-階段離去時間分配”(N-step interdeparture time distribution)的方法。藉由這個方法,我們可以計算出系統中離去間隔時間的期望值,E(DN),二階期望值, E(D2N),變異數,Var(DN),共變異數,Cov(D1,DN),和相關係數,Corr(D1,DN)。 / In this thesis, our goal is to study the correlation coefficients of the departure process in the E_m/E_k/1 model.
Many authors conduct a lot of researches about the correlation coefficients of M/G/1 models and G/M/1 models. But what if the property of “memoryless" fails ?
To realize the correlation coefficient of E_m/E_k/1, we derive the methodology of N-step interdeparture time distribution which was presented by Luh in 1999. By adopting it, we can calculate the expectation, E(D_N), second order expectation, E(D_N^2), variance, Var(D_N), covariance, Cov(D_1,D_N), and correlation coefficients, Cov(D_1,D_N) of the system.
|
Page generated in 0.0687 seconds