TEMPORAL DECOMPOSITION AND SCHEDULING OF GRID WORKFLOW
The work is funded by SERC of A*Star Singapore through the national grid office (NGO) under the research grant 0520150024 for two years.
Workflow scheduling is a very important system function that Grid systems have to support. But the scheduling of workflow tasks is an NP complete problem. In this paper, we propose a new scheduling method– “temporal decomposition” – which first divides a whole grid workflow into some sub-workflows and then schedules them using a new efficient algorithm. By dividing a large problem (workflow) into smaller problems (sub-workflows), the “temporal decomposition” can achieve much lower computation complexity. Numerical results show that our proposed scheme is more efficient in comparison with a well known existing grid workflow scheduling method.
