A trail-based approach for job scheduling in distributed systems with workflows

At the present, the amount of data need to be gathered, collected and processed in computing systems are increased significantly, their infrastructures may have to be improved or even redesigned. Distributed computing platforms is the one the most important approaches which can absorb large amount of data and also handle a higher computing workload efficiently. Job scheduling in such distributed systems is not a trivial issue. It can be even more complex when dealing with workflow-based composite jobs, i.e., each job has multiple tasks with dependencies between them. As the job scheduling problem has been proven an NP-hard, in this paper we propose a trail-based algorithm, Large Trail First (LTF), an effective heuristic approach for scheduling problem in the distributed systems when the workflows exist. The “trail” of each task is the number of remaining tasks in each workflow. The idea of the algorithm is that, for each workflow job, the task with larger size of the trail will be executed earliest. The experimental results are presented to show that the proposed approach is more effective and efficient than the other well-known approaches.