The Stability Box for Minimizing TotalWeighted Flow Time under Uncertain Data - Simulation and Modeling Methodologies, Technologies and Application - page 42

Remark 1. Due to Property 3, while looking for a permutation π t ∈ S max ,weshall
treat a pair of jobs satisfying (12) as one job (either job J i or J v ).

Case (III) is defined by the strict inequalities
w v
p v

{J i ,J v }

> w i
p i

w v
p v

< w i
p i

, . (13)

For a job J i ∈J satisfying case (III), let J ( i ) denote the set of all jobs J v ∈J ,for

which the strict inequalities (13) hold.
Property 4. (i) For a fixed permutation π k ∈ S ,job J i ∈J may have at most one

maximal segment [ l i ,u i ] of possible variations of the processing time p i ∈ [ p i ,p i ]
preserving the optimality of permutation π k .
(ii) For the whole set of permutations S , only in case (III), a job J i ∈J

may have

more than one (namely: |J ( i ) | +1 > 1 ) maximal segments [ l i ,u i ] of possible variations

of the time p i ∈ [ p i ,p i ] preserving the optimality of this or that particular permutation
from the set S .

Proof. Part (i) of Property 4 follows from the fact that a non-empty maximal segment
[ l i ,u i ] J − ( i ) of jobs located before job (if any) is uniquely determined by the subset

J + ( i ) of jobs located after job J i . The subsets

J i in permutation π k and the subset

J − ( i ) and J + ( i ) are uniquely determined for a fixed permutation π k ∈ S and a fixed

job J i ∈J .

Part (ii) of Property 4 follows from the following observations. If the open inter-

val w i
p i

does not intersect with the closed interval w v
p v

for each job J v ∈

, w i
p i

, w v
p v

∈ S max with a maximal segment

J , then there exists a permutation π t [ l i ,u i ]=

w i /p i ,w i /p i preserving the optimality of permutation π t .
Each job J v ∈J with a non-empty intersection w i

p i

w v
p v

, w i
p i

, w v
p v

sat-
isfying inequalities (11) (case (I)) or equalities (12) (case (II)) may shorten the above
maximal segment [ l i ,u i ] and cannot generate a new possible maximal segment. In case
(III), a job J v satisfying inequalities (13) may generate a new possible maximal seg-
ment [ l i ,u i ] just for job J i satisfying the same strict inequalities (13) as job J v does.
So, the cardinality

= ∅

|L ( i ) | of the whole set L ( i ) of such segments [ l i ,u i ] is not greater

than |J ( i ) | +1 .

Let L denote the set of all maximal segments [ l i ,u i ] of possible variations of the

processing times p i for all jobs J i ∈J preserving the optimality of a permutation

π t ∈ S max . Using Property 4 and induction on the cardinality |J ( i ) | , we proved

Property 5. |L| ≤ n.

3.3 A Job Permutation with the Largest Volume of a Stability Box
The above properties allows us to derive an O ( n log n ) algorithm for calculating a per-
mutation π t ∈ S max with the largest dimension

|N t | and the largest volume of a stabil-

ity box SB ( π t ,T ) .