Information Technology Reference
In-Depth Information
We obtain the permutation
π
l
=(
J
2
,J
1
,J
4
,J
3
,J
6
,J
5
,J
8
,J
7
)
with the stability box
w
2
d
2
w
6
d
6
,
w
2
d
2
,
w
6
d
6
SB
(
π
l
,T
)=
×
=[1
,
2]
×
[10
,
11]
.
SB
(
π
l
,T
)
is equal to 1. We obtain the permutation
π
u
=
(
J
1
,J
3
,J
2
,J
4
,J
5
,J
7
,J
6
,J
8
)
and the permutation
π
m
=(
J
1
,J
2
,J
4
,J
3
,J
5
,J
6
,J
8
,J
7
)
.
The volume of the stability box
The volume of the stability box
w
4
d
4
w
8
d
8
,
w
4
d
4
,
w
8
d
8
SB
(
π
u
,T
)=
×
=[9
,
10]
×
[19
,
20]
is equal to 1. The volume of the stability box
w
2
d
2
w
6
d
6
,
w
2
d
2
,
w
6
d
6
SB
(
π
m
,T
)=
×
=[3
,
6]
×
[12
,
15]
is equal to
9=3
·
3
. It is the same volume of the stability box as that of permutation
π
1
.
Note, however, that the dimension
|N
m
|
of the stability box
SB
(
π
m
,T
)
is equal to 2,
SB
(
π
1
,T
)
of the permutation
π
1
∈ S
max
is equal to 4. Thus,
π
m
∈ S
max
since permutation
π
m
does not possess property (a).
while the dimension
|N
1
|
of the stability box
4
Computational Results
There might be several permutations with the largest dimension and relative volume of
a stability box
SB
(
π
t
,T
)
since several consecutive jobs in a permutation
π
t
∈ S
max
may have an empty range of possible variations of their processing times preserving the
optimality of the permutation
π
t
. In the computational experiments, we break ties in
ordering such jobs by adopting the mid-point heuristic which generates a subsequence
of these jobs as a part of an optimal permutation
π
m
∈ S
for the instance
1
|p
M
|
w
i
C
i
with the scenario
p
M
∈ T
defined by (16).
Our choice of the mid-point heuristic is based on the computational results of the
experiments conducted in [12] for the problem
1
|p
i
≤ p
i
≤ p
i
|
w
i
C
i
with
10
≤
n ≤
1000
. In those computational results, the subsequence of a permutation
π
m
∈ S
outperformed both the corresponding subsequence of the permutation
π
l
∈ S
and that
of the permutation
π
u
∈ S
defined by (14) and (15), respectively.
We coded the algorithm MAX-STABOX combined with the mid-point heuristic for
ordering consecutive jobs having an empty range of their processing times preserving
the optimality of the permutation
π
t
∈ S
max
in C++. This algorithm was tested on a PC
with AMD Athlon (tm) 64 Processor 3200+, 2.00 GHz, 1.96 GB of RAM. We solved
(exactly or approximately) a lot of randomly generated instances. Some of the compu-
tationalresultsobtainedarepresentedinTables2-4forrandomly generated instances
of the problem
1
|p
i
≤ p
i
≤ p
i
|
w
i
C
i
with the number
n ∈{
1000
,
1100
,...,
2000
}
of jobs.
EachseriespresentedinTables2-4contains100solvedinstanceswiththesame
combination of the number
n
of jobs and the same maximal possible error
δ
%
of the
Search WWH ::
Custom Search