Valued Workflow Satisfiability Problem
This addresses workflow management systems where policies may make workflows unsatisfiable, providing a method to minimize violation costs, but it is incremental as it builds on existing workflow satisfiability problems.
The paper tackles the problem of finding the least bad assignment of users to workflow steps by assigning weights to policy and constraint violations, introducing the Valued Workflow Satisfiability Problem (Valued WSP) and showing it is fixed-parameter tractable for user-independent constraints, with algorithm performance evaluated against a mixed integer programming package.
A workflow is a collection of steps that must be executed in some specific order to achieve an objective. A computerised workflow management system may enforce authorisation policies and constraints, thereby restricting which users can perform particular steps in a workflow. The existence of policies and constraints may mean that a workflow is unsatisfiable, in the sense that it is impossible to find an authorised user for each step in the workflow and satisfy all constraints. In this paper, we consider the problem of finding the "least bad" assignment of users to workflow steps by assigning a weight to each policy and constraint violation. To this end, we introduce a framework for associating costs with the violation of workflow policies and constraints and define the \emph{valued workflow satisfiability problem} (Valued WSP), whose solution is an assignment of steps to users of minimum cost. We establish the computational complexity of Valued WSP with user-independent constraints and show that it is fixed-parameter tractable. We then describe an algorithm for solving Valued WSP with user-independent constraints and evaluate its performance, comparing it to that of an off-the-shelf mixed integer programming package.