Considering the utilization of idle time slots for DAG scheduling in optical grid applications

Cost-effective optical network solves the bottleneck of grid issues, thus promoting the study of optical grid. Task scheduling is the key optical grid research. List scheduling is one of the most common heuristic algorithms and the temporal and spatial mapping of a program to a parallel system. In this paper, we use the directed acyclic graph (DAG) to represent the tasks and the constraints among them. First we make some changes on the edge scheduling. Then by exploiting of unused time slots between edges or nodes which have been scheduled, the extended scheduling algorithm is proposed, which allows scheduling edge or node on the available time slots. Thus the edges and nodes can be scheduled within the first time. The extended algorithm takes the communication delay under consideration and can be used in heterogeneous environments. By way of evaluating the performance of the extended algorithm, it is conducive to DAG with higher degree of parallelism and is proved to be feasible for data-intensive applications.