# Research on Multi-DAG Satellite Network Task Scheduling Algorithm Based on Cache-Composite Priority
## 2 Related Research  
Most current research on task scheduling involves splitting tasks into subtasks. Due to the clear dependency relationship between subtasks, the current research mainly focuses on DAG task scheduling. [PERSON] et al. proposed a method to generate a scheduling list, arrange the list according to task priority, select the task with the highest priority for scheduling according to the list, and use a strategy to allocate tasks to appropriate processors in order to minimize the predefined objective function. This method is the most well known HEFT algorithm [13]. [PERSON] et al. improved the HEFT algorithm by not only considering the completion time of the current task, but also predicting the completion time of the subsequent tasks and including comprehensive considerations to obtain better scheduling decisions [14]. [PERSON] et al. took load balancing as the optimization objective and proposed the LB-HEFT algorithm based on the HEFT algorithm. This algorithm improved the performance of load balancing by 72.59% [15]. [PERSON] et al. used the actual communication time between tasks to replace the average communication time in the task priority evaluation phase and accurately analyzed the impact of heterogeneous data transmission time on task priority. When matching edge nodes for tasks, the influence of the entire DAG task completion time on the current task matching process was explored recursively, and a novel pruning mechanism was developed to prune the search process in order to reduce the time complexity of the algorithm [16]. [PERSON] et al. introduced a forward-looking function during the determination of task priorities and processor matching phase. This involved considering the priority of the current task and its immediate successor tasks to adjust the priority of the current task. Additionally, the matching of the current task to a server was guided by evaluating the minimum completion time of the entire task [17]. [PERSON] et al. further extended this forward-looking function by introducing a pre-scheduling phase before determining task priorities and server matching. In this phase, the PEFT algorithm [18] was used to preplan a feasible solution for task scheduling, and this solution was used as a guide to analyze the impact of the entire DAG task completion time on task priority determination and server matching, further reducing the makespan [19]. In addition, evolutionary algorithms are also suitable for solving DAG task scheduling problems. [PERSON] et al. proposed a DAG task scheduling problem with the optimization goal of processing latency and used a genetic algorithm to solve it [20]. The above papers mainly studied how to schedule a single DAG with multiple resources. These methods have been widely used and are basically mature. However, with the increasing demand for low cost and resource-sharing application systems, the scheduling problem of multi-DAG tasks needs to be solved. [PERSON] et al. proposed the well-known Fairness algorithm. The basic idea is to calculate and compare the slowdown values of different DAGs after scheduling tasks, then select the DAG with the largest slowdown value from multiple DAGs, and use the corresponding single-DAG scheduling algorithm for scheduling. This process is repeated until all tasks in all DAGs are scheduled. Experimental results demonstrate that the Fairness scheduling algorithm effectively improves the relative fairness of multiple tasks [21]. [PERSON] et al. proposed an intelligent scheduling method for multi-DAG jobs using deep reinforcement learning, called Smart-mDAG. It is a job-specific scheduling method that adjusts the scheduling policy based on diverse dependencies to minimize the makespan [22]. The above algorithm is suitable for situations where the priorities of individual DAGs are not defined, but in practice, the priorities of individual tasks are often different. [PERSON] et al. proposed an algorithm called Backfill, which effectively solved this problem.