Computational grids, with a collection of heterogeneous resources connected by heterogeneous networks, are being developed globally. Efficient partitioning of applications to exploit such grids is becoming an emerging area of research. Recent work in our group led to the creation of the PaGrid, an application that partitions meshes onto grids. The first version of PaGrid used a multilevel graph partitioning approach, with refinement based on minimization of total communication cost, augmented by execution time load balancing in the final uncoarsening phase. PaGrid was found to produce significantly better partitions for two models of heterogeneous computational grids, compared to two other partitioners, JOSTLE and METIS. In the present work we have redesigned PaGrid to minimize the estimated application execution time in all re.nement levels of the multilevel scheme. This has led to signi.cant improvements in partition quality.