A GPU Based Approach for Solving the Workflow Scheduling Problem

2. Scheduling Problem Modeling

Task scheduling problem is one of the most important steps when using cloud computing environment capabilities to execute a workflow. A workflow can be represented by a Directed Acyclic Graph (DAG), G = (V, E), as shown in Figure 1, where V is the set v nodes, v_i in V represents a workflow task, which contains a known number of instructions that must be executed on the same processor. E represents the set of communication edges between tasks; each edge e(i, j) ∈ E represents the task-dependency constraint which means that task n_i should be executed before task n_j can be started. A computation cost matrix W matrix complements the DAG, this matrix is a v × p, where v is the number of tasks and p is the number of processors. w_ij gives the estimated time to execute task v_i on machine p_j. Each edge e(i, j) ∈ E is associated with a nonnegative weight c_ij representing the communication cost between the tasks v_i and v_j (Topcuoglu et al., 2002).

In a given task graph, a task without any parent is called an entry task and a task without any child is called an exit task. A task graph may have more than one entry task and more than one exit task.