Online Hierarchical Scheduling Method for Dynamic Incremental Tasks

Mobile Edge Computing (MEC) involves offloading computation requests to the edge of the network, thereby diminishing bandwidth strain on the core network and reducing response times for user tasks. Current mobile edge computing research primarily focuses on static scenarios with a fixed number of applications, which cannot handle dynamic scenarios where mobile devices continuously and randomly generate applications as long-term task sources. The increase in the number of applications and the unpredictability of application generation time in dynamic scenarios pose new challenges for the design of scheduling algorithms. To tackle dynamic scenarios, this paper designs a random incremental application generation model. In this model, each mobile device randomly increases new applications with dependent subtasks. To manage the random arrival of new applications, a hierarchical scheduling strategy is proposed. This strategy determines the execution order of applications, selects subtask offloading locations, and updates the optimal execution decisions to schedule task offloading. Firstly, in the sequence pre-setting layer, the GSK (Gaining-sharing Knowledge) algorithm searches for the execution order of applications. Secondly, in the location selection layer, based on the priority of each subtask, the method uses an insertion-based strategy of HEFT (the Heterogeneous Earliest Finish Time) algorithm to select processors for executing the subtasks. Finally, in the decision update layer, the optimal execution decisions are updated based on the completion rate within the application deadline and the overall system completion time. Experimental results demonstrate that the proposed algorithm (GHED) enhances the completion rate of user applications within the stipulated deadline by at least 13.24% and reduces system completion time by at least 8.78% compared to other benchmark methods.