A Linear Programming Approach for Scheduling Divisible Real-Time Workloads

摘要

In this paper we study the problem of distributing arbitrarilyrnparallelizable real-time workloads among processors whichrnbecome available at different instants of time. Specifically,rnwhen given a divisible job of a particular size and a fixedrnnumber of processors which may become available atrndifferent times, we determine the earliest completion time forrnthe job. This problem is formulated as a linear program (LP),rnand thereby provides a polynomial-time algorithm for solvingrnit. Through an extensive experimental evaluation we showrnthat this LP based formulation significantly improves on thernheuristic approximations previously known for solving thesernproblems.