On the job rotation problem



Algorithm JRPBLOCKDIAG

Input: A = blockdiag(A 1, A2,..., Ap) Rn×n.

Output: For k = 1, . . . , n, δk (A), and if δk (A) is finite, then also k independent
entries of a
k × k principal submatrix of A whose total is δk (A).

1. Set M0 = {(0,0, 0)}

2. For j = 1 to p :

(a) For r = 1 to n(j ) :

i. Find δr(Aj).

ii. Find Bjr (Aj )r and πjr ap(Bj r) such that w(Bjr, πjr) =
δr(Aj).

(b) Set Mj = Mj-1

(c) For each element (S, w, l) Mj-1 :

j

For each r = 1 to min(   n(t) - l, n(j)) with δr (Aj ) finite :

t=1

i. If @(S0, w0, l + r) Mj, then add (S {(j, r)}, w + δr (Aj), l + r)
to
Mj .

ii. If (S0, w0, l + r) Mj and w0 < w + δr (Aj ), then remove
(
S0, w0, l + r) from Mj and add (S {(j, r)}, w + δr (Aj), l + r) to
Mj.

3. For k = 1 to n :

If (S, w, k) Mp, then return δk (A) = w, and for i = 1, . . . , r and all
(
j, r) S, return the element of A that corresponds to the (i, πjr (i)) entry
of
Bjr. Else return δk (A) = -∞.

Figure 2: An algorithm for solving JRP for block diagonal matrices.

Lemma 20.

1. If (S, w, k) Mj in Step 3 of the algorithm, then

(a) S {1, . . . , p} × {1, . . . , n},

(b) P δs(Ai) = w,

(i,s)S

(c) P s = k,

(i,s)S

(d) If (S0 , w0 , k) Mj , then S0 = S and w0 = w,

(e) If S0 {1,...,p} × {1,...,n}, w0 = P δs(Ai) and P s = k

(i,s)S0                    (i,s)S0

then w0 ≤ w.

16



More intriguing information

1. Multi-Agent System Interaction in Integrated SCM
2. Towards Teaching a Robot to Count Objects
3. The name is absent
4. The name is absent
5. Firm Creation, Firm Evolution and Clusters in Chile’s Dynamic Wine Sector: Evidence from the Colchagua and Casablanca Regions
6. Heavy Hero or Digital Dummy: multimodal player-avatar relations in FINAL FANTASY 7
7. The name is absent
8. A Rational Analysis of Alternating Search and Reflection Strategies in Problem Solving
9. Evidence-Based Professional Development of Science Teachers in Two Countries
10. Concerns for Equity and the Optimal Co-Payments for Publicly Provided Health Care