On Throughput Approximation of Resource-Allocation Systems by Bottleneck Regrowing

摘要

Complex systems, such as manufacturing, logistics, or Web services, are commonly modeled as discrete event systems dealing with the resource-allocation problem. In particular, Petri nets (PNs) are a widely used formalism to model these systems. Although their functional properties have been extensively studied in the literature, their nonfunctional properties (such as throughput) have usually been ignored. In this brief, we focus on a PN subclass useful for modeling concurrent sequential processes with shared resources, termedinline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"tex-math notation="LaTeX"$S^{4}PR$/tex-math/inline-formulanets. For these nets, we present an iterative strategy that makes intensive use of mathematical programming problems to approximate system throughput. Initially, our strategy selects the slowest part (a subsystem) of the net. Then, the next slowest parts are considered. In each step, the throughput is computed solving analytically the underlying continuous-time Markov chain when feasible (or by simulation, otherwise). Since only certain subsystems are considered, the state-explosion problem inherent to the increasing net size is mitigated. We evaluate our strategy in a set of randomly generatedinline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"tex-math notation="LaTeX"$S^{4}PR$/tex-math/inline-formulanets. Our findings show that the throughput improves the upper throughput bound computation by almost 20 and that small portions of the net are enough to approximate system throughput.