Backfill scheduling for embarrassingly parallel jobs. A disclosed method includes: receiving an initial schedule having a plurality of jobs scheduled over time on a plurality of nodes, determining that a first job can be split into a plurality of sub-tasks that can respectively be performed in parallel on different nodes, splitting the first job into the plurality of sub-tasks, and moving a first sub-task from its position in the initial schedule to a new position to yield a first revised schedule.