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

2 Problem Setting

J = {J 1 ,J 2 , ..., J n }

, n ≥ 2 , have to be processed on a single machine,

The jobs

a positive weight w i . The processing time p i of a

job J i can take any real value from a given segment [ p i ,p i ] , where 0 ≤ p i

being given for any job J i ∈J

≤ p i .

The exact value p i ∈ [ p i ,p i ]

may remain unknown until the completion of the job

.Let T = {p ∈ R n

+ | p i

≤ p i ≤ p i ,i∈{ 1 , 2 ,...,n}}

J i ∈J denote the set

of vectors p =( p 1 ,p 2 ,...,p n ) (scenarios) of the possible job processing times. S =
{π 1 ,π 2 ,...,π n ! } denotes the set of permutations π k =( J k 1 ,J k 2 ,...,J k n ) of the jobs

. Problem 1 |p i ≤ p i ≤ p i | w i C i is to find an optimal permutation π t ∈ S : J

w i C i ( π t ,p )= γ p =min
π k ∈S

w i C i ( π k ,p ) . (1)

J i ∈J J i ∈J

Hereafter, C i ( π k ,p )= C i is the completion time of job J i ∈J

in a semi-active

schedule [6,13] defined by the permutation π k .
Since a factual scenario p ∈ T is unknown before scheduling, the completion time
C i of a job J i ∈J

can be determined after the schedule execution. Therefore, one
cannot calculate the value γ p of the objective function
γ =
J i ∈J

w i C i ( π k ,p )

for a permutation π k ∈ S before the schedule realization.
However, one must somehow define a schedule before to realize it. So, the problem
1 |p i ≤ p i ≤ p i | w i C i of finding an optimal permutation π t ∈ S defined in (1)
is not correct. In general, one can find only a heuristic solution (a job permutation) to
problem 1 |p i ≤ p i ≤ p i | w i C i the efficiency of which may be estimated either
analytically or via a simulation.
In the deterministic case, when a scenario p ∈ T is fixed before scheduling (i.e.,
equalities p i = p i = p i hold for each job J i ∈J ), problem 1 |p i ≤ p i ≤ p i | w i C i

reduces to the classical problem 1 || w i C i . In contrast to the uncertain problem 1 |p i ≤

p i ≤ p i | w i C i , problem 1 || w i C i is called deterministic. The deterministic prob-

lem 1 || w i C i is correct and can be solved exactly in O ( n log n ) time [9] due to
the necessary and sufficient condition (2) for the optimality of a permutation π k =
( J k 1 ,J k 2 ,...,J k n ) ∈ S :

w k 1
p k 1 ≥

w k 2
p k 2 ≥ ...≥

w k n
p k n

, (2)

where the strict inequality p k i > 0 holds for each job J k i ∈J . Using the sufficiency of

condition (2), problem 1 || w i C i can be solved to optimality by the weighted shortest
processing time rule: process the jobs

J in non-increasing order of their weight-to-

process ratios w k i
p k i

, J k i ∈J .