Evaluation of a linear programming approach towards scheduling divisible real-time loads failure

Abstract

Recent research in real-time divisible load theory (RT-DLT) has addressed the problem of distributing arbitrarily parallelizable real-time workloads among processors which become available at different instants. In prior work, we proposed a Linear Programming based formulation of the problem of computing the completion time of a real-time workload on a given collection of processors. In this paper, we show via extensive experimental evaluation that thus LP based formulation significantly improves on the heuristic approximations that were the only techniques previously known for solving these problems.