A tight bound on the throughputof queueing networks with blocking

In this paper, we present a bounding methodology that allows to compute a tight lower boundon the cycle time of fork--join queueing networks with blocking and with general service timedistributions. The methodology relies on two ideas. First, probability masses fitting (PMF)discretizes the service time distributions so that the evolution of the modified network can bemodelled by a Markov chain. The PMF discretization is simple: the probability masses onregular intervals are computed and aggregated on a single value in the corresponding interval.Second, we take advantage of the concept of critical path, i.e. the sequence of jobs that coversa sample run. We show that the critical path can be computed with the discretizeddistributions and that the same sequence of jobs offers a lower bound on the original cycletime. The tightness of the bound is shown on computational experiments. Finally, we discussthe extension to split--and--merge networks and approximate estimations of the cycle time.....