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