Makespan-Minimization Workflow Scheduling for Complex Networks with Social Groups in Edge Computing

Abstract Edge computing enables users to offload certain computation loads in complex applications to a nearby network consisting of multiple mobile devices such that the mobile devices’ resources can be integrated to afford these complex applications. Due to the social relationships among the owners of mobile devices, networks in edge computing are always complex and consist of multiple sub-networks intersecting at several joint devices. In such complex networks, a joint device can communicate with all devices belonging to all sub-networks that intersect at this joint device while a general device can only communicate with the devices belonging to the same sub-network. This paper studies the makespan-minimization workflow scheduling problem for the aforementioned complex networks in edge computing environments, and formulates the problem as an integer program. Due to the limited energy capacity of each device, the dependence among workflow tasks, as well as network complexity, it is challenging to achieve feasible scheduling solutions for the concerned problem. Therefore, we propose a family of task allocation strategies to cope with different types of tasks in the workflow. These strategies are further integrated with a greedy strategy to construct an improved greedy search (IGS) algorithm which is capable of generating feasible solutions satisfying all constraints. In addition, we propose an improved composite heuristic (ICH) algorithm that employs IGS to initialize a feasible solution and uses a two-layer improvement scheme to further enhance the quality of the initial solution. Simulation results show that our proposed IGS achieves an 100% probability of generating feasible solutions, as compared to a 2.3% probability achieved by using the general round-robin scheduling algorithm. Furthermore, IGS and ICH outperform the counterpart scheduling algorithms in terms of makespan reduction.