期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2008
卷号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：In this paper, we present a bounding methodology that allows to compute a tight lower bound
on the cycle time of fork--join queueing networks with blocking and with general service time
distributions. 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 be
modelled by a Markov chain. The PMF discretization is simple: the probability masses on
regular 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 covers
a sample run. We show that the critical path can be computed with the discretized
distributions and that the same sequence of jobs offers a lower bound on the original cycle
time. The tightness of the bound is shown on computational experiments. Finally, we discuss
the extension to split--and--merge networks and approximate estimations of the cycle time.
关键词：queueing networks, blocking, throughput, bound, probability masses fitting,
critical path.
