  We study Probabilistic Workflow Nets (PWNs), a model extending van der
Aalst's workflow nets with probabilities. We give a semantics for PWNs in terms
of Markov Decision Processes and introduce a reward model. Using a result by
Varacca and Nielsen, we show that the expected reward of a complete execution
of the PWN is independent of the scheduler. Extending previous work on
reduction of non-probabilistic workflow nets, we present reduction rules that
preserve the expected reward. The rules lead to a polynomial-time algorithm in
the size of the PWN (not of the Markov decision process) for the computation of
the expected reward. In contrast, since the Markov decision process of PWN can
be exponentially larger than the PWN itself, all algorithms based on
constructing the Markov decision process require exponential time. We report on
a sample implementation and its performance on a collection of benchmarks.
