A linear programming approach to stability, optimisation and performance analysis for Markovian multiclass queueing networks

Our object of study is a multiclass queueing network which consists of a collection of (connected) single-server stations. Exogenous arrivals into the system form independent Poisson streams, service times are exponential and we have Markovian routing of customers between stations. Recent results concerning linear programming (LP) based approaches enable us to establish a simple and intuitive stability condition. This is of interest in its own right, but also enables us to progress with a study of optimal scheduling and performance analysis. Our methodology here is also based on LP. A primal– dual approach exploits the fact that the system satisfies (approximate) conservation laws to yield performance guarantees for a natural index-based scheduling heuristic. We are also able to analyse the performance of an arbitrary priority policy.