Browse Prior Art Database

Approximate solutions for multi-server queueing systems with Erlangian service times and an application to air traffic management

IP.com Disclosure Number: IPCOM000128041D
Original Publication Date: 1998-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 11 page(s) / 29K

Publishing Venue

Software Patent Institute

Related People

Marcos Escobar Fernandez de la Vega: AUTHOR [+3]

Related Documents

http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1998-234: URL

Abstract

This thesis is concerned with approximations of certain M(t)/G(t)/n(t)/n(t) + q queueing systems. More specifically, we are interested in such systems under very general conditions such as time-varying demand and capacity, and high utilization, including occasional oversaturation. Conditions such as these cannot be addressed with existing methodologies. We focus on M(t)/G(t)/n(t)/n(t) + q systems that call be approximated fairly well by M(t)/E k (t)/n(t)/n(t) + q systems. The latter have a large number of system states, that increase with the system parameters k, n, q and the utilization ratio, and involve complicated state transition probabilities. We propose numerical methods to solve the corresponding ChaplnanKolmogorov equations, exactly and approximately We first describe the exact solution technique of M(t)/Ek(t)/n(t)/n(t) + q queueing systems. Then, we develop two heuristic solution techniques of M(t)/E k (t)/n(t)//n(t) + q queueing systems, and provide the corresponding complete state descriptions. We compare the exact and approximate results to validate our heuristics and to select the heuristic that best approximates the exact results in steady-state and under stationary conditions. We also propose two algorithms to vary the number of servers in the system, since many real-life problems involve such changes in response to variations in demand. Further results using our ELC heuristic show that our practical approach behaves well under nonstationary conditions, including varying capacity, and during the transient period to steady-state. We conclude that our heuristic approach is an excellent alternative for studying and analyzing M(t)/E k (t)/n(t)/n(t) +q models and, as a by-product, many M(t)/G(t)/n(t)/n(t)+q systems that arise in practice. Finally, we present an application of the M(t)/E k (t)/n(t)/n(t) + q queueing model in the context of Air Traffic Management. This model appears to be a reasonable approach to estimating delays and congestion in an en-route sector in the air traffic system and call be used as an important building block in developing an analytical model of the entire Air Traffic Management system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 19% of the total text.

Page 1 of 11

 This record is the front matter from a document that appears on a server at MIT and is used through permission from MIT. See http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1998-234 for copyright details and for the full document in image form.

Approximate Solutions for Multi-Server Queueing Systems with Erlangian Service Times and an Application to Air Traffic Management

by

Marcos Escobar Fern andez de la, Vega
S.M. in O.R., Massachusetts Institute of Technology (1996) S.M. in E.E., Massachusetts Institute of Technology (1995) B. S. in E.C.E., Instituto Tecnologico y de Estudios Superiores de MonterreyCEM (1992)

Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy at the Massachusetts Institute of Technology
September.....1998
SIGNATURE OF author: [[signature omitted]]

Department of Electrical Engineering and Computer Science

September 11,.....1998
CERTIFIED BY: [[SIGNATURE OMITTED]]

Amedoo R. Odoni
T. Wilson Professor of Aeronautics and Astronautics and Civil and Environmental Engineering Thesis Supervisor
Richard C. Larson
Professor of Electrical Engineering
ACCEPTED BY: [[SIGNATURE OMITTED]]

Arthur C. Smith Chairman, Departmental Committee on Graduate Students ARCHIVES MASSACHUSETTS INSTITUTE OF TECHNOLOGY LIBRARIES Nov 16 1998

Massachusetts Institute of Technology Page 1 Dec 31, 1998

Page 2 of 11

Approximate solutions for multi-server queueing systems with Erlangian service times and an application to air traffic management

Approximate Solutions for Multi-Server Queueing Systems with Erlangian Service Times and an Application to Air Traffic Management

by

Marcos Escobar Fernandez de la Vega

Submitted to the Department of Electrical Engineering and Computer Science on September 11, 1998, in partial fulfillment of the requirements for the degree of Doctor of Philosophy

Abstract

This thesis is concerned with approximations of certain M(t)/G(t)/n(t)/n(t) + q queueing systems. More specifically, we are interested in such systems under very general conditions such as time-varying demand and capacity, and high utilization, including occasional oversaturation. Conditions such as these cannot be addressed with existing methodologies.

We focus on M(t)/G(t)/n(t)/n(t) + q systems that call be approximated fairly well by M(t)/Ek(t)/n(t)/n(t) + q systems. The latter have a large number of system states, that increase with the system parameters k, n, q and the utilization ratio, and involve complicated state transition probabilities. We propose numerical methods to solve the corresponding ChaplnanKolmogorov equations, exactly and approximately

We first describe the exact solution technique of M(t)/Ek(t)/n(t)/n(t) + q queueing systems. Then, we develop two heuristic solution techniques of M(t)/Ek(t)/n(t)//n(t) + q queueing systems, and provide the corresponding complete state descriptions. We compare the exact and approximate results to validate our heuristics and to select the heuristic...