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 (= ∑Fjwj / ∑wj) on one machine with zero ready dates.
If the ready date of the machine and all jobs is 0, then Cj = Fj for all jobs j. The problem is thus equivalent to minimizing total weighted completion date Cw = ∑wj Cj over all schedules, where wj is a given weight associated with job j, and Cj is the date at which job j is completed.
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 S0 in which some job j is preempted at time t1 and resumed at time t2. We can construct a new schedule S1 in which all work done between t1 and t2, say set X, is interchanged with the first part of job j.
S0 : - - - - - j1 x x x x x x j2 - - - - - - - - S1 : - - - - - x x x x x x j1 j2 - - - - - - - -
Now any jobs that are completed in interval X are completed earlier in S1 than in S0, and all other jobs are completed at the same time in both schedules. Thus schedule S1 has each job completed at the same time or earlier than does schedule S0, and so Cw (S1 ) ≤ Cw (S0 ). Similarly we could remove all preemptions from any optimal schedule without increasing the mean weighted completion date. Hence schedules without preemption form a dominant set, as we know that at least one of them is optimal, and so we need only consider permutation schedules in our search for an optimal schedule.
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, Cw(S) − Cw(S′) ≤ 0.
If we let T be the completion date of job j−1, then
0 ≥ Cw(S) − Cw(S′) = ( wj(T+tj) + wj+1(T+tj+tj+1) )
−( wj+1(T+tj+1) + wj(T+tj+1+tj) )
= wj+1tj − wjtj+1
And so tj / wj ≤ tj+1 / wj+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, ti / wi = tj / wj, but ti > tj, it is by no means obvious which should be scheduled earlier.
We will now prove that WSPT is also a sufficient condition for the given problem, and hence that for the case ti / wi = tj / wj it does not matter in which order the two jobs are scheduled.
Let S be any WSPT schedule. Let S0 be any optimal permutation schedule. If all adjacent pairs of jobs in S0 are in the same order as in S, then S=S0 and so S is optimal. Otherwise there exists a pair of jobs, i and j, such that i immediately precedes j in S0, but j precedes i (perhaps not immediately) in S.
S : - - - - - j - - - - - - - - - i - - - - - - - S0 : - - - - - - - - - - i j - - - - - - - - - - - S1 : - - - - - - - - - - j i - - - - - - - - - - -
Construct S1 from S0 by interchanging jobs i and j and leaving all other jobs in the same positions. Let T be the time at which job i starts processing in S0.
Cw(S0) − Cw(S1) = ( wi(T+ti) + wj(T+ti+tj) )
−( wj(T+tj) + wi(T+tj+ ti) )
= −witj + wjti
= wiwj ( ti/wi − tj/wj )
≥ 0 because ti/wi≥tj/wj as j→i in S (WSPT order)
Thus Cw (S0 ) ≥ Cw (S1 ). Since S0 is optimal Cw (S0 ) ≤ Cw (X) for all schedules X, and so Cw(S1) = Cw(S0) and hence both are optimal. Now interchanging jobs i and j reduced by one the number of pairs of jobs in S0 which were in a different order than in S. But as there can be at most a finite number of such pairs, we can construct a finite sequence of optimal schedules, {S0 , S1 , S2 , ..., Sz} such that Sz =S. As S is any WSPT schedule, we have just proven that all WSPT schedules are optimal and so WSPT is sufficient to minimize mean weighted completion date.
If all wj are equal, then the weights may be ignored and we have that all schedules in which tj ≤ tj+1 minimize the mean completion date. Such schedules are known as SPT ( shortest processing time ) schedules. If the jobs are arranged in the opposite order, they form a LPT ( longest processing time ) schedule.
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.