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

作者：Cela Eranda^*; Deineko Vladimir G; Woeginger Gerhard J

来源：Operations Research Letters, 2012, 40(5): 356-359.

DOI：10.1016/j.orl.2012.06.005

• Combinatorial optimization
• Quadratic assignment problem
• Machine scheduling
• Well-solvable special case

We analyze a special case of the maximum quadratic assignment problem where one matrix is a monotone anti-Monge matrix and the other matrix has a multi-layered structure that is built on top of certain Toeplitz matrices. To demonstrate an application of our main result, we derive a (simple and concise) alternative proof for a recent result on the scheduling problem of maximizing the variance of job completion times.

• 出版日期2012-9