On the job rotation problem

benefits. Many solution methods exist for the assignment problem [1], [6], prob-
ably the best known being the Hungarian method of computational complexity
O(n³), whose many variants exist in the literature.

The job rotation problem is motivated by the following task: Suppose that a
company with n employees requires these workers to swap their jobs (possibly
on a regular basis) in order to avoid exposure to monotonous tasks (for instance
manual workers at an assembly line or ride operators in a theme park). It is also
required that to maintain stability of service only a certain number of employees,
say k (k < n), actually swap their jobs. With each transition old job - new job a
coefficient is associated expressing either the cost (for instance for an additional
training) or the preference of the worker to this particular change. So the aim
is to select k employees and to suggest a plan of the job changes between them
so that the sum of the coefficients corresponding to these changes is minimum
or maximum.

For any set X and positive integer n the symbol X^n×n will denote the set
of all n × n matrices over X . In most cases we will deal with matrices over
R := R U {-∞}. By a principal submatrix of a square matrix A we understand
as usual any submatrix of A whose set of row indices is the same as the set of
column indices. A principal submatrix of A = (a_ij) ∈ Rn×ⁿ is therefore any
matrix of the form
where 1 ≤ i1 < ... < ik ≤ n. This matrix will be denoted by A(i1, i2, ..., ik).
Hence the job rotation problem is the problem to find, for a given n × n matrix
A and k < n, a k × k principal submatrix of A for which the optimal assignment
problem value is minimal or maximal (the diagonal entries can be set to +∞
or -∞ to avoid an assignment to the same job). For a particular A and k, we
shall refer to this problem as JRP (A, k). The task of solving the job rotation
problem for all k, we shall refer to as JRP (A) or just JRP. In the rest of the
paper, we will discuss the maximisation version of the problem.

Note that there is also a “non-weighted” version of JRP in which it is only
given which job moves are feasible. The problem is to decide if it is possible to
re-assign / rotate k jobs between the employees, (k ∈ N), where job i can be

<<   <   1   2   3   4   5   >   >>