Information Technology Reference
In-Depth Information
3
The Stability Box
In [12], the stability box
SB
(
π
k
,T
)
within a set of scenarios
T
has been defined for
a permutation
π
k
=(
J
k
1
,J
k
2
,...,J
k
n
)
∈ S
. To present the definition of the stability
box
SB
(
π
k
,T
)
, we need the following notations.
We denote
J
(
k
i
)=
{J
k
1
,J
k
2
,...,J
k
i−
1
}
and
J
[
k
i
]=
{J
k
i
+1
,J
k
i
+2
,...,J
k
n
}
.
Let
S
k
i
denote the set of permutations
(
π
(
J
(
k
i
))
,J
k
i
,π
(
J
[
k
i
]))
∈ S
of the jobs
J
,
π
(
J
)
being a permutation of the jobs
J
⊂J
.Let
N
k
denote a subset of set
N
=
. The notation
1
|p|
w
i
C
i
will be used for indicating an instance with a
{
1
,
2
,...,n}
fixed scenario
p ∈ T
of the deterministic problem
1
||
w
i
C
i
.
Definition 1.
[12]
The maximal closed rectangular box
SB
(
π
k
,T
)=
×
k
i
∈N
k
[
l
k
i
,u
k
i
]
⊆ T
is a stability box of permutation
π
k
=(
J
k
1
,J
k
2
,...,J
k
n
)
∈ S,
if permutation
π
e
=
(
J
e
1
,J
e
2
,...,J
e
n
)
∈ S
k
i
being optimal for the instance
1
|p|
w
i
C
i
with a scenario
p
=(
p
1
,p
2
,...,p
n
)
∈ T
remains optimal for the instance
1
|p
|
w
i
C
i
with a sce-
nario
p
∈{×
i−
1
j
=
i
+1
[
p
k
j
,p
k
j
]
}
for each
k
i
∈ N
k
.Ifthere
does not exist a scenario
p ∈ T
such that permutation
π
k
is optimal for the instance
j
=1
[
p
k
j
,p
k
j
]
}×
[
l
k
i
,u
k
i
]
×{×
1
|p|
w
i
C
i
,then
SB
(
π
k
,T
)=
∅
.
The maximality of the closed rectangular box
SB
(
π
k
,T
)=
×
k
i
∈N
k
[
l
k
i
,u
k
i
]
in Defini-
tion 1 means that the box
SB
(
π
k
,T
)
⊆ T
has both a maximal possible dimension
|N
k
|
and a maximal possible volume.
For any scheduling instance, the stability box is a subset of the stability region
[13,14]. However, we substitute the stability region by the stability box, since the latter
is easy to compute [11,12]. In [11], a branch-and-bound algorithm has been developed
to select a permutation in the set
S
with the largest volume of a stability box. If several
permutations have the same volume of the stability box, the algorithm from [11] selects
one of them due to simple heuristics. The efficiency of the constructed permutations has
been demonstrated on a set of randomly generated instances with
5
≤ n ≤
100
.
In [12], an
O
(
n
log
n
)
algorithm has been developed for calculating a stability box
SB
(
π
k
,T
)
for the fixed permutation
π
k
∈ S
and an
O
(
n
2
)
algorithm has been devel-
oped for selecting a permutation in the set
S
with the largest dimension and volume of
a stability box. The efficiency of these algorithms was demonstrated on a set of ran-
domly generated instances with
10
≤ n ≤
1000
. All algorithms developed in [11,12]
use the precedence-dominance relation on the set of jobs
J
and the solution concept of
a minimal dominant set
S
(
T
)
⊆ S
defined as follows.
Definition 2.
[10]
The set of permutations
S
(
T
)
⊆ S
is a minimal dominant set for
a problem
1
|p
i
≤ p
i
≤ p
i
|
w
i
C
i
, if for any fixed scenario
p ∈ T
,theset
S
(
T
)
contains at least one optimal permutation for the instance
1
|p|
w
i
C
i
, provided that
any proper subset of set
S
(
T
)
loses such a property.
Definition 3.
[10]
Job
J
u
dominates job
J
v
, if there exists a minimal dominant set
S
(
T
)
for the problem
1
|p
i
≤ p
i
≤ p
i
|
w
i
C
i
such that job
J
u
precedes job
J
v
in every
permutation of the set
S
(
T
)
.
Search WWH ::
Custom Search