Information Technology Reference
In-Depth Information
Algorithm.
MAX-STABOX
Segments
[
p
i
,p
i
]
, weights
w
i
,
J
i
∈J
Input:
.
Permutation
π
t
∈ S
max
, stability box
Output:
SB
(
π
t
,T
)
.
Step 1:
Construct the list
M
(
U
)=(
J
u
1
,J
u
2
,...,J
u
n
)
and the list
w
u
1
p
u
1
,
w
u
2
p
u
2
,...,
w
u
n
p
u
n
)
in non-increasing order of
w
u
r
W
(
U
)=(
.
p
u
r
Ties are broken via decreasing
w
u
r
p
u
r
.
Step 2:
Construct the list
M
(
L
)=(
J
l
1
,J
l
2
,...,J
l
n
)
and the list
w
l
1
p
l
1
,
w
l
2
p
l
2
,...,
w
l
n
p
l
n
)
in non-increasing order of
w
l
r
W
(
L
)=(
.
p
l
r
Ties are broken via decreasing
w
l
r
p
l
r
.
Step 3:
FOR
j
=1
to
j
=
n
DO
compare job
J
u
j
and job
J
l
j
.
Step 4:
IF
J
u
j
=
J
l
j
THEN job
J
u
j
has to be located in position
j
in
permutation
π
t
∈ S
max
GOTO step 8.
Step 5:
ELSE job
J
u
j
=
J
i
satisfies inequalities (13). Construct the set
J
(
i
)=
{J
u
r
+1
,J
u
r
+2
,...,J
l
k
+1
}
of all jobs
J
v
satisfying
inequalities (13), where
J
i
=
J
u
j
=
J
l
k
.
Step 6:
Choose the largest range
[
l
u
j
,u
u
j
]
among those generated for the
job
J
u
j
=
J
i
.
J
+
(
i
)
generating
the largest range
[
l
u
j
,u
u
j
]
.Set
j
=
k
+1
GOTO step 4.
J
−
(
i
)
and
Step 7:
Partition the set
J
(
i
)
into the subsets
Step 8:
Set
j
:=
j
+1
GOTO step 4.
END FOR
Construct the permutation
π
t
∈ S
max
via putting the jobs
Step 9:
J
in the
positions defined in steps 3 - 8.
Step 10: Construct the stability box
SB
(
π
t
,T
)
using algorithm STABOX
derived in [12]. STOP.
Steps 1 and 2 of algorithm MAX-STABOX are based on Property 3 and Remark 1. Step
4isbasedonProperty2.Steps5-7arebasedonProperty4,part
(ii)
. Step 9 is based
on Property 6 which follows.
To prove Property 6, we have to analyze algorithm MAX-STABOX. In steps 1, 2 and
4, all jobs
t
J
=
{J
i
| J
u
j
=
J
i
=
J
l
j
}
having the same position in both lists
M
(
U
)
M
(
L
)
obtain fixed positions in the permutation
π
t
∈ S
max
.
The positions of the remaining jobs
and
t
in the permutation
π
t
are determined in
J\J
t
may shorten the original segment
[
p
i
,p
i
]
of
steps 5 - 7. The fixed order of the jobs
J
t
. We denote such a reduced segment as
[
p
i
,p
i
]
.So,insteps5-7,
the reduced segment
[
p
i
,p
i
]
has to be considered instead of original segment
[
p
i
,p
i
]
for a job
J
i
∈J\J
ajob
J
i
∈J\J
t
.
L
denote the maximal subset of set
Let
L
(see Property 5) including exactly one
element from each set
L
(
i
)
, for which job
J
i
∈J
satisfies the strict inequalities (13).
Search WWH ::
Custom Search