Fluid Models of Parallel Service Systems under FCFS

Friday, May 18, 2018 - 10:00am - 10:50am
Lind 305
Hanqin Zhang (National University of Singapore)
We study deterministic fluid approximation models of parallel service systems, operating under first come first served policy (FCFS), when the service time distributions may depend on both the server and the customer type. We explore the relations between fluid models and the properties of stability, resource pooling, and matching rates. We find that stability and resource pooling are determined by the unique fluid model in two cases: when service rates are of product form, consisting of the ratio of server speed and customer type average work requirement, and when the bipartite compatibility graph is a tree or a complete graph. For these cases we are able to give a complete description of the unique fluid limit model of the system, which has piecewise linear sample paths. In general, when service rates depend on both server and customer type and the graph is not one of the above, we find that the fluid model may not be unique, and stability and resource pooling cannot be determined from first moment information. Matching rates between pairs of compatible server and customer types cannot be determined from the fluid model, unless the compatibility graph is complete or a tree. In particular, we discuss an example of Foss and Chernova (Queueing System, 1998), and show by simulation that matching rates and stability depend on the service time distributions beyond the first moments. Further simulations show that matching rates depend on distributions of service times even when service times depend only on the server type and the fluid model is unique. On the other hand, we solve a static planning linear program similar to Harrison and Lopez (Queueing System, 1999), and obtain a maximum throughput compatibility sub-graph that is a tree or a forest. We show that using only links of this sub-graph, FCFS is a throughput optimal policy. We also show that FCFS is a throughput optimal policy for systems with product-form processing rates.