Problem description

General introduction

On this page we present an introduction to the problem this solver is expected to solve. Namely, we consider a variation of the well-known Facility Layout Problem with the following specificities.

We assume that we are given some production process that involves some objects following a certain pipeline in a given facility. We view the entire process within the facility as a sequence of interactions between subjects of production (machines, departments, etc.) and objects of production (tyres, patients, documents, etc.).

Each subject is placed into one of the predefined points that collectively form a facility and occupies a certain area in this point. Each subject also has its input capacity (a number of objects it can accept in total from other subjects within one time unit), and output capacity (a number of objects it can distribute in total among other subjects within one time unit). Each subject belongs to one and only one of non-intersecting groups. All subjects within one group share the same respective values of area occupied by a single subject, input and output capacities, and are mutually interchangeable in a production pipeline.

Originally, we know the total flow between any two subject groups with the help of which we can identify the necessary number of subjects in each group. Flow preservation constraints (a.k.a. Kirchhoff constraints) are, in general, not expected to be met: subjects can produce and destroy objects when necessary. Despite this, we will abuse the notation further and call all weights of a production pipeline ‘flows’. Even though this might be seemed irrelevant and unrealistic as flow preservation constraints are usually met in reality, this formality helps us easily model sources (subject groups from which the production process begins, they have no incoming flows and ‘generate’ all distributed objects) and sinks (subject groups at which the production process ends, they have no outcoming flows and ‘destroy’ all accepted objects).

Quick example

Suppose, there is subject group $\text{raw wood supply}$ with output capacity $500$ and subject group $\text{table saw}$ with input capacity $150$. We assume that $400$ units of wood is supplied to $\text{raw wood supply}$ from outside the facility (i.e. this group is a source) and all of them must be then delivered to $\text{table saw}$ subjects. We know that the output capacity of a single $\text{raw wood supply}$ is $500$ meaning that it suffices to install a single subject from this group into a facility to be able to distribute all the wood. At the same time, the input capacity of a single $\text{table saw}$ is $150$ and one $\text{table saw}$ will not be able to process all the wood on its own. Hence, we will need $\lceil 400/150 \rceil = \lceil 2.(6) \rceil = 3$ subjects from group $\text{table saw}$ to accept all the raw material. This is exactly how the solver computes the number of subjects to place in the facility.

We agree that we cannot put a set of subjects into a point if their cumulative area exceeds the area of this point.

The final goal is to find an optimal arrangement of all the subjects within the facility which means the following:

• each subject from each group is assigned with a specific point of the facility where it must be located,
• each couple of subjects is assigned with a flow of objects between them.

Résumé

An instance of the problem is, then, defined by three components:

1. Facility made of points each of which is characterised by:
   • its 2D coordinates (two real numbers),
   • its area (non-negative integer).
2. Subject groups each of which is characterised by:
   • its input capacity (positive integer),
   • its output capacity (positive integer),
   • its area (non-negative integer).
3. Total flows between each pair of subject groups (positive integers).