Segment Level Based Heuristic for Workflow Cost-time Optimization in Grids

Workflow scheduling with the objective of time-cost optimization is a fundamental problem in grids and generally the problem is NP-hard.In this paper,a novel heuristics called SL (Segment Level) for workflows represented by DAG (Directed Acyclic Graph) is proposed.Considering the parallel and synchronization properties,the workflow application is divided into segments,and the workflow deadline is transformed into the time intervals and appointed to different segments.The floating time is prorated to each segment to enlarge cost-time duration,and a dynamic programming method is implemented to optimize cost for each segment.By comparing SL with MCP (Minimum Critical Path),DTL (Deadline Top Level),DBL (Deadline Bottom Level),the heuristics' efficiency is verified by experimental results.