| Many physical systems, e.g., computer systems and store-and-forward packet switching networks, can be modelled as queueing networks with several types of customers and finite buffers. For these networks, in general, the determination of optimal resource-sharing strategies is a complex problem. Even though the optimal strategy can be found in some simple models, it may be complicated and difficult to implement in practice. Therefore, instead of finding optimal strategies, it may be preferable to obtain an easily-implemented near-optimal strategy. We deal with this problem in two directions: analytical and numerical methods.; In this dissertation, a single-server queueing system with several types of customers and one common finite buffer is considered first. The objective function is the average waiting cost in the system over an infinite horizon. The aim is to find optimal or sub-optimal server allocation strategies. It is shown that the well-known simple c(mu)-rule is a near-optimal server allocation strategy for a wide range of parameters by using martingale methods, coupling arguments and work-conserving properties.; Second, a general dynamic programming algorithm is derived for finding a good approximation to optimal strategies for certain Markov decision processes with countable state space and unbounded cost. This algorithm is illustrated on a basic dynamic routing problem by using some structural information on the value function and on optimal strategies.; Finally, for a completely symmetric single-server queueing system with several equal-length buffers, it is shown that always serving the shortest queue first in an optimal server allocation strategy to minimize the expected total discounted cost or average cost over an infinite horizon. Conversely, always serving the longest queue first is an optimal server allocation strategy to maximize the throughput of the system. The proofs are given: one is by value iteration, the other by coupling arguments.; The results in this dissertation plus some heuristic arguments can be used for finding optimal or sub-optimal resource-sharing strategies for existing store-and-forward packet switching networks. |
