Average Completion Time (Interval Scheduling)

computation scheduling

Definition

Average Completion Time

The average completion time of a schedule is the mean of the job completion times:

$$\frac{1}{|J|}\sum _{j\in J}{C}_j.$$

Objective

For a fixed job set $J$, minimising average completion time is equivalent to minimising total completion time, because $|J|$ is constant.

Thus the objective is often written as

$$\sum _{j\in J}{C}_j$$

instead of $\frac{1}{|J|}{\sum }_j{C}_j$.

No release times

For the single-machine problem

$$1\mid \varnothing \mid \sum _j{C}_j,$$

the shortest processing time first rule is optimal. It orders the jobs by nondecreasing processing time $p_j$.

SPT optimality

Shortest processing time first minimises ${\sum }_j{C}_j$ for $1\mid \varnothing \mid {\sum }_j{C}_j$.

Exchange argument $S$ does not follow shortest processing time first. Then there are two jobs $i$ and $k$ such that $i$ starts before $k$, but

Suppose, toward a contradiction, that an optimal schedule

$$p_k<p_i.$$

Construct $S^{\prime }$ by moving $k$ into the position of $i$, moving all jobs between $i$ and $k$ forward, and placing $i$ where $k$ was. No idle time is introduced.

Every job other than $i$ and $k$ completes no later in $S^{\prime }$ than in $S$. Job $i$ in $S^{\prime }$ completes when $k$ completed in $S$. Job $k$ in $S^{\prime }$ completes earlier than $i$ completed in $S$, because $p_k<p_i$.

Therefore

$$\sum _j{C}_j(S^{\prime })<\sum _j{C}_j(S),$$

contradicting the optimality of $S$. Hence some optimal schedule follows shortest processing time first. $\square$

Release times

With release times and no preemption, the problem

$$1\mid r_j\mid \sum _j{C}_j$$

is strongly NP-hard.

If preemption is allowed, the problem becomes easier:

$$1\mid r_j,\mathrm{pmtn}\mid \sum _j{C}_j.$$

The optimal rule is shortest remaining processing time first. At every time, among released unfinished jobs, process the job with smallest remaining processing time.

SRPT optimality

Shortest remaining processing time first minimises ${\sum }_j{C}_j$ for $1\mid r_j,\mathrm{pmtn}\mid {\sum }_j{C}_j$.

Local exchange $S$ does not follow shortest remaining processing time first. Then at some time $t$, job $i$ is processed even though another released job $k$ has smaller remaining processing time:

Suppose, toward a contradiction, that an optimal schedule

$$p_k^{\prime }<p_i^{\prime }.$$

After time $t$, the schedule spends $p_i^{\prime }+p_k^{\prime }$ units of processing on jobs $i$ and $k$. Construct $S^{\prime }$ by spending the first $p_k^{\prime }$ of those units on $k$, and the remaining units on $i$.

All jobs other than $i$ and $k$ have the same completion time in $S^{\prime }$ as in $S$. Job $i$ completes in $S^{\prime }$ at time $\max \{C_i,C_k\}$ from $S$, while job $k$ completes before $\min \{C_i,C_k\}$ from $S$ because $p_k^{\prime }<p_i^{\prime }$.

Hence the total completion time decreases, contradicting optimality. $\square$

Approximation without preemption

The preemptive optimum gives a useful lower bound for the non-preemptive problem

$$1\mid r_j\mid \sum _j{C}_j.$$

Let

$$C_{1,P}\le C_{2,P}\le \cdots \le C_{n,P}$$

be the completion times in an optimal preemptive schedule. Consider the non-preemptive algorithm that schedules jobs greedily in this order. The next job starts once the previous job has finished and the job has been released.

2-approximation

The greedy order induced by the optimal preemptive schedule is a $2$-approximation for $1\mid r_j\mid {\sum }_j{C}_j$.

Completion-time bound $j$-th job in the preemptive completion order,

For the

$$C_{j,P}\ge \underset{k=1,\dots ,j}{\max }{r}_k\text{and}{C}_{j,P}\ge \sum _{k=1}^j{p}_k.$$

Let $C_{j,N}$ be the completion time of the same job in the non-preemptive greedy schedule. Before it completes, the schedule waits at most until the latest release time among the first $j$ jobs and then processes those $j$ jobs. Thus

$$C_{j,N}\le \underset{k=1,\dots ,j}{\max }{r}_k+\sum _{k=1}^j{p}_k\le 2C_{j,P}.$$

Summing over all jobs gives

$$\sum _{j=1}^n{C}_{j,N}\le 2\sum _{j=1}^n{C}_{j,P}\le 2\mathrm{OPT},$$

because the preemptive optimum is a lower bound on the non-preemptive optimum. $\square$