Scheduling UET-UCT Series-Parallel Graphs on Two Processors

The scheduling of task graphs on two identical processors is considered. It is assumed that tasks have unit-execution-time, and arcs are associated with unit-communication-time delays. The problem is to assign the tasks to the two processors and schedule their execution in order to minimize the makespan. A quadratic algorithm is proposed to compute an optimal schedule for a class of series-parallel graphs, called SP1 graphs, which includes in particular in-forests and out-forests. Keywords: Scheduling, Makespan, Precedence Constraint, Series-Parallel Graphs, Complexity, Optimal Algorithm. Fellow of the European Union Program Human Capital and Mobility 1 Introduction A notoriously difficult problem in the scheduling of parallel computation has been the minimization of makespan (i.e. schedule length) of a set of partially ordered tasks with unit-execution-time (UET) and unit-communication-time (UCT) delays on m (identical) processors [2]. A general description of the problem is the ..