Workflow-Based Composite Job Scheduling for Decentralized Distributed Systems
Nasi Tantitharanukul, Juggapong Natwichai, Pruet Boonma · 2013
The development of distributed systems has been accelerated in this recent years through the development of P2P, grid, and cloud computing. Nevertheless, job scheduling is still a major challenge for distributed system design and implementation. Such issue can be more complex when dealing with workflow-based composite jobs, i.e. each job has multiple tasks with dependencies between them. In this paper we prove that, when task dependency in such kind of jobs is pre-defined with workflow templates, finding minimal execution time for multiple jobs is an NP-complete problem. So, we propose a heuristic algorithm for this problem. The experimental results show that this algorithm can find near optimal solutions to the problem with a polynomial computation time.