Optimization Online


A Semidefinite Optimization Approach to the Parallel Row Ordering Problem

Philipp Hungerlaender (philipp.hungerlaender***at***aau.at)

Abstract: 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.

Keywords: Facilities planning and design; Flexible manufacturing systems; Semidefinite Programming; Global Optimization

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Category 3: Applications -- Science and Engineering (VLSI layout )

Citation: Technical Report, Alpen-Adria-Universitaet Klagenfurt

Download: [PDF]

Entry Submitted: 09/15/2014
Entry Accepted: 09/16/2014
Entry Last Modified: 03/17/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society