  There has been a considerable amount of interest in recent years in the
problem of workflow satisfiability, which asks whether the existence of
constraints in a workflow specification makes it impossible to allocate
authorized users to each step in the workflow. Recent developments have seen
the workflow satisfiability problem (WSP) studied in the context of workflow
specifications in which the set of steps may vary from one instance of the
workflow to another. This, in turn, means that some constraints may only apply
to certain workflow instances. Inevitably, WSP becomes more complex for such
workflow specifications. Other approaches have considered the possibility of
associating costs with the violation of `soft' constraints and authorizations.
Workflow satisfiability in this context becomes a question of minimizing the
cost of allocating users to steps in the workflow. In this paper, we introduce
new problems, which we believe to be of practical relevance, that combine these
approaches. In particular, we consider the question of whether, given a
workflow specification with costs and a `budget', all possible workflow
instances have an allocation of users to steps that does not exceed the budget.
We design a fixed-parameter tractable algorithm to solve this problem
parameterized by the total number of steps, release points and xor branchings.
