Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems: a Dataflow-driven Approach Using S-Net

In this paper we present the implementation of a concurrent ant colony optimisation based solver for the combinatorial Single Machine Total Weighted Tardiness Problem (ACOSMTWTP). We introduce S-Net, a coordination language based on dataflow principles, report on the performance of the implementation and compare it against a sequential and a parallel implementation of the same algorithm in C. As the workload of the optimisation algorithm is highly irregular we consider this application to be an important use-case for runtime measurement directed optimisations of the coordination rogram as much as for guiding optimisations of numerical code.