A look-ahead algorithm for online multiple workflow scheduling problem in heterogeneous systems

摘要

A look-ahead algorithm is proposed to solve the online multiple workflow scheduling problem with two constraints in heterogeneous system. In this problem, workflows come to the system online when they are released, and each workflow is composed of multiple tasks which can be executed on heterogeneous processors, according to their types. Considered two constrains including the non-preemptive processor and the task order in a workflow, the proposed algorithm utilizes the information contained in the list of the submitted workflows and optimizes the scheduling of current task according to subsequent tasks. It can keep the subsequent tasks from waiting for a long time due to the occupation of the limited resource by the current task. The simulation results show that the proposed look-ahead algorithm outperforms four classical online scheduling algorithms, and the algorithm can get better performance when the look-ahead value L=1 than L2.