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

≤ p i ≤ p i | w i C i ,job J u dominates job J v

Theorem 1. [10] For the problem 1 |p i

if and only if inequality (3) holds:

w u
p u ≥

w v
p v

. (3)

Due to Theorem 1 proven in [10], we can obtain a compact presentation of a minimal
dominant set S ( T ) in the form of a digraph ( J , A ) with the vertex set

J

and the arc

set and

construct a dominance digraph ( J , A ) of the precedence-dominance relation on the set
of jobs

A . To this end, we can check inequality (3) for each pair of jobs from the set J

if and only if inequality (3)
holds. The construction of the digraph ( J , A ) takes O ( n 2 ) time.

J as follows. The arc ( J u ,J v ) belongs to the set A

3.1 Illustrative Example

For the sake of simplicity of the calculation, we consider a special case 1 |p i ≤ p i ≤

p i | C i of the problem 1 |p i ≤ p i ≤ p i | w i C i when each job J i ∈J has a weight

w i equal to one. From condition (2), it follows that the deterministic problem 1 || C i
can be solved to optimality by the shortest processing time rule: process the jobs in
non-decreasing order of their processing times p k i , J k i ∈J

.

A set of scenarios T for Example 1 of the uncertain problem 1 |p i ≤ p i ≤ p i | C i
is defined in columns1and2inTable1.

Ta b l e 1 . Data for calculating SB ( π 1 ,T ) for Example 1

12345678
ip i p i

w i
p i

w i
p i

d i d i

w i
d +
i

w i
d −
i

12 3 3 0 . 5 1 0 . 5 21

21 9 9

1
6

1
3

1 36

38 8 8

1
8

1
6

1
9

96

1
6 0 . 1

1
9

46 10 0 . 1 910

511 12 12

1
11 0 . 1

1
11

11 10

610 19 19 0 . 1

1
15

1
12

12 15

717 19 19

1
17

1
15

1
19

19 15

815 20 20

1
15

1
20

1
19

19 20

In [12], formula (9) has been proven. To use it for calculating the stability box SB ( π k ,

T ) , one has to define for each job J k i ∈J the maximal range [ l k i ,u k i ] of possible vari-

ations of the processing time p k i preserving the optimality of permutation π k (see Def-

inition 1). Due to the additivity of the objective function γ = J i ∈J w i C i ( π k ,p ) , the
lower bound d k i on the maximal range of possible variations of the weight-to-process

w k i
p k i

ratio preserving the optimality of the permutation π k =( J k 1 ,J k 2 ,...,J k n ) ∈ S

is calculated as follows: