On the job rotation problem

assigned to job j only if (i, j) is from a given set of feasible transitions. This can
obviously be represented by a {0, -∞} matrix C, where a 0 corresponds to a
feasible move. Alternatively, this version can be represented by a (non-weighted)
digraph D = (V, E), where V = {v1, v2, . . . , vn} and E = {(vi, vj); cij = 0}.

The number of principal submatrices of order k of a matrix of order n is
ⁿ_k . Therefore if k is an input variable, solving the assignment problem for all
principal submatrices and then comparing the resulting values would be non-
polynomial. If k ≤ n is fixed, then the method would be polynomial (though
of a high degree in most cases). However, the total number of submatrices of
all orders is _kⁿ₌₁ ⁿ_k = 2ⁿ - 1 and therefore checking all of them would not
solve JRP for all k in polynomial time. In fact, no polynomial method seems
to be known for solving this problem, neither is it proved to be N P -hard. In
this paper we present a number of cases when JRP is solvable polynomially.
Note that there is a randomized polynomial algorithm for solving JRP [5]. It
may be interesting to mention that the problem arising by removing the word
“principal” from the formulation of the JRP is easily solvable [10].

In Section 2 we will give an overview of known results. Section 3 deals
with matrices over T = {-∞, 0} and Section 4 contains results for matrices
over R := R U {-∞}. These include the proof that JRP(A) can be solved
in polynomial time if this is true for every irreducible diagonal block of the
Frobenius normal form of A.

2 Definitions and known results

In the rest of the paper we will assume that n ≥ 1 is a given integer and we
denote by N the set {1,..., n}. If A = (a_ij) ∈ Rn×ⁿ then we denote

m(A) = m_∈a_Px    ai,π(i)

^{π∈ n} i∈N

where Pn stands for the set of all permutations of the set N . The quantity
a_i,π(_i) will be called the weight of π (notation w(A, π)). Obviously, m(A) is
i∈N

the optimal value of the assignment problem for the matrix A. The set of all
optimal permutations will be denoted by ap(A), that is,

ap(A) = {π ∈ Pn; m(A) =    ai,π(i)}.

i∈N

<<   1   2   3   4   5   6   >>

More intriguing information