臺灣博碩士論文加值系統

在這篇論文中我要介紹兩種解馬可夫模型的方法-光譜拓展法和矩陣幾何法。許多二維的模型可以用這兩個方法來解，這篇論文中我所用的是M/M/N的列隊模型。在文中我們會比較兩個方法的差異。實驗中，我們主要的目的是要比較這兩個方法的速度與精確度。

In this paper, I want to introduce spectral expansion method and matrix-geometric method on a class of Markov models. Many two-dimensional Markov models whose state space is a semi-infinite strip can be solved efficiently by these two methods. The example described in the context is an M/M/N queue with general breakdowns and repairs. The objective of experiments is to compare the effectiveness of computing the average queue size with two different methods. The detail of the algorithms will also be presented in this paper.

Contents
1. Introduction …………………………………………………………1
2. The Markov model……………………………………………………2
3. Spectral expansion method……………………………………………4
3.1 A description of the method………………………………………4
3.2 Algorithm for spectral expansion method…………………………6
4. Matrix-geometric method……………………………………………9
4.1 A description of the method…………………………………………9
4.2 Algorithm for matrix-geometric method…………………………10
5. Examples and Numerical results……………………………………11
5.1 The multi-server example…………………………………………11
5.1.1 Numerical result………………………………………………13
5.2 Two severs in tandem……………………………………………14
5.2.1 Numerical result…………………………………………15
6. Comparison…………………………………………………………16
7. Conclusion…………………………………………………………23
Reference…………………………………………………………24
List of figures
1. Multi-server with breakdowns………………………………………12
2. Numerical result of the multi-server example…………………13
3. Two servers in tandem with feedback………………………………14
4. E(J) of the two servers in tandem example………………………15
5. E(I) of the two servers in tandem example………………………16
6. Compare two methods in computing time with different arrival rate………19
7. Compare two methods in different N with arrival rate 0.8…20
8. Compare two methods in different N with arrival rate 1.05…21
9. Number of iterations for computing R…………………………22
List of tables
1. Trade-off between accuracy and complexity………………………17
2. Trade-off between accuracy and the number h for computed E(J)……23

[1] R. Chakka and I. Mitrani, A numerical solution method for multiprocessor systems with general breakdowns and repairs, Proceedings of the 6th International Conference on Performance Tools and Techniques, Edinburgh, 1992, page 289-304.
[2] R. Chakka and I. Mitrani, Heterogeneous multiprocessor systems with breakdowns: Performance and optimal repair strategies, Theoretical Computer Science 125(1994)91-109.
[3] M. Ettl and I. Mitrani, Applying spectral expansion in evaluating the performance of multiprocessor systems, Proceedings of the 3rd QMIPS Workshop Part 1, eds. O. J. Boxma and G. M. Koole, CWITRACT, Amsterdam, 1994, page 45-58.
[4] R. Chakka and I. Mitrani, Approximate solutions for open networks with breakdowns and repairs, in: Stochastic Networks: Theory and Applications, eds. F. P. Kelly, S. Zachary and I. Ziedins, Oxford University Press, Oxford, 1996.
[5] A. I. Elwalid, D. Mitra and T. E. Stern, Statistical multiplexing of Markov modulated sources: Theory and computational algorithms, in: Teletraffic and Data Traffic in a Period of Change, eds. A. Jensen and V. B. Iversen, International Teletraffic Congress-13, Copenhagen, 1991, page 495-500.
[6] N. U. Prabhu and Y. Zhu, Markov-Modulated Queuing Systems, QUESTA 5(1989) 215-246.
[7] M. F. Neuts, Matrix Geometric Solutions in Stochastic Models, John Hopkins University Press, Baltimore, Md. (1981).
[8] Mitrani and R. Chakka, Spectral expansion solution for a class of Markov models: Application and comparison with the matrix-geometric method, Performance Evaluation 23(1995) 241-260.
[9] Gohberg, P. Lancaster and L. Rodman, Matrix Polynomials, Academic Press, New York (1982).
[10] Jennings, Matrix Computations for Engineers and Scientists, Wiley, New York (1977).
[11] L. Gun, Experimental Results on Matrix-Analytical Solution Techniques- Extensions and Comparison, Stoch. Models 5(4) (1989) 669-682.
[12] G. Konheim and M. Resier, A queuing model with finite waiting room and blacking, Journal of the ACM23 (1976) 328-341.
[13] H. R. Gail, S. L. Hantler and B. A. Taylor, Spectral Analysis of M/G/1 Type Markov Chains, RC17765, IBM Research Division, 1992.