Research
Seminars
Department Series
[an error occurred while processing this directive]
The Determination of the Equilibrium Probabilities in Systems with Two Queues by Using Eigenvalues. |
|
Winfried Grassmann Department of Computer Science University of Saskatchewan |
|
We consider systems with 2 Markovian queues. The events that can occur are restricted to single arrivals, changes of queues by individuals, and departures by individuals. Also, one of the two queues must be restricted to some finite number N. Such systems can be formulated as Markov chains with block-tridiagonal structures, where each block is again tridiagonal. We propose to solve this system by using eigenvalues. This procedure we employ is based on so called Sturm sequences. These Sturm sequences allow one to use a generalization of the binary search to find all eigenvalues. This procedure is extremely efficient, but there are problems of numerical stability as N increases. By exploiting regularities of the system, one can also find each eigenvectors in essentially constant time. Once all eigenvalues and eigenvectors are known, the problem can be solved readily.
Dr. Winfried Grassmann obtained his Dr. oec. from the University of Zurich, Switzerland with summa cum laude in 1967. While completing his doctoral thesis, he was an employee of Swissair, where he developed systems for inventory control. These systems remained in place long after he left the company January 1969 to join the recently created department of Computer Science of the University of Saskatchewan. He later pioneered the so-called randomization method as a numerical tool, a method which is now widely applied in performance evaluation. He is also the inventor of the GTH (Grassmann/Taksar/Heyman) method. For his work, Dr. Grassmann received the Merit Award of the Canadian Operational Research Society. Dr. Grassmann is associate editor of the INFORMS Journal on Computing, and also of INFOR, the Canadian Operational Research Society.
[an error occurred while processing this directive]