A framework for simulation-based optimization of business process models

摘要

The Assignment Problem is a classical problem in the field of combinatorial optimization, having a wide range of applications in a variety of contexts. In general terms, the Assignment Problem consists of determining the best assignment of tasks to agents according to a predefined objective function. Different variants of the Assignment Problem have been extensively investigated in the literature in the last 50 years. In this work, we introduce and analyze the problem of optimizing a business process model with the objective of finding the most beneficial assignment of tasks to agents. Despite similarities, this problem is distinguished from the traditional Assignment Problem in that we consider tasks to be part of a business process model, being interconnected according to defined rules and constraints. In other words, assigning a business process to agents is a more complex form of the Assignment Problem. Two main categories of business processes, assignment-independent and assignment-dependent, are distinguished. In the first category, different assignments of tasks to agents do not affect the flow of the business process, while processes in the second category contain critical tasks that may change the workflow, depending on who performs them. In each category several types of processes are studied. Algorithms for finding optimal and near-optimal solutions to these categories are presented. For the first category, depending on the type of process, the Hungarian algorithm is combined with either the analytical method or simulation to provide an optimal solution. For the second category, we introduce two algorithms. The first one finds an optimal solution, but is feasible only when the number of critical tasks is small. The second algorithm is applicable to large number of critical tasks, but provides a near-optimal solution. In the second algorithm a hill-climbing heuristic method is combined with the Hungarian algorithm and simulation to find an overall near-optimal solution. A series of tests is conducted which demonstrates that the proposed algorithms efficiently find optimal solutions for assignment-independent and near-optimal solutions for assignment-dependent processes.