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

DOI10.1016/j.orl.2012.06.005zbMath1250.90045OpenAlexW2096919221MaRDI 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 schedulingcombinatorial optimizationquadratic assignment problemwell-solvable special case

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Linearizable special cases of the QAP, A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems, Robinsonian matrices: recognition challenges, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, An LP-based characterization of solvable QAP instances with chess-board and graded structures, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, A New Tractable Case of the QAP with a Robinson Matrix, 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

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