  Directed Acyclic Graph (DAG) scheduling in a heterogeneous environment is
aimed at assigning the on-the-fly jobs to a cluster of heterogeneous computing
executors in order to minimize the makespan while meeting all requirements of
scheduling. The problem gets more attention than ever since the rapid
development of heterogeneous cloud computing. A little reduction of makespan of
DAG scheduling could both bring huge profits to the service providers and
increase the level of service of users. Although DAG scheduling plays an
important role in cloud computing industries, existing solutions still have
huge room for improvement, especially in making use of topological dependencies
between jobs. In this paper, we propose a task-duplication based learning
algorithm, called \textit{Lachesis}, for the distributed DAG scheduling
problem. In our approach, it first perceives the topological dependencies
between jobs using a specially designed graph convolutional network (GCN) to
select the most likely task to be executed. Then the task is assigned to a
specific executor with the consideration of duplicating all its precedent tasks
according to a sophisticated heuristic method. We have conducted extensive
experiments over standard workload data to evaluate our solution. The
experimental results suggest that the proposed algorithm can achieve at most
26.7\% reduction of makespan and 35.2\% improvement of speedup ratio over seven
strong baseline algorithms, including state-of-the-art heuristics methods and a
variety of deep reinforcement learning based algorithms.
