Techniques are described for automatically scaling (or “auto scaling”) compute resources—for example, virtual machine (VM) instances, containers, or standalone servers—used to support execution of service-oriented software applications and other types of applications that may process heterogeneous workloads. The resource requirements for a software application can be approximated by measuring “worker pool” utilization of instances of each service, where a worker pool represents a number of requests that the service can process concurrently. A scaling service can thus be configured to scale the compute instances provisioned for a service in proportion to worker pool utilization, that is, compute instances can be added as the fleet's worker pools become more “busy,” while compute instances can be removed when worker pools become inactive.