General List Scheduling (GLS)

Input

An ordered list of $n$ jobs $\{J_1, \ldots, J_n\}$, a positive integer execution time $T(J_i)$ for each job, and a non-preemptive schedule $L$. The jobs are to be scheduled on two identical processors.

Problem

Is the final offset produced by the list scheduling algorithm nonzero?

Definitions

The final offset is the difference in the total execution time of the two processors.

Status

$\P$-complete (Helmbold and Mayr [1]).

Remarks

The reduction to show hardness is from NORCVP with gates in reverse topological order. The problem is in $\NC$ if the job times are small, that is $n^{O(1)}$. $\NC$ algorithms for scheduling problems with either intree or outtree precedence constraints are known (Helmbold and Mayr [2][1]). Also see HPS for additional scheduling results. See Mayr [3] for $\NC$ approximation algorithms. Sunder and He show that List Scheduling is $\P$-complete [4]. The differences between List Scheduling and GLS are that all jobs have unit time and the number of processors is an input to the problem. That is, it is not fixed at two as in GLS.

Sunder and He prove their result via a reduction from HPS. They also show that List Scheduling is in $\NC$ if the precedence constraints are an interval order. An interval order is a partial order $G = (V, E)$, where $V$ is a set of intervals on the real line and $([l_1, r_1], [l_2, r_2]) \in E$ if and only if $r_1 < l_2$. Their algorithm runs in $O((\log n)^2)$ time using $n^5$ processors on a PRIORITY CRCW-PRAM. Another version of the algorithm runs in $O((\log n)^3)$ time using $n^4$ processors on the same model [4].