موعد زمانی اکتشافی مبتنی بر تقسیم برای بهینه سازی هزینه در زمان بندی جریان کار

Cost optimization for workflow applications described by Directed Acyclic Graph (DAG) with deadline constraints is a fundamental and intractable problem on Grids. In this paper, an effective and efficient heuristic called DET (Deadline Early Tree) is proposed. An early feasible schedule for a workflow application is defined as an Early Tree. According to the Early Tree, all tasks are grouped and the Critical Path is given. For critical activities, the optimal cost solution under the deadline constraint can be obtained by a dynamic programming strategy, and the whole deadline is segmented into time windows according to the slack time float. For non-critical activities, an iterative procedure is proposed to maximize time windows while maintaining the precedence constraints among activities. In terms of the time window allocations, a local optimization method is developed to minimize execution costs. The two local cost optimization methods can lead to a global near-optimal solution. Experimental results show that DET outperforms two other recent leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines.

Workflow applications are generally described as collections of tasks to be processed in a well-defined order to accomplish a specific goal [26]. Many complex applications in e-science and e-business can be modeled as workflows [12] and [29]. Because of the large amounts of computation and data involved, these workflows require the power of the Grid to run efficiently. Grid computing [13] has emerged as the next generation computing platform for solving large-scale problems in science, engineering, and commerce. It facilitates the sharing and aggregation of heterogeneous and distributed resources, such as computing resources, data sources, instruments, and application services. Grid workflow can be defined as the composition of different Grid application services that run on heterogeneous and distributed resources in a well-defined order to accomplish a specific goal [28]. Yu and Buyya [29] proposed a taxonomy that characterizes and classifies various approaches for building and executing Grid workflows. A popular representation of workflow applications is Directed Acyclic Graph (DAG), in which nodes represent individual tasks and directed arcs or edges represent inter-task data or control dependencies. DAG-based workflow applications usually have different structures, such as pipeline, parallel and hybrid structures. A pipeline application executes a number of tasks in a single sequential order. A parallel application requires multiple pipelines to be executed in parallel. Fig. 1a shows a neuroscience workflow [33] where there are four pipelines (1–2, 3–4, 5–6 and 7–8) before task 9. A hybrid structure application is a combination of both parallel and sequential applications. For example, Fig. 1b shows a protein annotation workflow [25] developed by the London e-Science Centre.Workflow scheduling is one of the key problems on Grids. It is meant to deal with the allocation of tasks to suitable resources so that the objective function can be minimized or maximized while maintaining task-precedence constraints. A number of Grid workflow management systems with scheduling algorithms have been developed by several projects, such as Condor DAGMan [16], GrADS [8] and Pegasus [5] and [12]. They facilitate the execution of workflow applications and minimize their execution time on Grids. However, Grid resources are normally heterogeneous in terms of their architectures, powers, configurations, and availabilities. They are owned and managed by different organizations with different access policies and cost models that vary with time and the users. The resource owners and end-users have different goals, objectives, and demand patterns. Due to these unique characteristics, different and effective performance parameters (i.e., quality of service), such as time, cost, and reliability [24], are applied to reflect the actual characteristics of Grids. QoS (quality of service) is a determinant factor used to ensure customer satisfaction that can be expressed as the utility functions over QoS attributes or the QoS constraints. Therefore, QoS-based workflow scheduling becomes a significant and challenging problem. This paper aims to study the QoS optimization strategy for workflow scheduling on Grids. The remainder of the paper is structured as follows. Section 2 introduces the related work. Section 3 formulates the workflow scheduling problem. An early feasible schedule and its related definitions are introduced in Section 4. Section 5 reviews the leveling algorithms and describes the proposed algorithm, DET. In Section 6, experimental results are given, followed by conclusions in Section 7.

This paper tackles the cost optimization for workflow scheduling represented by DAG with a deadline constraint. It is formulated as the discrete time-cost tradeoff problem in project scheduling. Since the optimization problem is generally NP-hard and the Grid environment is highly dynamic, an effective and efficient heuristic should be developed to solve the larger and hard instances. The deadline division strategy is applied to solve the workflow scheduling described by DAG. The heuristic DET is proposed. An early feasible schedule, defined as an Early Tree (ET), is constructed, in which the Critical Path is defined and workflow tasks are grouped. For critical activities, the optimal cost solution under the given deadline constraint can be obtained by the dynamic programming method. The whole deadline is also segmented into time windows in terms of the slack time float. For non-critical activities, an iterative procedure is proposed to maximize the time windows while keeping the precedence constraints among activities. According to the time window allocation, a local cost optimization method is applied to non-critical activities. Extensive computational testing indicates that the proposed approach can achieve better results than the other two leveling algorithms. Moreover, the deadline division strategy adopted by DET can be applied to all feasible deadlines. In terms of the computation time, DET requires a little more computation effort than the other leveling algorithms, but its average run time is less than 12 s when the instance size increases to 200, which is acceptable in practice. In addition, resource consumption is one of the important evaluation criteria for workflow scheduling. Only two criteria (i.e., cost and the completion time) are considered in this paper. The objective of our future work involves incorporating resource consumption criterion into the objective function.