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. We present two heuristic mesh-partitioning methods, both of which build on the multiple ant-colony algorithm in order to improve the quality of the mesh partitions. The first method augments the multiple ant-colony algorithm with a multilevel paradigm, whereas the second uses the multiple ant-colony algorithm as a refinement to the initial partition obtained by vector quantization. The two methods are experimentally compared with the well-known mesh-partitioning programs, p-METIS and Chaco.