\(\textbf {Single-Stage Scheduling :}\)  For the single-stage job scheduling
problem, many heuristic algorithms have been proposed to minimize
CCT, including heuristic algorithms [1]}, [2]}, [3]}, [4]}.
Orchestra [1]} is perhaps the first work to mention
the concept of coflow and shows that even a simple FIFO algorithm
can significantly improve coflow performance. Coflow abstraction is
later formally defined in [6]}. Varys [2]}
proposes the smallest-effective-bottleneck-first (SEBF) and minimum-allocation-for-desired-duration
(MADD) heuristic algorithms to greedily schedule coflows according
to the bottleneck completion time of coflow to minimize CCT and meet
the deadline of coflow at the same time. Barrat [3]}
and Stream [4]} both aim at decentralized coflow scheduling,
and Barrat [3]} exploits multiplexing to prevent head-of-line
blocking to small coflows. There is also some theoretical work [11]}, [12]}, [13]}
aimed at minimizing the approximate algorithm of the total weighted
CCT. [11]} provided the first deterministic algorithm
with a constant approximation ratio of \(\frac{67}{3}\)  to minimize
the total weighted CCT. [12]} presented a 12-approximation
ratio algorithm by reducing to concurrent open shop problem, and [13]}
further proposed a 5-approximation ratio algorithm by relaxing the
problem to linear programming (LP). The work as mentioned above abstracts
the network topology as a big non-blocking switch without considering
the constraints of network resources. Now, several research works
have considered network resource constraints and combined routing
and resource scheduling to minimize CCT [17]}, [18]}.
Rapier [17]} is the first algorithm that considers
routing and scheduling jointly to minimize CCT. However, it is a heuristic
solution and cannot provide theoretical performance guarantees. Next,
Tan et al. [18]} proposed a rounding-based randomization
algorithm for single coflow and online algorithms to provide performance
guarantees for multiple coflow routing and scheduling. Recently, a
distributed bottleneck aware coflow scheduling algorithm [21]}
was proposed to minimize CCT by reducing network bottlenecks and improving
link capacity utilization. However, these algorithms focus on minimizing
CCT without considering the dependencies among coflows of multi-stage
jobs.
