Another well-solvable case of the QAP: maximizing the job completion time variance

DOI10.1016/j.orl.2012.06.005zbMath1250.90045MaRDI QIDQ1758277

Eranda Çela, Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 8 November 2012

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2012.06.005

zbMATH Keywords

machine scheduling; combinatorial optimization; quadratic assignment problem; well-solvable special case

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

A New Tractable Case of the QAP with a Robinson Matrix, An LP-based characterization of solvable QAP instances with chess-board and graded structures, Linearizable special cases of the QAP, A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, Using well-solvable minimum cost exact covering for VLSI clock energy minimization, Linear programming insights into solvable cases of the quadratic assignment problem, Four-point conditions for the TSP: the complete complexity classification, Well-solvable cases of the QAP with block-structured matrices, Robinsonian matrices: recognition challenges

Cites Work

• Unnamed Item
• Optimal sequencing of a set of positive numbers with the variance of the sequence's partial sums maximized
• The Wiener maximum quadratic assignment problem
• Extreme Hamiltonian lines
• A solvable case of the quadratic assignment problem
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Completion time variance minimization on a single machine is difficult
• The quadratic assignment problem. Theory and algorithms
• Perspectives of Monge properties in optimization
• Assignment Problems and the Location of Economic Activities
• On the Minimization of Completion Time Variance with a Bicriteria Extension
• Minimizing the Time-in-System Variance for a Finite Jobset
• Minimising Waiting Time Variance in the Single Machine Problem
• The cone of Monge matrices: Extremal rays and applications