A heuristic algorithm for stochastic partitioning of process networks

In this paper, we study the problem of partitioning networks of processes under chance constraints. This problem arises in the field of compilation for multi-core processors. The theoretical equivalent for the case we consider is the Node Capacitated Graph Partitioning with uncertainty affecting the weights of the vertices. For solving this problem we propose an approximate algorithm which takes benefit of the available experimental data through a sample-based approach combined with a randomized greedy heuristic, originally developed for the deterministic version. Our computational experiments illustrate the algorithm ability to efficiently obtain robust solutions.