Conference Agenda

In the directed circular facility layout problem (DCFLP) one has given a set of departments, their lengths and pairwise weights between the departments. In contrast to the single row facility layout problem (SRFLP), where departments are arranged along one side of a path without overlapping, the DCFLP looks for an arrangement on a circle such that the sum of the weighted center-to-center distances measured in clockwise direction is minimized.

In this talk, we present a new facility layout problem, the undirected circular facility layout problem (UDCFLP). For each pair of departments we consider here the shortest distance along the circle, either travelling in clockwise or in counter-clockwise direction.

We present two new mixed-integer linear programming models for the UDCFLP, whereby one model is an adaptation of a well-known model for the DCFLP and the other model is based on the well-known betweenness model for the SRFLP. We develop symmetry-breaking constraints and study the structure of the associated polytopes. Our models, which are strengthened by our new cutting planes, allow us to solve instances with up to 13 departments to optimality within a time limit of one hour. For larger instances we derive strong lower bounds exploiting the connections to some parallel machine scheduling problem.

Given a set of departments, their lengths and pairwise weights the single-row facility layout problem (SRFLP) asks for an arrangement of the departments along one side of a path such that the weighted sum of the center-to-center distances is minimized. In the constrained SRFLP certain ordering and positioning conditions have to be satisfied. We present some new constraints for strengthening the betweenness approach presented by Maier and Taferner. Optimal solutions or strong lower bounds are derived using a cutting plane approach where the linear programs are solved using an interior point method.

Apart from this we show that the so called weighted linear ordering problem, which leads to asymmetric betweenness variables, can be handled as well by our approach by a transformation to the standard betweenness model. This allows us to solve some previously unsolved instances rather fast.

We present novel binary linear programs to model betweenness relations, and reveal favorable structural results as well as handy relations to the (linearized) quadratic linear ordering problem. The findings can be exploited to obtain compact and strong relaxations for dense as well as sparse application settings.