For any given problem, there exists a set (possibly empty, possibly infinite)
of solutions, which we will call `A`,
and a set of optimal solutions `A* ⊆ A`.
In general our aim will be to find any one of the optimal
solutions to the problem.

For some easily determinable property, say `X`,
we will represent the set of all solutions having that property by
`<X>`.
If `<N> ⊇ A*` then property `N` is known as a
necessary condition
for optimality as all optimal solutions satisfy it.
If `<S> ⊆ A*` then property `S` is known as a
sufficient condition
for optimality as any solution with that property is optimal.
If `<D> ∩ A*` is not null,
then property `D` is known as a
dominant condition
as at least one solution in the set determined by `D` is optimal.

____________________________________________ | | | ______________________________ | | | | | | | _____________________ | | | | | | | | | | | ____________ | | | | | | | | | | | | | | | _______________________ | | | | | | | | A <N> A* <S> <D> | | | | | | | | | | | | | |_______________________| | | | | | | | | | | | | |____________| | | | | | | | | | | | |_____________________| | | | | | | | |______________________________| | | | |____________________________________________|

Necessary or dominant conditions are often easy to determine, but are of course not always of immediate use in finding an optimal solution. Sufficient conditions readily give optimal solutions, but are often much more difficult to find.

If some property is both necessary and sufficient for optimality, then all solutions satisfying the property are optimal but no other solutions are. Such properties are valuable (the holy grails of scheduling theory), especially if they have a simple characterization.

In the following section we will determine a dominance condition and a necessary condition for a specific scheduling problem and then prove that the necessary condition is also sufficient.

Minimizing
mean weighted flow time
(`= ∑F _{j}w_{j} / ∑w_{j}`)
on one machine with zero ready dates.

If the ready date of the machine and all jobs is 0,
then `C _{j} = F_{j}`
for all jobs

If preempt-repeat scheduling is used, all interrupted processing can be removed from a schedule without increasing any of the completion times.

Suppose we have a schedule `S _{0}`
in which some job

S_{0}: - - - - - j^{1}x x x x x x j^{2}- - - - - - - -S_{1}: - - - - - x x x x x x j^{1}j^{2}- - - - - - - -

Now any jobs that are completed in interval `X` are completed earlier
in `S _{1}` than in

Let `S` be any optimal permutation schedule.
Construct `S′` by interchanging any pair of adjacent jobs `j` and `j+1` in `S`.

S = (1,2,3,...,j,j+1,...,n)S′ = (1,2,3,...,j+1,j,...,n)

As `S` is optimal, `C _{w}(S) − C_{w}(S′) ≤ 0`.

If we let `T` be the completion date of job `j−1`, then

0 ≥ C_{w}(S) − C_{w}(S′) = ( w_{j}(T+t_{j}) + w_{j+1}(T+t_{j}+t_{j+1}) )−( w_{j+1}(T+t_{j+1}) + w_{j}(T+t_{j+1}+t_{j}) )= w_{j+1}t_{j}− w_{j}t_{j+1}

And so `t _{j} / w_{j} ≤ t_{j+1} / w_{j+1}`, as all weights are positive.

This condition is known as WSPT ( weighted shortest processing time ), and as it is true for any optimal permutation schedule it is a necessary condition for minimizing mean weighted completion date.

Note that if for some jobs `i` and `j`,
`t _{i} / w_{i} = t_{j} / w_{j}`, but

We will now prove that WSPT is also a sufficient condition for the given problem,
and hence that for the case `t _{i} / w_{i} = t_{j} / w_{j}`
it does not matter in which order the two jobs are scheduled.

Let `S` be any WSPT schedule.
Let `S _{0}` be any optimal permutation schedule.
If all adjacent pairs of jobs in

S : - - - - - j - - - - - - - - - i - - - - - - -S_{0}: - - - - - - - - - - i j - - - - - - - - - - -S_{1}: - - - - - - - - - - j i - - - - - - - - - - -

Construct `S _{1}` from

C_{w}(S_{0}) − C_{w}(S_{1}) = ( w_{i}(T+t_{i}) + w_{j}(T+t_{i}+t_{j}) )−( w_{j}(T+t_{j}) + w_{i}(T+t_{j}+ t_{i}) )= −w_{i}t_{j}+ w_{j}t_{i}= w_{i}w_{j}( t_{i}/w_{i}− t_{j}/w_{j})≥ 0becausetas_{i}/w_{i}≥t_{j}/w_{j}j→iinS(WSPT order)

Thus `C _{w} (S_{0} ) ≥ C_{w} (S_{1} )`.
Since

If all `w _{j}` are equal,
then the weights may be ignored and we have that all
schedules in which

A function is regular if its value worsens only when the value of at least one of its arguments increases. In the preceding section we saw that permutation schedules were a dominant set with respect to minimizing the mean completion date on a single machine, as we were able to remove all preemptions from any given schedule without increasing any of the completion dates. It thus follows that for any regular function of completion date on a single machine, permutation schedules are a dominant set.