Advanced search
Add to list

Block rearranging elements within matrix columns to minimize the variability of the row sums

Author
Organization
Abstract
Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic-based on an idea of variance equalization-to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar-Karp differencing algorithm.
Keywords
MACHINE SCHEDULING PROBLEM, EXACT ALGORITHMS, MIXABILITY, BOUNDS, Assembly line crew scheduling, Greedy algorithm, Rearrangements, k-Partitioning, Karmarkar-Karp differencing algorithm

Citation

Please use this url to cite or link to this publication:

MLA
Boudt, Kris, Edgars Jakobsons, and Steven Vanduffel. “Block Rearranging Elements Within Matrix Columns to Minimize the Variability of the Row Sums.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 16.1 (2018): 31–50. Print.
APA
Boudt, K., Jakobsons, E., & Vanduffel, S. (2018). Block rearranging elements within matrix columns to minimize the variability of the row sums. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 16(1), 31–50.
Chicago author-date
Boudt, Kris, Edgars Jakobsons, and Steven Vanduffel. 2018. “Block Rearranging Elements Within Matrix Columns to Minimize the Variability of the Row Sums.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 16 (1): 31–50.
Chicago author-date (all authors)
Boudt, Kris, Edgars Jakobsons, and Steven Vanduffel. 2018. “Block Rearranging Elements Within Matrix Columns to Minimize the Variability of the Row Sums.” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 16 (1): 31–50.
Vancouver
1.
Boudt K, Jakobsons E, Vanduffel S. Block rearranging elements within matrix columns to minimize the variability of the row sums. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH. Heidelberg: Springer Heidelberg; 2018;16(1):31–50.
IEEE
[1]
K. Boudt, E. Jakobsons, and S. Vanduffel, “Block rearranging elements within matrix columns to minimize the variability of the row sums,” 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, vol. 16, no. 1, pp. 31–50, 2018.
@article{8600208,
  abstract     = {Several problems in operations research, such as the assembly line crew scheduling problem and the k-partitioning problem can be cast as the problem of finding the intra-column rearrangement (permutation) of a matrix such that the row sums show minimum variability. A necessary condition for optimality of the rearranged matrix is that for every block containing one or more columns it must hold that its row sums are oppositely ordered to the row sums of the remaining columns. We propose the block rearrangement algorithm with variance equalization (BRAVE) as a suitable method to achieve this situation. It uses a carefully motivated heuristic-based on an idea of variance equalization-to find optimal blocks of columns and rearranges them. When applied to the number partitioning problem, we show that BRAVE outperforms the well-known greedy algorithm and the Karmarkar-Karp differencing algorithm.},
  author       = {Boudt, Kris and Jakobsons, Edgars and Vanduffel, Steven},
  issn         = {1619-4500},
  journal      = {4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH},
  keywords     = {MACHINE SCHEDULING PROBLEM,EXACT ALGORITHMS,MIXABILITY,BOUNDS,Assembly line crew scheduling,Greedy algorithm,Rearrangements,k-Partitioning,Karmarkar-Karp differencing algorithm},
  language     = {eng},
  number       = {1},
  pages        = {31--50},
  publisher    = {Springer Heidelberg},
  title        = {Block rearranging elements within matrix columns to minimize the variability of the row sums},
  url          = {http://dx.doi.org/10.1007/s10288-017-0344-4},
  volume       = {16},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: