Research On Online Scheduling Algorithm For Multiple Workflows In Heterogeneous Systems

The paper relies on a project of National Natural Science Foundation of China," key technologies for collaborative design of the AUV", we have a deep research on the multiple workflows online scheduling problem on AUV collaborative design systems, the problem is modeled as a heterogeneous multiple workflows online scheduling problem, and an online scheduling algorithm based on look-ahead is prosented. Simulation results show that the algorithm can reduce the total time to complete multiple workflows, thereby increasing the efficiency of AUV collaborative design platform.Multiple workflows scheduling problem on AUV collaborative design platform is an online scheduling problem in heterogeneous system, it usually can’t get the optimal solution in polynomial time, it have been recognized as an NP problem. This paper introduces the background of AUV collaborative design platform and the classic task scheduling algorithms, like the MCT, MET, SA and KPB four classic online scheduling algorithm, and Min-min, Max-min and Sufferage three classical offline scheduling algorithms. This paper compares the advantages and disadvantages of each algorithm. Combined with the characteristics of AUV collaborative design platform, we improved the MCT algorithm.This paper defines the look-ahead value and presents an multiple workflows online scheduling algorithm. For the particularity of heterogeneous environments and multiple workflows, we use a small range strategies, making use of the workflow task waitting queue and follow-up tasks when schedule the current task, avoiding long waits problem of successor tasks due to the limited resources being assigned to the previous task,, making rational use of resources, reducing the total time scheduled for the execution of multiple workflows.Finally, we developed a simulation system, that uses multiple sets of data, and a variety of heterogeneous workflow environment to performe the algorithms with look-ahead value is land 2. Through the comparative analysis of the results, the proposed algorithm outperforms the online scheduling algorithm MCT, which can get a smaller makespan,and when the look-ahead value is 2, the performace is worse than that of value equals 1. Finally, we have successfully applying this algorithm to the AUV collaborative design platform.