Methods, apparatus, systems and articles of manufacture are disclosed for runtime scheduling of software executing on a heterogeneous system. An example apparatus includes in response to a variant compiler to generate a representation of an algorithm in a domain-specific language (DSL), a compilation auto-scheduler to generate a schedule based on configurations for processing elements of the heterogeneous system, the processing elements including at least a first and a second processing element, the variant compiler to compile variant binaries based on the schedule, each of the variant binaries associated with the algorithm in the DSL, the variant binaries including a first variant binary corresponding to the first processing element and a second variant binary corresponding to the second processing element, and an application compiler to generate a fat binary including a runtime scheduler to select one or more of the variant binaries to execute a workload based on the schedule.