Temporal and Resource Controllability of Workflows Under Uncertainty

Workflow technology has long been employed for the modeling, validation and execution of business processes. A workflow is a formal description of a business process in which single atomic work units (tasks), organized in a partial order, are assigned to processing entities (agents) in order to achieve some business goal(s). Workflows can also employ workflow paths (projections with respect to a total truth value assignment to the Boolean variables associated to the conditional split connectors) in order (not) to execute a subset of tasks. A workflow management system coordinates the execution of tasks that are part of workflow instances such that all relevant constraints are eventually satisfied. Temporal workflows specify business processes subject to temporal constraints such as controllable or uncontrollable durations, delays and deadlines. The choice of a workflow path may be controllable or not, considered either in isolation or in combination with uncontrollable durations. Access controlled workflows specify workflows in which users are authorized for task executions and authorization constraints say which users remain authorized to execute which tasks depending on who did what. Access controlled workflows may consider workflow paths too other than the uncertain availability of resources (users, throughout this thesis). When either a task duration or the choice of the workflow path to take or the availability of a user is out of control, we need to verify that the workflow can be executed by verifying all constraints for any possible combination of behaviors arising from the uncontrollable parts. Indeed, users might be absent before starting the execution (static resiliency), they can also become so during execution (decremental resiliency) or they can come and go throughout the execution (dynamic resiliency). Temporal access controlled workflows merge the two previous formalisms by considering several kinds of uncontrollable parts simultaneously. Authorization constraints may be extended to support conditional and temporal features. A few years ago some proposals addressed the temporal controllability of workflows by encoding them into temporal networks to exploit "off-the-shelf" controllability checking algorithms available for them. However, those proposals fail to address temporal controllability where the controllable and uncontrollable choices of workflow paths may mutually influence one another. Furthermore, to the best of my knowledge, controllability of access controlled workflows subject to uncontrollable workflow paths and algorithms to validate and execute dynamically resilient workflows remain unexplored. To overcome these limitations, this thesis goes for exact algorithms by addressing temporal and resource controllability of workflows under uncertainty. I provide several new classes of (temporal) constraint networks and corresponding algorithms to check their controllability. After that, I encode workflows into these new formalisms. I also provide an encoding into instantaneous timed games to model static, decremental and dynamic resiliency and synthesize memoryless execution strategies. I developed a few tools with which I carried out some initial experimental evaluations.