New approach for task scheduling in distributed systems

The problem of scheduling tasks on parcel systems has been shown to be computationally intractable in its general form as well as many restricted cases. When the communication cost among system processors is not considered, optimal algorithm are known for only interval-ordered task graphs, tree-structural task graphs, and two-processor systems. When communication cost is considered, optimal algorithms exist in two cases: interval-ordered task graphs and tree-structured task graphs on two processors. As these special case constitute only a small subset of real-world situations, researchers have attempted to solve the general version of the scheduling problem using heuristic techniques. In this paper, the authors introduce a two-step algorithm for scheduling general task graphs in parallel systems. In the first step the algorithm augments the input task graph, by adding as few relations (precedence edges) as possible, in order to obtain an interval order. In the second step the algorithm uses optimal scheduling algorithms to find an optimal schedule of the augmented graph. Experimental studies are conducted to compare the performance of the propose technique with several known heuristics. The results obtained show that the augmentation-based algorithm out-performs other heuristics on most of the randomly generated task graphs. The authors also show that the algorithm finds optimal schedules for a class that properly includes the class of interval orders.