Fluid Models of Parallel Service Systems Under FCFS

• 成果类型: Article
• 署名作者: Nov, Yuval; Weiss, Gideon; Zhang, Hanqin
• 署名单位: University of Haifa; National University of Singapore
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.2102
• 发表日期: 2022
• 页码: 1182-1218
• 关键词: heavy traffic analysis; scheduling networks; dynamic control; STABILITY; instability; 1st-come; policies; QUEUE; optimality; Servers

摘要

We study deterministic fluid approximation models of parallel service systems with a fixed set of servers, operating under first come first served (FCFS) policy, 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 given by 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 model of the system. In general, when service rates depend on both server and customer type and the graph is not one of those listed previously, stability and resource pooling cannot be determined from first moment information. Matching rates between pairs of compatible server and customer type cannot be determined from the fluid model unless the compatibility graph is complete or a tree. In particular, we discuss an example 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 the 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 and obtain a maximum throughput compatibility subgraph that is a tree or a forest. We show that using only links of this subgraph, FCFS is a throughput optimal policy. We also show that FCFS is a throughput optimal policy for systems with product form service rates.