Computing Degree of Parallelism for BPMN Processes

For sequential processes and workflows (i.e., pipelined tasks), each enactment (process instance) only has one task being performed at each time instant. When a process allows tasks to be performed in parallel, an enactment may have a number of tasks being performed concurrently and this number may change in time. We define the "degree of parallelism" of a process as the maximum number of tasks to be performed concurrently during an execution of the process. This paper initiates a study on computing degree of parallelism for three classes of BPMN processes, which are defined based on the use of BPMN gateways. For each class, an algorithm for computing degree of parallelism is presented. In particular, the algorithms for "homogeneous" and acyclic "choice- less" processes (respectively) have polynomial time complexity, while the algorithm for "asynchronous" processes runs in exponential time.