On the job rotation problem

Peter Butkovic; Seth Lewis

doi:10.1016/j.disopt.2006.11.003

On the job rotation problem

Peter Butkovic, Seth Lewis

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

205 Downloads (Pure)

Abstract

The job rotation problem (JRP) is the following: Given an n x n matrix A over \(\Re ∪ {-∞} and k ≤ n, find a k x 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.

Original language	English
Pages (from-to)	163-174
Number of pages	12
Journal	Discrete Optimization
Volume	4
Issue number	2
Early online date	13 Dec 2006
DOIs	https://doi.org/10.1016/j.disopt.2006.11.003
Publication status	Published - 1 Jun 2007

Keywords

principal submatrix
assignment problem
job rotation problem
node disjoint cycles

Access to Document

10.1016/j.disopt.2006.11.003

Lewis07JobRotationProblem.pdf
Elsevier Science B.V. Amsterdam
Submitted manuscript, 239 KB

http://www.sciencedirect.com/science/journal/15725286

Cite this

@article{41e54936b6144bd49b1f184d2a266efa,

title = "On the job rotation problem",

abstract = "The job rotation problem (JRP) is the following: Given an n x n matrix A over \(\Re ∪ {-∞} and k ≤ n, find a k x 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",

author = "Peter Butkovic and Seth Lewis",

year = "2007",

month = jun,

day = "1",

doi = "10.1016/j.disopt.2006.11.003",

language = "English",

volume = "4",

pages = "163--174",

journal = "Discrete Optimization",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - On the job rotation problem

AU - Butkovic, Peter

AU - Lewis, Seth

PY - 2007/6/1

Y1 - 2007/6/1

N2 - The job rotation problem (JRP) is the following: Given an n x n matrix A over \(\Re ∪ {-∞} and k ≤ n, find a k x 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.

AB - The job rotation problem (JRP) is the following: Given an n x n matrix A over \(\Re ∪ {-∞} and k ≤ n, find a k x 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.

KW - principal submatrix

KW - assignment problem

KW - job rotation problem

KW - node disjoint cycles

U2 - 10.1016/j.disopt.2006.11.003

DO - 10.1016/j.disopt.2006.11.003

M3 - Article

VL - 4

SP - 163

EP - 174

JO - Discrete Optimization

JF - Discrete Optimization

IS - 2

ER -

On the job rotation problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this