Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Approximation Algorithms for Product-Form Networks In Chapter 8, several efficient algorithms for the exact solution of queueing networks are introduced. However, the memory requirements and computation time of these algorithms grows exponentially with the number of job classes in the system. For computationally difficult problems of networks with a large number of job classes, we resort to approximation methods. In Sections 9.1, 9.2, and 9.3 we introduce methods for obtaining such approximate results. The first group of methods is based on the MVA. The approximate methods that we present need much less memory and computation time than the exact MVA and. | Queueing Networks and Markov Chains Gunter Botch Stefan Greiner Hermann de Meer Kishor S. Trivedi Copyright 1998 John Wiley Sons Inc. Print ISBN 0-471-19366-6 Online ISBN 0-471-20058-1 Approximation Algorithms for Product-Form Networks In Chapter 8 several efficient algorithms for the exact solution of queueing networks are introduced. However the memory requirements and computation time of these algorithms grows exponentially with the number of job classes in the system. For computationally difficult problems of networks with a large number of job classes we resort to approximation methods. In Sections 9.1 9.2 and 9.3 we introduce methods for obtaining such approximate results. The first group of methods is based on the MVA. The approximate methods that we present need much less memory and computation time than the exact MVA and yet give very accurate results. The second approach is based on the idea that the mean number of jobs at a network node can be computed approximately if the utilization pi of this node is known. The sum of all the equations for the single nodes leads to the so-called system equation. By solving this equation we get approximate performance measures for the whole queueing network. In some cases it is enough to have upper and lower bounds to make some statements about the network. Therefore the third approach Section 9.4 deals with methods on how to get upper and lower bounds on performance measures of a queueing network. In Section 9.5 we introduce a method that allows intervals as input parameters. For other techniques that have been developed to analyze very large networks see ChYu83 SLM86 HsLa89 . 379 380 APPROXIMATION ALGORITHMS FOR PRODUCT-FORM NETWORKS 9.1 APPROXIMATIONS BASED ON THE MVA The fundamental equation of the MVA 8.31 describes the relation between the mean response time of a node when there are k jobs at the node and the mean number of jobs in that node with one job less in the network. Therefore to solve a queueing network
