Information Technology Reference
In-Depth Information
Property 6.
There exists a permutation
π
t
∈ S
with the set
L
⊆L
of maximal seg-
ments
[
l
i
,u
i
]
of possible variations of the processing time
p
i
,J
i
∈J,
preserving the
optimality of the permutation
π
t
.
Proof.
Due to Property 2 and steps 1 - 4 of algorithm MAX-STABOX, the maximal
segments
[
l
i
,u
i
]
and
[
l
v
,u
v
]
(ifany)ofjobs
J
i
and
J
v
satisfying (11) preserve the
optimality of the permutation
π
t
∈ S
max
.
Let
J
∗
denote the set of all jobs
J
i
satisfying (13). It is easy to see that
(
p
i
, p
i
]=∅
.
J
i
∈J
Therefore,
J
(
i
)=∅
.
J
i
∈J
Hence, step 9 is correct: putting the set of jobs
in the positions defined in steps 3 - 8
does not cause any contradiction of the job orders.
J
Obviously, steps 1 and 2 take
O
(
n
log
n
)
time. Due to Properties 4 and 5, steps 6, 7 and 9
take
O
(
n
)
time. Step
10
takes
O
(
n
log
n
)
time since algorithm STABOX derived in [12]
has the same complexity. Thus, the whole algorithm MAX-STABOX takes
O
(
n
log
n
)
time. It is easy to convince that, due to steps 1 - 5, the permutation
π
t
constructed
by algorithm MAX-STABOX possesses property (a) and, due to steps 6, 7 and 9, this
permutation possesses property (b).
Remark 2.
Algorithm MAX-STABOX constructs a permutation
π
t
∈ S
such that the
dimension
SB
(
π
t
,T
)=
×
t
i
∈N
t
[
l
t
i
,u
t
i
]
⊆ T
is the largest one
for all permutations
S
, and the volume of the stability box
|N
t
|
of the stability box
SB
(
π
t
,T
)
is the largest one
for all permutations
π
k
∈ S
having the largest dimension
|N
k
|
=
|N
t
|
of their stability
boxes
SB
(
π
k
,T
)
.
Returning to Example 1, one can show (using Algorithm MAX-STABOX) that permu-
tation
π
1
=(
J
1
,J
2
,...,J
8
)
has the largest dimension and volume of a stability box.
Next, we compare
SB
(
π
1
,T
)
with the stability boxes calculated for the permutations
obtained by the three heuristics defined as follows.
The lower-point heuristic generates an optimal permutation
π
l
∈ S
for the instance
1
|p
L
|
w
i
C
i
with
p
L
=(
p
L
1
,p
L
2
,...,p
n
)
∈ T.
(14)
The upper-point heuristic generates an optimal permutation
π
u
∈ S
for the instance
1
|p
U
|
w
i
C
i
with
p
U
=(
p
U
1
,p
U
2
,...,p
n
)
∈ T.
(15)
The mid-point heuristic generates an optimal permutation
π
m
∈ S
for the instance
1
|p
M
|
w
i
C
i
with
p
U
1
− p
L
,
p
U
2
− p
L
,...,
p
n
− p
n
2
p
M
1
2
=
∈ T.
(16)
2
2
Search WWH ::
Custom Search