A Semidefinite Optimization Approach to the Parallel Row Ordering Problem

The $k$-Parallel Row Ordering Problem (kPROP) is an extension of the Single-Row Facility Layout Problem (SRFLP) that considers arrangements of the departments along more than one row. We propose an exact algorithm for the kPROP that extends the semidefinite programming approach for the SRFLP by modelling inter-row distances as products of ordering variables. For k=2 rows, our algorithm is a good complement to a mixed integer programming (MIP) formulation that was proposed by Amaral [A parallel ordering problem in facilities layout. Computers & Operations Research, 2013.] very recently. The MIP approach allows to solve instances with up to 23 departments to optimality within a few days of computing time while our semidefinite programming approach yields tight global bounds for instances of the same size within a few minutes on a similar machine. Additionally our algorithm is able to produce reasonable global bounds for instances with up to 100 departments. We show that our approach is also applicable for k >= 3 rows and even yields better computational results for a larger number of rows.

Citation

Technical Report, Alpen-Adria-Universitaet Klagenfurt

Article

Download

View A Semidefinite Optimization Approach to the Parallel Row Ordering Problem