In: Journal of the ACM, Vol. 41, No. 5, pages 903-942. 1994.
Abstract: In this paper, we study quantitative as well as qualitative properties of Fork-Join Queuing Networks with Blocking (FJQN/Bs). Specifically, we prove results regarding the equivalence of the behavior of a FJQN/B and that of its duals and a strongly connected marked graph. In addition, we obtain general conditions that must be satisfied by the service times to guarantee the existence of a long-term throughput and its independence on the initial configuration. We also establish conditions under which the reverse of a FJQN/B has the same throughput as the original network. By combining the equivalence result for duals and the reversibility result, we establish a symmetry property for the throughput of a FJQN/B. Last, we establish that the throughput is a concave function of the buffer sizes and the initial marking, provided that the service times are mutually independent random variables belonging to the class of PERT distributions that includes the Erlang distributions. This last result coupled with the symmetry property can be used to identify the initial configuration that maximizes the long-term throughput in closed series-parallel networks.
Keywords: Petri nets, finite buffers, fork-join queueing networks, marked graphs, networks with blocking, performance evaluation.