# Facility Layout Problem with Alternative Facility Variants
## 1 Introduction  
The facility layout problem (FLP) is one of the most important problems in production management and industrial engineering. It is a nonlinear combinatorial optimization problem defined as finding the most efficient arrangement of non-overlapping facilities on the factory floor with respect to one or more objectives subject to various constraints. Typically, the optimization goals are to maximize the utilization of the area available, minimize material-handling costs, or fulfill the adjacency or distance requirements between facilities. Furthermore, various constraints are imposed on the solution sought, such as the total area available, maximum acquisition or material handling costs, maximum maintenance costs, and other indirect expenses limits. The problem of finding the optimal layout of a set of elements occurs at various levels of a complex manufacturing environment, e.g., when arranging machines in a workshop, production lines in a production hall, or buildings on factory premises [1; 2; 3]. The FLP is a challenging task that has a direct impact on production efficiency, as it directly affects manufacturing costs, work in process, lead times, and productivity. A good layout of facilities contributes to the overall efficiency of operations and can reduce total operating costs by 20% to 50% [1]. Additionally, it has been shown that more than 35% of system efficiency is likely to be lost by applying incorrect layouts and location designs [4]. Numerous variants of the FLP problem have been formulated and researched. They can be categorized by different aspects as static or dynamic FLP, single- or multi-objective FLP [5], single- or multi-floor FLP, or FLP with equal or unequal facility areas, etc. [6; 7; 8; 9]. When considering facility characteristics, several factors and design issues are addressed in the literature, such as the production variety and volume, the facility shapes and dimensions, the material handling system chosen, and different possible movement types allowed for parts, to name a few. Regarding the shapes and dimensions, there are two types of facilities: facilities with regular rectangular shapes and those with irregular shapes, i.e., generally polygons. In the former case, a facility can be defined by fixed length and width, and this facility is called fixed or rigid block [10]. An important FLP variant with numerous practical uses is the FLP with loosely-defined facility shapes and dimensions. In that case, each facility is associated with its area and a shape constraint, e.g., the maximum aspect ratio allowed (quotient between greater and lesser side measurements) or the minimum side length. Layout problems are known to be generally NP-hard, which means that no exact algorithm exists that can provide an optimal solution in a reasonable polynomial time. On the one hand, there are many works in the literature that successfully use mathematical programming approaches to solve particular FLP variants. For instance, discrete quadratic assignment problem models were used for FLP with regular-shape equal-area facilities [11; 12], and continuous linear and non-linear mixed integer programming models were used for FLP with irregularly-shaped facilities of unequal areas [13; 14; 15; 16; 17]. On the other hand, these approaches are applicable only to a rather small number of FLP instances, typically a few dozen facilities at most. Thus, many recent developments in solving the FLP are based on iterative metaheuristic approaches such as Tabu Search [18], Ant System [19; 20], Particle Swarm Optimization [21], Variable Neighborhood Search [22], Simulated Annealing [23], and Evolutionary Algorithms [24; 25; 26; 27; 28; 29; 30; 31]. We build on our previous work [32] that considers the FLP with workstations to be optimally placed into a production hall. A realistic definition of the hall and workstations was introduced there.