ZENTURIO: A grid service-based tool for optimising parallel and grid applications. ZENTURIO [R. Prodan and T. Fahringer, “ZENTURIO: a grid middleware-based tool for experiment management of parallel and distributed applications”, J. Parallel Distrib. Comput. 64, 693–707 (2004; Zbl 02106042)] is a semi-automatic experiment management tool for performance and parameter studies of parallel and distributed applications on cluster and grid architectures. ZENTURIO has been designed as an Open Grid Services Architecture (OGSA) – compliant grid application built on top of standard web and grid services technologies. In this paper we first comparatively present various issues from our transition to an Open Grid Services Infrastructure (OGSI) – compliant prototype. Then we introduce a generic framework for solving NP-complete optimisation problems for parallel and grid applications. We present a case study on high throughput scheduling for large sets of computational tasks on the Grid using genetic algorithms. Our algorithm has a complexity of and 𝒪(n 2 ) delivers a fivefold improvement in solution over 500 generations in a grid withuniformly distributed computational resources.