.png){kind=icon}
.png){kind=icon}
Return
Maximizing throughput in queueing networks with limited flexibility
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2007.03.035.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We study a queueing network where customers go through several stages of processing, with the class of a customer used to indicate the stage of processing. The customers are serviced by a set of flexible servers, i.e., a server is capable of serving more than one class of customers and the sets of classes that the servers are capable of serving may overlap. We would like to choose an assignment of servers that achieves the maximal capacity of the given queueing network, where the maximal capacity is lambda* if the network can be stabilized for all arrival rates lambda < lambda* and cannot possibly be stabilized for all lambda > lambda*. We examine the situation where there is a restriction on the number of servers that are able to serve a class, and reduce the maximal capacity objective to a maximum throughput allocation problem of independent interest: the total discrete capacity constrained problem (TDCCP). We prove that solving TDCCP is in general NP-complete, but we also give exact or approximation algorithms for several important special cases and discuss the implications for building limited flexibility into a system. (c) 2007 Elsevier B.V. All rights reserved.
Keywords:
queueing
scheduling
approximation algorithms
flexible servers
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W