With the growth of Utility Grids and various Grid market infrastructures, the need for efficient and cost effective scheduling algorithms is also increasing rapidly, particularly in the area of meta-scheduling. In these environments, users not only may have conflicting requirements with other users, but also they have to manage the trade-off between time and cost such that their applications can be executed most economically in the minimum time. Thus, selection of the best Grid resources becomes a challenge in such a competitive environment. This paper presents three novel heuristics for scheduling parallel applications on Utility Grids that manage and optimize the trade-off between time and cost constraints. The performance of the heuristics is evaluated through extensive simulations of a real-world environment with real parallel workload models to demonstrate the practicality of our algorithms. We compare our scheduling algorithms against existing common meta-schedulers experimentally. The results show that our algorithms outperform existing algorithms by minimizing the time and cost of application execution on Utility Grids. © 2010 Elsevier B.V. All rights reserved.