26-28 Jun 2019 Bordeaux (France)
An EPTAS for scheduling fork-join task graphs with communication delays
Klaus Jansen  1  , Oliver Sinnen  2@  , Huijun Wang  3  
1 : University of Kiel
2 : University of Auckland
3 : University of Auckland

In this talk we present an EPTAS for the scheduling of fork-join task graphs with communication delay on homogeneous processors, P|fork-join,c_ij|C_max. The EPTAS uses an integer program that selects configurations of task placements which satisfy a given makespan and covers all tasks. The integer program is a feasibility test that is repeated over the range of possible optima in a binary search to find a solution, which is guaranteed to be within a 1 + ε factor of the optimum. Communication costs are dealt with effectively for this fork-join graph structure. A simpler version can be used on a fork or join DAG only. It is shown that these run in time exponential in terms of 1/ε and polynomial in terms of the input size.

  • Poster
Online user: 1