Talks (sorted by speaker) > Sinnen Oliver

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.