We present two heuristic mesh-partitioning methods, both of which build on the ant-colony algorithm (ACA) in order to improve the quality of the mesh partitions. The first method augments the ACA with a multilevel paradigm, while the second focuses on improving the initial partition that is submitted to the ACA. The two methods are experimentally compared with the well-known mesh-partitioning programs pMETIS 4.0 and Chaco 2.0.