A Heuristic Scheduling Algorithm for Distributed Systems with Workflow Constraints
Nasi Tantitharanukul, Juggapong Natwichai, Pruet Boonma
Journal of Intelligent Computing, Vol. 5, No. 4, 2014.
DOI: 
Link: http://www.dline.info/jic/fulltext/v5n4/2.pdf
Abstract:
Distributed systems become one of the most important computing platform because they can efficiently handle large amount of data with a high computing workload. However, the job scheduling in the 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 to be an NP-hard, we propose a trail-based algorithm; Large Trail First (LTF), which is an effective heuristic approach for scheduling problem in the distributed systems
when workflows exist. In this paper, â€œtrailâ€ of each task is the number of remaining tasks in each workflow. Thus, the idea of
the algorithm is that, for each workflow job, the task with the largest size of the trail will be executed earliest. The experimental
results show that the proposed approach is more effective and efficient than the other three approaches including a well known 2-approximation algorithm.