Resource controllability of business processes (BPs) is the problem of executing a BP by assigning resources to tasks, while satisfying a set of constraints, according to the outcome of a few uncontrollable events that we only observe during execution. Recent research addressed resource controllability of acyclic BPs where the choices of the XOR paths to take were out of control. However, a formal model of BP to reason on resource controllability is still missing. Thus, the precise mathematical definitions of controllability problems, their semantics and complexity analysis, have remained unexplored. To bridge this gap, we propose a hierarchy of 8 classes of Business Processes with Resources and Uncertainty (BPRUs) to address controllable and uncontrollable resource assignments in combination with controllable and uncontrollable choices of the XOR paths to take. We define consistency of BPRs (i.e., BPRUs without uncertainty) and prove that deciding it is NP-complete. We define strong controllability of BPRUs and prove that deciding it is either NP-complete or Sigma_2^p-complete depending on the class. We define weak and dynamic controllability of BPRUs and prove that deciding them is Pi_2^p-complete and PSPACE-complete, respectively.

On the Complexity of Resource Controllability in Business Process Management

Zavatteri, Matteo
;
Rizzi, Romeo;Villa, Tiziano
2020-01-01

Abstract

Resource controllability of business processes (BPs) is the problem of executing a BP by assigning resources to tasks, while satisfying a set of constraints, according to the outcome of a few uncontrollable events that we only observe during execution. Recent research addressed resource controllability of acyclic BPs where the choices of the XOR paths to take were out of control. However, a formal model of BP to reason on resource controllability is still missing. Thus, the precise mathematical definitions of controllability problems, their semantics and complexity analysis, have remained unexplored. To bridge this gap, we propose a hierarchy of 8 classes of Business Processes with Resources and Uncertainty (BPRUs) to address controllable and uncontrollable resource assignments in combination with controllable and uncontrollable choices of the XOR paths to take. We define consistency of BPRs (i.e., BPRUs without uncertainty) and prove that deciding it is NP-complete. We define strong controllability of BPRUs and prove that deciding it is either NP-complete or Sigma_2^p-complete depending on the class. We define weak and dynamic controllability of BPRUs and prove that deciding them is Pi_2^p-complete and PSPACE-complete, respectively.
978-3-030-66497-8
BPRU, resource controllability, complexity analysis
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1043537
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact