Scalable linear programming based resource allocation for makespan minimization in heterogeneous computing systems

• We present a novel scheduling algorithm for heterogeneous computing environments.
• Uses groupings of similar tasks and machines to reduce the computational complexity.
• Computes upper and lower bounds on the optimal makespan.
• Schedule approaches a lower bound on the makespan as the number of tasks increases.
• Scheduling algorithm run time scales linearly with the number of tasks.

Resource management for large-scale high performance computing systems poses difficult challenges to system administrators. The extreme scale of these modern systems require task scheduling algorithms that are capable of handling at least millions of tasks and thousands of machines. Highly scalable algorithms are necessary to efficiently schedule tasks to maintain the highest level of performance from the system. In this study, we design a novel linear programming based resource allocation algorithm for heterogeneous computing systems to efficiently compute high quality solutions for minimizing makespan. The novel algorithm tightly bounds the optimal makespan from below with an infeasible schedule and from above with a fully feasible schedule. The new algorithms are highly scalable in terms of solution quality and computation time as the problem size increases because they leverage similarity in tasks and machines. This novel algorithm is compared to existing algorithms via simulation on a few example systems.