Graham's List Scheduling Algorithm

computation scheduling

Definition

Graham's List Scheduling Algorithm

Graham’s list scheduling algorithm is a greedy algorithm for scheduling jobs on identical parallel machines with precedence constraints.
For an instance of

$$P\mid \mathrm{prec}\mid C_{\max },$$

the jobs are given in an ordered list. Whenever a machine becomes available, the algorithm scans the list and assigns the first ready job to it. A job is ready if all its predecessors have already completed.

Algorithm

List rule

Given $m$ identical machines and a fixed list $L$ of jobs:

while (some job is unscheduled) {
    wait until some machine is available;
 
    scan L from left to right;
    choose the first unscheduled job j whose predecessors are complete;
    assign j to the available machine;
}

The list order is arbitrary input to the algorithm. The approximation guarantee holds for every list.

Approximation

Approximation ratio

For $P\mid \mathrm{prec}\mid C_{\max }$ on $m$ identical machines, Graham’s list scheduling algorithm produces a schedule with makespan $C_{\max }$ satisfying

$$C_{\max }\le \left(2-\frac{1}{m}\right)\mathrm{OPT},$$

where $\mathrm{OPT}$ is the optimal makespan.

Idle-time argument $j_x$ be the job that finishes last in the schedule produced by the algorithm. Let $j_{x-1}$ be the predecessor of $j_x$ that finishes last. Continue backwards in the same way to obtain a chain

Let

$$j_1\prec j_2\prec \cdots \prec j_x.$$

This chain is a precedence path, so every feasible schedule must process it in this order. Therefore

$$\sum _{i=1}^x{p}_{j_i}\le \mathrm{OPT}.$$

Let $y$ be the total time during the algorithm’s schedule in which at least one machine is idle. A machine can be idle only while some job on the chain is being processed. Otherwise, the next chain job would have been ready and the algorithm would have assigned it earlier. Hence

$$y\le \sum _{i=1}^x{p}_{j_i}\le \mathrm{OPT}.$$

Let $P={\sum }_{j\in J}{p}_j$ be the total processing time. During the $C_{\max }-y$ time units in which all machines are busy, $m$ jobs are processed in parallel. During the remaining $y$ time units, at least one machine may be idle. Equivalently, the average load per machine gives

$$C_{\max }\le y+\frac{1}{m}(P-y)=y\left(1-\frac{1}{m}\right)+\frac{P}{m}.$$

Since every feasible schedule needs at least the average load,

$$\frac{P}{m}\le \mathrm{OPT}.$$

Together with $y\le \mathrm{OPT}$, this yields

$$C_{\max }\le \left(1-\frac{1}{m}\right)\mathrm{OPT}+\mathrm{OPT}=\left(2-\frac{1}{m}\right)\mathrm{OPT}.$$

Intuition

The proof separates the schedule into two kinds of time. Busy time is controlled by the total processing work $P$. Idle time is controlled by one precedence chain leading to the last job. Both quantities are lower bounds on the optimal makespan.

Complexity

With a priority queue of machine availability times and explicit predecessor counts, the algorithm can be implemented in polynomial time. The exact running time depends on how the ordered list and precedence graph are represented.