Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
Combinatorial optimization meets facility layout problems, als mathkol
Termin
20.06.2022, 16:30 Uhr -
Veranstaltungsort
Mathematikgebäude, Hörsaal E28
Abstract
Given a set of departments and the pairwise transport weights between them, the Single-Row Facility Layout Problem (SRFLP) asks for an arrangement of the departments on one side of a path such that the weighted sum of the distances between the departments is minimized. The best integer linear programming approach for the SRFLP is based on the betweenness model (Amaral, 2009).
In this talk we present new classes of inequalities for the associated betweenness polytope and show their validity using combinatorial arguments. Using a cutting plane approach allows us to solve more and larger instances of the SRFLP to optimality than the lower bounding approach of Amaral. In the second part of the talk we consider the Multi-Bay Facility Layout Problem and Facility Layouts with Pier Type Patterns which are special Combined Cell Layout Problems (CCLP). Here the path structure is more complicated. We solve these problems exactly by enumerating over all assignments of the departments to the cells and solving several CCLP with fixed-cell assignment using the betweenness model in each of the subproblems. We show how to reduce the number of distinguishable cell assignments significantly by merging two cells of type single-row.
In this talk we present new classes of inequalities for the associated betweenness polytope and show their validity using combinatorial arguments. Using a cutting plane approach allows us to solve more and larger instances of the SRFLP to optimality than the lower bounding approach of Amaral. In the second part of the talk we consider the Multi-Bay Facility Layout Problem and Facility Layouts with Pier Type Patterns which are special Combined Cell Layout Problems (CCLP). Here the path structure is more complicated. We solve these problems exactly by enumerating over all assignments of the departments to the cells and solving several CCLP with fixed-cell assignment using the betweenness model in each of the subproblems. We show how to reduce the number of distinguishable cell assignments significantly by merging two cells of type single-row.
Hinweis
vorab Institutstee / -kaffee um 16.00 Uhr im Besprechungsraum M614/616
Vortragende(r)
Prof. Dr. Anja Fischer
Herkunft der/des Vortragenden
Fakultät Wirtschaftswissenschaften, TU Dortmund