An elastic scaling cloud-hosted batch application system and method that performs automated elastic scaling of the number of compute instances used to process batch applications in a cloud computing environment. The system and method use automated elastic scaling to minimize job completion time and monetary cost of resources. Embodiments of the system and method use a workload-driven approach to estimate a work volume to be performed. This is based on task arrivals and job execution times. Given the work volume estimate, an adaptive controller dynamically adapts the number of compute instances to minimize the cost and completion time. Embodiments of the system and method also mitigate startup delays by computing a work volume in the near future and gradually starting up additional compute instances before they are needed. Embodiments of the system and method also ensure fairness among batch applications and concurrently executing jobs.