A system and method for backing up virtual machines are disclosed. To better use the backup resources, an optimal set of virtual machines needing backup during a time window is generated. The optimal set depends on a total time for backing up each virtual machine needing backup and a cost metric that indicates a cost of not backing up the virtual machine during the time window. The optimal set also meets various system constraints that reflect the backup resource limitations. Performing backups according to the optimal set limits the number of missed backups and the number of service level agreement violations, thereby improving the backup performance without costly additions to its infrastructure.