CONCAVITY OF QUEUING-SYSTEMS WITH NBU SERVICE TIMES

This paper establishes structural properties for the throughput of a l arge class of queueing networks with i.i.d. new-better-than-used servi ce times. The main result obtained in this paper is applied to a wide range of networks, including tandems, cycles and fork-join networks wi th general blocking and starvation (as well as certain networks with s plitting and merging of traffic streams), to deduce the concavity of t heir throughput as a function of system parameters, such as buffer and initial job configurations, and blocking and starvation parameters. T hese results have important implications for the optimal design and co ntrol of such queueing networks by providing exact solutions, reducing the search space over which optimization need be performed, or establ ishing the convergence of optimization algorithms. In order to obtain results for such disparate networks in a unified manner, we introduce the framework of constrained discrete event systems (CDES), which enab les us to characterize any permutable and non-interruptive queueing ne twork through its constraint set. The main result of this paper establ ishes comparison properties of the event occurrence processes of CDES as a function of the constraint sets, which are then translated into t he above-mentioned concavity of the throughput as a function of system parameters in the context of queueing networks.