Systems and methods permit customers of a service provider network to specify various constraints on a desired fleet of virtual machine instances without having to specify the hardware types of instances to be included in the fleet. Instead, the customer can specify per-instance hardware constraints (number of CPUs, amount of memory, etc.) and job constraints (e.g., deadline, budget, application type, etc.). A provisioning service accesses an internal database containing instance cost data, instance availability data, and mappings between application type and fleet configurations to propose a fleet of instances that complies with the customer-specified per-instance hardware and job constraints, thereby freeing the customer from having to be conversant in the particular instances offered by the service provider.