Backups of workloads in a multi-tenant cloud computing environment are efficiently queued and scheduled. A method of backing up workloads for multiple tenants of a cloud computing system, includes the steps of determining a pool of workloads to be backed up during a time window, the workloads including workloads for a first tenant and workloads for a second tenant, placing a backup task for backing up each of the workloads in the pool in a scheduling queue and prioritizing the backup tasks according to backup parameters specified by the tenants, sizes of workload data to be backed up, and hardware constraints of a backup storage device executing the backups, and instructing the backup storage device to execute the backup tasks according to an order of the backup tasks in the scheduling queue.