DESCENDANT SET - AN EFFICIENT APPROACH FOR THE ANALYSIS OF POLLING SYSTEMS

Polling systems have been used to model a large variety of application s and much research has been devoted to the derivation of efficient al gorithms for computing the delay measures in these systems. Recent res earch efforts in this area, which have focused on the optimization of these systems, have raised the need for very efficient such algorithms . This work develops the descendant set approach as a general efficien t algorithm for deriving all moments of customer delay (in particular, mean delay) in these systems. The method is applied to a very large v ariety of model variations, including: 1) The exhaustive and gated ser vice policies, 2) Fractional service policies, 3) The cyclic visit ord er, 4) Arbitrary periodic visit orders (polling tables), and 5) Custom er routing. For most of these variations the method significantly outp erforms the algorithms commonly used today.