On the job rotation problem

of these disjoint subgraphs, and it is not possible to have a cycle in D(A) with
arcs corresponding to elements from more than one of the matrices A1 , . . . , Ap.

We now show how to solve JRP (A) for A = blockdiag(A1 , A2, . . . , Ap) in
polynomial time, as long as we can solve JRP (Aj ) in polynomial time, for
j = 1, . . . , p. This is shown in an algorithm called JRPBLOCKDIAG (see
Figure 2).

Let n(j) be the order of Aj , j = 1, . . . , p. Assume that we have solved
JRP (Aj). This may have been done in polynomial time if Aj is one of the
special types of matrix previously mentioned in this paper.

So for j = 1, . . . p and r = 1, . . . , k we are able to find δ_r (Aj ) and also a
principal submatrix Bjr ∈ (Aj)r (where (Aj)r is the set of all r × r principal
submatrices of Aj ) and permutation πjr ∈ ap(Bj r) such that w(Bjr , πjr) =
δr(Aj).

Let Dj = D(Aj ). For each block Aj , we have the following information: For
r = 1, . . . , k, the permutation πjr in Dj gives cycles of total length r and total
weight δr (Aj).

We will use S , a set of pairs to tell us which submatrix to select and which
elements from within it to select. We do this by assigning pairs (j, r) to S. A
pair (j, r) tells us that by choosing Bjr and πjr we select a total of r elements
from Bjr and give a total sum of δr (Aj ).

There are p stages to the algorithm. At each stage information is collected
and then stored within a set of triples called Mj . Each triple has the form
(S, w, k), where S is as described above, w is the total weight of elements selected
by using the information in S , and k is the total number of elements selected
by using the information in S .

M0 is set to {(0,0, 0)} at Stage 0. For j = 1,... ,p, at Stage j, the infor-
mation found from Aj (i.e. δ1 (Aj), δ2 (Aj), . . . , δ_n(j) (Aj)) and the information
from Stage j - 1 (i.e. Mj_-1) is combined to produce Mj . We start by copying
all triples from Mj-1 to Mj. Next, if we can find a triple (S, w, k) (of the form
described above) by combining the information found from Aj and Mj-1 that
is not in Mj , then we add (S, w, k) to Mj . Otherwise, if w is larger than the
second coordinate of any triple in Mj having third component equal to k, then
we replace that triple with (S, w, k) in Mj .

We now give the algorithm, called JRPBLOCKDIAG, and then discuss the
correctness and complexity of this algorithm.

15

<<   12   13   14   15   16   17   18   >>

More intriguing information