Abstract:
© 2021 Elsevier B.V. This paper presents an EPTAS for scheduling fork-join task graphs with communication delay on homogeneous processors, denoted as P|fork-join,cij|Cmax in the α|β|γ-notation. The fork-join structure is a basic structure found in many parallel computations. The algorithm uses an integer program as the feasibility test and searches for a solution which would be guaranteed to be within a 1+ϵ factor of the optimum. It is shown that this runs in time exponential in terms of 1/ϵ and polynomial in terms of the input size. Communication costs are dealt with effectively for this fork-join graph structure. The EPTAS is also adapted to scheduling independent tasks with release times and deadlines, which is denoted as P|rj|Lmax.
