Information Technology Reference
In-Depth Information
Definition 18.
Let
freeright
(i, j )
be the largest
j
′
such that for all
k
,
j
k
j
′
,
C
ik
∈ E
.
We define
next
(j, L)
to be the line in
L
that reads from the channel with the
rightmost empty block in column
j
.
Definition 19.
Let
next
(j, L)
be a line
l
∈
L
such that
freeright
(l[j ],j) =
max
{
freeright
(l
′
[j ],j) | l
′
∈ L}
.
We define
First
(i)
to be the column in which a requested object first appears in
row
i
.
Definition 20.
Let
First
(i)
be the smallest
j
such that for all
j
′
,1
j
′
<j
,
C
ij
′
∈ S
.
Let
Start
(m)
be rows
{i
1
,...,i
m
}
such that for any row
i
′
/∈{i
1
,...,i
m
}
First
(i)
First
(i
′
)
for all
i ∈{i
1
,...,i
m
}
. In other words,
Start
(m)
are rows that contain
objects before any other rows. These rows will be the starting point for our
MAX_cut
lines, as we obviously do not want to switch a line before it has read any objects on
a channel (
Fig. 40
(a)).
POS Algorithm
1.
if (
MAX_total
=
MAX_cut
)
2.
use
Row Scan
;
3. else
4. Let
m =
MAX
_
cut
5. Create
m
lines,
l
1
,...,l
m
6.
Lines
={l
1
,...,l
m
}
/* Set containing all the lines */
7.
l
1
[
1
],...,l
m
[
1
]=
Start
(m)
/* Initialize lines */
8.
for
j =
2to
M
do {
9.
L =
Lines
/* All the lines */
A = R
j
/* Required Rows:
|A|
|L|
*/
10.
11.
foreach
l ∈ L
/* check for no switch, line reads an object */
12.
if
l[j ]∈A
then
l[j ]=l[j −
1
]
;
A = A −{l[j ]}
;
L = L −{l}
13.
foreach
i ∈ A
/* remaining objects, inside switch */
14.
l =
next
(j, L)
15.
l[j ]=i
16.
L = L −{l}
17.
foreach
l ∈ L
/* no object to read, no switch */
18.
l[j ]=l[j −
1
]}
