Joint Scheduling and Offloading Schemes for Multiple Interdependent Computation Tasks in Mobile Edge Computing

Mobile Edge Computing (MEC) can sufficiently meet the computing demands of complex application consists of multiple interdependent tasks which can be represented by a directed acyclic graph (DAG). For tasks in a DAG, different scheduling orders and offloading decisions will generate different completion time, which further affects the quality of experiences (QoE). So it is important to study the scheduling and offloading schemes for tasks in MEC scenarios. To this end, we firstly designed a scheme that schedules tasks with the highest response ratio and offloads tasks to the optimal processor with optimization method for a DAG, which is termed as HRRO algorithm. Then, considering the complexity of the reality, we extended the HRRO to the ultra-dense MEC system and achieved the optimal joint scheduling and offloading scheme for multi-DAG based on the genetic algorithm, which can be concluded as HRRO-GA. Subsequently, to evaluate the performance of the algorithms, we conducted amounts of the simulation experiments and compared the results with several state-of-the-art algorithms including DEFO (distributed earliest finish-time offloading), PGOA (potential game based offloading algorithm), and GA-MEFT (GA-based Multi-User Earliest Finish Time). Meanwhile, we selected some random strategies to verify the schemes of HRRO-GA are the best. Lastly, we concluded that HRRO-GA is more suitable for the ultra-dense MEC system.