Optimal Scheduling for Precedence-Constrained Applications on Heterogeneous Machines

High-Performance Computing (HPC) is a growing necessity of our technological society, HPC demands high loads of parallel computing jobs, an optimal scheduling of the parallel applications tasks is a priority to meet the demands of its users on time. Branch-and-bound (BB) Algorithms and Mathematical Programming (MP) solve complex optimization problems in an optimal manner, some MP or BB even have parallel computing capabilities, making them suitable solutions to solve real-world problems. In this paper, we propose two exact algorithms, a BB and a MP Model for scheduling precedence-constrained applications, on heterogeneous computing systems, as far as we known the first ones on his kind presented in the state of the art. One major contribution of the work is the proposed formulations of the objective function in both methods. Experimental results obtained more than twenty optimal values for synthetic applications from the literature.