Methods and apparatus for flexible batch job scheduling in virtualization environments are disclosed. A descriptor for a batch job requested by a client is received at a job scheduling service. The descriptor comprises an indication of a time range during which a job iteration may be performed. A target time for executing the iteration is determined based on an analysis of a plurality of received descriptors. An indication of the target time at which the iteration is to be scheduled is provided to a selected execution platform.