# Facility Layout Problem with Alternative Facility Variants
## 3 Preliminaries  
The main feature of the original method introduced in [32] is that the evolutionary algorithms (see the pseudocode in Appendix A) use an indirect representation. This means that the layout of the floor plan, i.e., the exact position and rotation of the workstations, is not directly encoded into the solution representation. Instead, the solution is represented using a so-called _priority list_, which encodes the order in which the workstations will be added to the floor plan using placement heuristics designed for the problem. The priority list is thus a sequence of tuples  
\[t_{j}=(\texttt{id},\texttt{orientation},\texttt{heuristic}),\]  
where each tuple at the position \(j=1\ldots N\) in the priority list specifies which workstation (id) with what orientation (orientation) will be added to the floor plan using what placement heuristic (heuristic). Mapping from the priority list to the floor plan is accomplished through an iterative process. It starts with an empty floor plan. Then, the priority list is traversed from left to right, and the workstations are successively added one by one to the developed floor plan according to the 'instructions' given in the corresponding tuple. The mapping process is illustrated in Figure 2. For more details, refer to [32]. An important aspect of this representation is its redundancy. On the one hand, each priority list maps to exactly one floor plan. On the other hand, multiple different priority lists can potentially map to the same floor plan. This is an important feature, as it allows for converging to an optimal solution via different search trajectories. In [32], a single crossover and several mutation operators were used. The crossover operator is a variant of a standard order-based crossover operator [36]. It takes for its input two parental priority lists and starts generating the offspring by randomly choosing two crossover points. Standard tournament selection is used to select the parents. Then, the head and tail parts are inherited from the first parent. The middle part is filled in with the missing elements in the same order in which they appear in the second parent. The crossover points delimiting the head, middle, and tail parts are found randomly anew for each crossover operation. In the following, we denote this operator as a _2-point crossover_. We also implement a simple _1-point crossover_ operator. It generates the offspring by inheriting a randomly-chosen head part from the first parent and then appending missing elements in the same order in which they appear in the second parent. Figure 1: An example of (**a**) the production hall geometry and (**b**) three alternative variants of the same workstation. The mutation operators operate on a single priority list. They are designed to modify a randomly-chosen element of the parental priority list so that it changes either its position within the priority list or the way the corresponding workstation is added to the floor plan, i.e., its orientation or heuristic. In the original work, two optimization criteria, maxFreeSpace and minConnDist, were defined. The first one maximizes the compactness of the floor plan, defined as the maximization of the free space remaining between the lower horizon of the placed workstations and the bottom edge of the hall. This objective ensures that among the maximally-compact floor plans, the ones with the remaining space concentrated towards the bottom edge of the hall are preferred. As its name suggests, this objective drives the optimization towards floor plans that have the greatest potential for placing new workstations. This objective exhibits desired properties, as it drives the search towards maximally-compact floor plans and simultaneously maximizes the utilization of the available area. Contrary to traditional variants of FLP space occupation-related objectives that try to pack the entities within the smallest rectangular envelope, our maxFreeSpace objective better optimizes for space utilization.