Information Technology Reference
In-Depth Information
J
8
J
7
J
6
J
5
J
4
J
3
J
2
J
1
2
4
6
8
10
12
14
16
18
20
Fig. 1.
The maximal ranges
[
l
i
,u
i
]
of possible variations of the processing times
p
i
,i ∈
{
2
,
4
,
6
,
8
},
within the stability box
SB
(
π
1
,T
)
are dashed
Each job
J
i
,
i ∈{
1
,
3
,
5
,
7
},
has an empty range of possible variations of the time
p
i
preserving the optimality of permutation
π
1
since
d
i
>d
i
(see columns 5 and 6 in
SB
(
π
1
,T
)
is equal to
4=8
−
4
.The
volume of this stability box is equal to
9=3
·
1
·
3
·
1
.
In [12], an
O
(
n
log
n
)
algorithm STABOX has been developed for calculating the
stability box
Table 1). The dimension of the stability box
SB
(
π
k
,T
)
for a fixed permutation
π
k
∈ S
.
For practice, the value of the relative volume of a stability box is more useful than
its absolute value. The relative volume of a stability box is defined as the product of the
fractions
w
i
d
i
−
:
p
i
− p
i
w
i
d
i
(10)
for the jobs
J
i
∈J
having non-empty ranges
[
l
i
,u
i
]
of possible variations of the pro-
cessing time
p
i
(inequality
d
i
≤ d
i
must hold for such a job
J
i
∈J
).
The relative volume of the stability box for permutation
π
1
in Example 1 is calculated
as follows:
8
·
4
·
9
·
5
=
1
160
.
The absolute volume of the whole box of the scenarios
T
is equal to
2880 = 1
·
8
·
4
·
1
·
9
·
2
·
5
. The relative volume of the rectangular box
T
is defined as 1.
3.2
Properties of a Stability Box
A job permutation in the set
S
with a larger dimension and a larger volume of the
stability box seems to be more efficient than one with a smaller dimension and (or) a
smaller volume of stability box.
We investigate properties of a stability box, which allow us to derive an
O
(
n
log
n
)
algorithm for choosing a permutation
π
t
∈ S
which has
(a) the largest dimension
|N
t
|
of the stability box
SB
(
π
t
,T
)=
×
t
i
∈N
t
[
l
t
i
,u
t
i
]
⊆ T
among all permutations
π
k
∈ S
and
Search WWH ::
Custom Search