Information Technology Reference
In-Depth Information
w
k
i
p
k
i
w
k
j
p
k
j
d
k
i
=max
,
max
i<j≤n
,i∈{
1
,
2
,...,n−
1
},
(4)
w
k
n
p
k
n
d
k
n
=
.
(5)
The upper bound
d
k
i
,J
k
i
∈J,
on the maximal range of possible variations of the
w
k
i
p
k
i
weight-to-process ratio
preserving the optimality of the permutation
π
k
is calcu-
lated as follows:
w
k
i
p
k
i
w
k
j
p
k
j
d
k
i
=min
,
min
1
≤j<i
,i∈{
2
,
3
,...,n},
(6)
w
k
1
p
k
1
d
k
1
=
.
(7)
For Example 1, the values
d
k
i
,i ∈{
1
,
2
,...,
8
},
defined in (4) and (5) are given in
column 5 of Table 1. The values
d
k
i
defined in (6) and (7) are given in column 6. In
[12], the following claim has been proven.
Theorem 2.
[12]
If there is no job
J
k
i
,
i ∈{
1
,
2
,...,n−
1
}
, in permutation
π
k
=
(
J
k
1
,J
k
2
,...,J
k
n
)
∈ S
such that inequality
w
k
i
p
k
i
<
w
k
j
p
k
j
(8)
holds for at least one job
J
k
j
,
j ∈{i
+1
,i
+2
,...,n}
, then the stability box
SB
(
π
k
,T
)
is calculated as follows:
w
k
i
d
k
i
,
w
k
i
d
k
i
SB
(
π
k
,T
)=
×
d
k
i
≤d
k
i
.
(9)
Otherwise,
.
Using Theorem 2, we can calculate the stability box
SB
(
π
k
,T
)=
∅
SB
(
π
1
,T
)
of the permutation
π
1
=(
J
1
,J
2
,...,J
8
)
in Example 1. First, we convince that there is no job
J
k
i
,
i ∈
{
1
,
2
,...,n−
1
},
with inequality (8). Due to Theorem 2,
SB
(
π
1
,T
)
=
∅
.
The bounds
w
k
i
d
k
i
and
w
k
i
d
k
i
on the maximal possible variations of the processing times
p
k
i
preserving the optimality of the permutation
π
1
are given in columns 7 and 8 of
Table 1. The maximal ranges (segments) of possible variations of the job processing
times within the stability box
SB
(
π
1
,T
)
are dashed in a coordinate system in Fig. 1,
where the abscissa axis is used for indicating the job processing times and the ordinate
axis for the jobs from set
.
Using formula (9), we obtain the stability box for permutation
π
1
as follows:
J
w
2
d
2
w
4
d
4
w
6
d
6
w
8
d
8
,
w
2
d
2
,
w
4
d
4
,
w
6
d
6
,
w
8
d
8
SB
(
π
1
,T
)=
×
×
×
=[3
,
6]
×
[9
,
10]
×
[12
,
15]
×
[19
,
20]
.
Search WWH ::
Custom Search