Information Technology Reference
In-Depth Information
SB
(
π
t
,T
)
among all permutations
π
k
∈ S
(b) the largest volume of the stability box
|N
k
|
=
|N
t
|
SB
(
π
k
,T
)
.
having the largest dimension
of their stability boxes
Definition 1 implies the following claim.
Property 1.
For any jobs
J
i
∈J
,
v
=
i
,
(
w
i
/u
i
,w
i
/l
i
)
w
v
/p
v
,w
v
/p
v
= ∅
.
and
J
v
∈J
Let
S
max
denote the subset of all permutations
π
t
in the set
S
possessing properties (a)
and (b). Using Property 1, we shall show how to define the relative order of a job
J
i
∈J
with respect to a job
J
v
∈J
for any
v
=
i
in a permutation
π
t
=(
J
t
1
,J
t
2
,...,J
t
n
)
∈
S
max
. To this end, we have to treat all three possible cases (I)-(III) for the intersection
of the open interval
w
i
p
i
.
The order of the jobs
J
i
and
J
v
in the desired permutation
π
t
∈ S
max
may be defined in the cases (I)-(III)
using the following rules.
Case (I) is defined by the inequalities
w
v
p
v
≤
and the closed interval
w
v
p
v
,
w
i
p
i
,
w
v
p
v
w
i
p
i
w
v
p
v
≤
w
i
p
i
,
(11)
provided that at least one of inequalities (11) is strict.
In case (I), the desired order of the jobs
J
v
and
J
i
in permutation
π
t
∈ S
max
may be
defined by a strict inequality from (11): job
J
v
proceeds job
J
i
in permutation
π
t
.
Indeed, if job
J
i
proceeds job
J
v
, then the maximal ranges
[
l
i
,u
i
]
and
[
l
v
,u
v
]
of
possible variations of the processing times
p
i
and
p
v
preserving the optimality of
π
k
∈
S
are both empty (it follows from equalities (4) - (7) and (9)). Thus, the following
property is proven.
Property 2.
For case (I), there exists a permutation
π
t
∈ S
max
,inwhichjob
J
v
pro-
ceeds job
J
i
.
Case (II) is defined by the equalities
w
v
p
v
=
w
i
p
i
w
v
p
v
=
w
i
p
i
,
.
(12)
Property 3.
For case (II), there exists a permutation
π
t
∈ S
max
, in which the jobs
J
i
and
J
v
are located adjacently:
i
=
t
r
and
v
=
t
r
+1
.
Proof.
The maximal ranges
[
l
i
,u
i
]
and
[
l
v
,u
v
]
of possible variations of the processing
times
p
i
and
p
v
preserving the optimality of
π
k
∈ S
are both empty.
If job
J
i
and job
J
v
are located adjacently, then the maximal range
[
l
u
,u
u
]
of possible
variations of the processing time
p
u
preserving the
optimality of the permutation
π
k
is no less than that if at least one job
J
w
∈J\{J
i
,J
v
}
is located between job
J
i
and job
J
v
.
If equalities (12) hold, one can restrict the search for a permutation
π
t
∈ S
max
by a
subset of permutations in set
S
with the adjacently located jobs
J
i
and
J
v
(Property 3).
Moreover, the order of such jobs
for any job
J
u
∈J\{J
i
,J
v
}
{J
i
,J
v
}
does not influence the volume of the stability
box and its dimension.
Search WWH ::
Custom Search