Chinese Journal of Computers   Full Text
Title	Bottom Level Based Heuristic for Workflow Scheduling in Grids
Authors	YUAN Ying-Chun1),3) LI Xiao-Ping1),2) WANG Qian1),2) ZHANG Yi1),2)
Address	1)(School of Computer Science and Engineering, Southeast University, Nanjing 210096) 2)(Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education，Nanjing 210096) 3)(Faculty of Information Science and Technology, Agriculture University of Hebei, Baoding, Hebei071001)
Year	2008
Issue	No.2(282—290)
Abstract &   Background	Abstract Efficient scheduling of workflow applications represented by DAG (Directed Acyclic Graph) with the objective of time-cost optimization is fundamental and intractable in computational Grid. By analyzing parallel and synchronization properties of DAG, all tasks are divided into BL (Bottom Level) groups using a backward method. The workflow deadline can be transformed into the time intervals of all tasks based on BL groups, a bottom leveling based algorithm called DBL (Deadline Bottom Level) is proposed. In DBL, the starting time of a task in each group is determined by the maximum finish time among those of its predecessors rather than the finish time of its parent group, which is adopted by DTL (Deadline Top Level). The total time float is allocated equally to each group, which manage to enlarge the cost optimization intervals of all tasks. By comparing DBL with DTL and MCP (Minimum Critical Path), which is a cost optimization method based on the minimum critical path, experimental results show that DBL can save 24.74% average cost of MCP and DTL can only do 15.62%. In other words, DBL outperforms both DTL and MCP. As well, parameters affecting algorithms (such as leveling parameters, deadlines) are analyzed by experiments. keywords computational grid; workflow; directed acrylic graph; heuristics; bottom level background The aim of this work is to implement the efficient scheduling of workflow applications in computational Grids. This work is part of National Natural Science Foundation of China under Grant "the research and implement for AMS data computational environment". Grid computing has emerged as a promising distributed computing paradigm for solving large-scale computational and data intensive problems in science, engineering and commerce. This project intends to implement efficiently the storage, management, access and operation of AMS massive data. In order to meeting users’ requirements, the resource management and application scheduling are the key problems in Girds. For the scheduling of workflow applications represented by Directed Acyclic Graph(DAG), which widely exist in different scientific domains such as bioinformatics and astronomy, Buyya et al. have proposed some constructive heuristics (e.g. DTL) for solving cost optimization with deadline constraints. The work still focuses on the cost optimization problem for workflows with deadline constraints. A heuristic called Deadline Bottom Level (DBL) is proposed. By analyzing the properties of DAG, a new concept called Bottom Depth (BD) is defined. Those tasks with same bottom depth are divided into a level, which comprehensives the parallel and synchronization properties of DAG. Thus, the overall deadline can be transformed into the time intervals of all tasks. All tasks can select the appropriate service resources to minimize the total cost with their time intervals. Experimental results show that DBL can save 9.12% average cost of DTL. Moreover, the heuristic DBL can also applied to general workflow applications considering choice and iteration structure if pre-processing strategies is executed. In addition, the deadline division strategy based on level is very suitable for dynamic gird environment. The scheduler may re-adjust unexecuted task level’s sub-deadlines level-by-level and re-compute their optimal schedules. Thus, the minimum number of tasks is only considered to reallocation other candidate services. This work is also supported by the National Natural Science Foundation of China under grants No.60672092 and No.60504029.