Many real-world engineering problems can be expressed in terms of partial differential equations and solved by using the finite-element method, which is usually parallelized, i.e. the mesh is divided among several processors. To achieve high parallel efficiency it is important that the mesh is partitioned in such a way that workloads are well balanced and interprocessor communication is minimized. In this paper we present an enhancement of a technique that uses a nature-inspired metaheuristic approach to achieve higher-quality partitions. The so-called multilevel ant-colony algorithm, which is a relatively new metaheuristic search technique for solving optimisation problems, was applied and studied, and the possible parallelisation of this algorithm is discussed. The multilevel ant-colony algorithm performed very well and is superior to classical k-METIS and Chaco algorithms; it is even comparable with the combined evolutionary/multilevel scheme used in the JOSTLE evolutionary algorithm and returned solutions that are better than the currently available solutions in the Graph Partitioning Archive.