Definition
Average Completion Time
The average completion time of a schedule is the mean of the job completion times:
Objective
For a fixed job set
Thus the objective is often written as
instead of
No release times
For the single-machine problem
the shortest processing time first rule is optimal. It orders the jobs by nondecreasing processing time
SPT optimality
Shortest processing time first minimises
for . Exchange argument
Suppose, toward a contradiction, that an optimal schedule
does not follow shortest processing time first. Then there are two jobs and such that starts before , but Construct
by moving into the position of , moving all jobs between and forward, and placing where was. No idle time is introduced. Every job other than
and completes no later in than in . Job in completes when completed in . Job in completes earlier than completed in , because . Therefore
contradicting the optimality of
. Hence some optimal schedule follows shortest processing time first.
Release times
With release times and no preemption, the problem
is strongly NP-hard.
If preemption is allowed, the problem becomes easier:
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
for . Local exchange
Suppose, toward a contradiction, that an optimal schedule
does not follow shortest remaining processing time first. Then at some time , job is processed even though another released job has smaller remaining processing time: After time
, the schedule spends units of processing on jobs and . Construct by spending the first of those units on , and the remaining units on . All jobs other than
and have the same completion time in as in . Job completes in at time from , while job completes before from because . Hence the total completion time decreases, contradicting optimality.
Approximation without preemption
The preemptive optimum gives a useful lower bound for the non-preemptive problem
Let
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
-approximation for . Completion-time bound
For the
-th job in the preemptive completion order, Let
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 jobs and then processes those jobs. Thus Summing over all jobs gives
because the preemptive optimum is a lower bound on the non-preemptive optimum.