Project # 1

Assignment

The goal of the project is the implementation of a solution to the facility layout problem (Single-Row Facility Layout Problem, SRFLP).

Problem description. SRFLP consists of finding a linear arrangement of a set of devices that will minimize the (weighted) sum of the distances between every two devices. As an illustration, we can imagine a robotic arm that takes products from four locations (e.g. belts), as shown in Fig. 1. However, each belt delivers products with different intensity. If the belts on which the products appear are often located far from each other (in the picture, e.g. m1, m4), the use of the robot will be inefficient (it will often move along a long path between m1 and m4). In addition, the width of the belts can be different.

Obrázek 1: SRFLP example

Mathematically, the basic version of SRFLP can be formulated as follows: let us have a set of devices, \(F= \{1, 2, ..., n\}\) with a known width, \(\vec L = (l_1, l_2, ..., l_n)\). Next, let's have a matrix \(C = \{c_{ij}\} \in \mathbb{R}^{n\times n}\) with weights of transitions between facilities \(i\) and \(j\). We can think of this as an estimate of the probability that the arm (in the figure) will move from location \(i\) to location \(j\).

The goal of solving SRFLP is to find a linear arrangement (=permutation) of facilities, \(\pi = (\pi_1, \pi_2,\ldots \pi_n)\), which will minimize the following cost function: \[\min_{\pi\in\mathcal{S}_n} f_{\mathrm{SRFLP}}(\pi),\] \[f_{\mathrm{SRFLP}}(\pi) = \sum\limits_{1 \leq i < j\leq n}\left[c_{\pi_i\pi_j} \cdot d(\pi_i,\pi_j)\right],\] \[d(\pi_i,\pi_j) = \frac{l_{\pi_i} + l_{\pi_j}}{2} + \sum\limits_{i\le k\le j} l_{\pi_k}.\] The specific problem we want to solve (an SRFLP instance) can be described, for example, as follows:

Figure 2: a SRFLP instance

10
1 1 1 1 1 1 1 1 1 1
0 30 17 11 24 25 24 17 16 22
0 0 21 23 26 24 27 19 11 32
0 0 0 24 18 23 31 36 28 19
0 0 0 0 19 18 33 25 20 28
0 0 0 0 0 15 37 27 17 16
0 0 0 0 0 0 27 23 29 24
0 0 0 0 0 0 0 27 31 24
0 0 0 0 0 0 0 0 14 18
0 0 0 0 0 0 0 0 0 24
0 0 0 0 0 0 0 0 0 0
The meaning of the lines in Fig. 2 is as follows: line (1) contains the dimension of the problem, i.e. the number of devices (\(n\)). Row (2) contains facility widths, \(l_1, l_2, ..., l_n\). In this instance, all devices have the same width, 1. Lines (3) - (12) then contain the matrix \(C\), i.e. the weights of transitions between locations, \(c_{ij}\). he lower part of the matrix is ​​filled with zeros, since the problem is symmetric, \(c_{ij} = c_{ji}\), let's imagine the same values ​​there as above the main diagonal. Based on all this, we can formulate the following assignment of the task.

Assignment. Implement a SRFLP solution (for problem instance Y-10_t.txt) using brute-force and branch-and-bound (backtracking) methods.

References

  1. Kothari, R., Ghosh, D. The single row facility layout problem: state of the art. OPSEARCH 49, 442–462 (2012). https://doi.org/10.1007/s12597-012-0091-4