On the job rotation problem



On the job rotation problem

Peter Butkovic and Seth Lewis
School of Mathematics

The University of Birmingham
Edgbaston
Birmingham B15 2TT
United Kingdom

August 26, 2006

Abstract

The job rotation problem (JRP) is the following: Given an n × n
matrix A over R {-∞} and k ≤ n, find a k × k principal submatrix of
A whose optimal assignment problem value is maximum. No polynomial
algorithm is known for solving this problem if
k is an input variable. We
analyse JRP and present polynomial solution methods for a number of
special cases.

Keywords: principal submatrix, assignment problem, job rotation
problem, node disjoint cycles.

AMS-classification: 15A15, 90C27

1 Introduction

One of the classical problems in combinatorial optimization is the (linear) as-
signment problem
which can be described as follows: A one-to-one assignment
between two
n-element sets of objects, say {A1 , ..., An} and {B1, ..., Bn} has to
be found. The cost
cij of assigning Ai to Bj is given for every pair (Ai , Bj ) and
the task is to find an assignment that minimises the total cost. This problem
has a convenient matrix formulation: If we store the coefficients
cij in an n × n
matrix C then the assignment problem means to choose n entries of C so that
no two are from the same row or column, and their sum is minimal.

The assignment problem has, of course, also a maximising form in which
the coefficients represent benefits and the object is to maximise the sum of the



More intriguing information

1. Bridging Micro- and Macro-Analyses of the EU Sugar Program: Methods and Insights
2. Gianluigi Zenti, President, Academia Barilla SpA - The Changing Consumer: Demanding but Predictable
3. Evidence on the Determinants of Foreign Direct Investment: The Case of Three European Regions
4. FUTURE TRADE RESEARCH AREAS THAT MATTER TO DEVELOPING COUNTRY POLICYMAKERS
5. Female Empowerment: Impact of a Commitment Savings Product in the Philippines
6. Insecure Property Rights and Growth: The Roles of Appropriation Costs, Wealth Effects, and Heterogeneity
7. Income Taxation when Markets are Incomplete
8. Legal Minimum Wages and the Wages of Formal and Informal Sector Workers in Costa Rica
9. Competition In or For the Field: Which is Better
10. Cyber-pharmacies and emerging concerns on marketing drugs Online