A heuristic for optimum allocation of real-time service workflows

In this paper, the problem of optimum allocation of real-time service workflows over a set of heterogeneous resources is tackled. In previous works, this problem was formally stated in terms of a Mixed-Integer Non-Linear Programming optimization program, that could be solved by recurring to commercial solvers. However, due to the big dimension of the solution space to be searched, finding the absolutely optimum solution: might take too much time in order to be concretely useful; it may preclude the use of these techniques in large-scale infrastructures; it makes the technique hardly usable adaptively in response to corrective actions that may be needed when some bad event occurs while the services are running (e.g., hardware-level failures). Therefore, in this paper a heuristic algorithm based on graph-matching is introduced that may find very efficiently a reasonably good, albeit non-necessarily optimum, solution. The algorithm is described, and its performance assessed by a set of synthetic experiments.