A Full-Path Priority Based Workflow Scheduling Approach

Workflow scheduling is a well-known NP-complete problem with broad applications and increasing importance. In this paper, we present a heuristic-based algorithm, called FPPTS, which uses a new ranking method in the task ranking phase, prioritizing tasks according to their full paths from the entry task to the exit task. Experimental results show that FPPTS excels at workflows of high CCR running in heterogeneous computing environments, significantly outperforming HEFT and IPPTS. For example, in experiments with 30-task and 10-CCR workflows running on 10 processors, FPPTS shows an average performance improvement of 15.93% compared to IPPTS. The excellent performance of FPPTS indicates a promising direction for future workflow scheduling research.