Information Technology Reference
In-Depth Information
random processing times
p
i
∈
[
p
i
,p
i
]
. The integer center
C
of a segment
[
p
i
,p
i
]
[
L,U
]
:
L ≤ C ≤ U
.The
was generated using the uniform distribution in the range
lower bound
p
i
for the possible job processing time
p
i
∈
[
p
i
,p
i
]
was defined as
δ
p
i
=
C ·
(1
−
100
)
,
the upper bound
p
i
of
p
i
∈
[
p
i
,p
i
]
was defined as
p
i
=
δ
100
)
.
The same range
[
L,U
]
for the varying center
C
of the segment
[
p
i
,p
i
]
was used for all jobs
J
i
∈J
C ·
(1 +
, namely:
L
=1
and
U
= 100
.InTables2-4,we
report computational results for the series of instances of the problem
1
|p
i
≤ p
i
≤
p
i
|
w
i
C
i
with the maximal possible errors
δ
%
of the job processing times from the
set
{
0
.
25%
,
0
.
4%
,
0
.
5%
,
0
.
75%
,
1%
,
2
.
5%
,
5%
,
15%
,
25%
}
.
, the weight
w
i
∈ R
+
was uniformly distributed in the range
[1
,
50]
. It should be noted that the job weights
w
i
were assumed to be known before
scheduling (in contrast to the actual processing times
p
i
For each job
J
i
∈J
of the jobs
J
i
∈J,
which
were assumed to be unknown before scheduling).
The number
n
of jobs in each instance of a series is given in column 1 of Table 2,
Table 3 and Table 4. The maximum possible error
δ
%
of the random processing times
p
i
∈
[
p
i
,p
i
]
is given in column 2. Column 3 represents the average relative number
|A|
of the arcs in the dominance digraph
(
J , A
)
constructed using condition (3) of Theorem
1. The relative number
|A|
is calculated in percentages of the number of arcs in the
complete circuit-free digraph of order
n
as follows:
n
(
n−
1)
2
|A|
:
·
100%
.
Column 4
represents the average dimension
|N
t
|
of the stability box
SB
(
π
t
,T
)
of the permutation
π
t
with the largest relative volume of a stability box.
is equal to the number of
jobs with a non-zero maximal possible variation of the processing time preserving the
optimality of permutation
π
t
∈ S
max
. Column 5 represents the average relative volume
of the stability box
|N
k
|
SB
(
π
t
,T
)
of the permutations
π
t
with the largest dimension and
relative volume of a stability box. If
SB
(
π
t
,T
)=
T
for all instances in the series, then
column 5 contains the number one.
In the experiments, we answered the question of how large the relative error
Δ
of the
objective function
γ
=
i
=1
w
i
C
i
was for the permutation
π
t
∈ S
max
with the largest
dimension and relative volume of a stability box
SB
(
π
t
,T
)
:
γ
p
∗
− γ
p
∗
γ
p
∗
Δ
=
,
where
p
∗
is the actual scenario (unknown before scheduling),
γ
p
∗
is the optimal objec-
tive function value for the scenario
p
∗
∈ T
and
γ
p
∗
=
i
=1
w
i
C
i
(
π
t
,p
∗
)
.
Column 6 represents the number of instances (among the 100 instances in a series)
for which a permutation
π
t
with the largest dimension and relative volume of the sta-
bility box
SB
(
π
t
,T
)
provides an optimal solution for the instance
1
|p
∗
|
w
i
C
i
with
the actual processing times
p
∗
=(
p
1
,p
2
,...,p
n
)
∈ T
.
From the experiments, it follows that, if the maximal possible error of the processing
times is not greater than
0
.
4%
, then the dominance digraph
(
J , A
)
is a complete circuit-
free digraph. Therefore, the permutation
π
t
∈ S
max
provides an optimal solution for
such an instance
1
|p
∗
|
w
i
C
i
.
The average (maximum) relative error
Δ
of the objective function value
γ
p
∗
calcu-
lated for the permutation
π
t
∈ S
max
constructed by the algorithm MAX-STABOX with
Search WWH ::
Custom Search