An Approximation Scheme for Heterogeneous Parallel Task Scheduling in a Two-Stage Hybrid Flow Shop

Motivated by applications in cyber-physical systems (CPS), this paper introduces a two-stage hybrid flow shop with heterogeneous parallel tasks for minimizing makespan. There is only one processor for the first stage and m identical parallel processors for the second stage. Each task consists of several operations where the first operation executed at the first stage and afterwards the other operations with different processing time which can be executed concurrently at the second stage. The problem is proved to be NP-hard in the strong sense even when m = 2 and each task consists of only one operation at the second stage. To deal with the intractable problem, we first equivalently cast it to a two-stage multiprocessor schedule problem with clustered tasks. Then we show that the search for an optimal solution of the latter problem may be restricted to the schedules that execute the first-stage operations of each task cluster in a chain. Finally, we demonstrate the existence of an approximation scheme for this problem with a worst-case ratio bound of 1 + epsilon and a running time polynomial in 1/epsilon.