Workflow-Based Composite Job Scheduling for Decentralized Distributed Systems

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.