hope you are doing fine.
I am facing some mathematical problem which I am not certain of which type is it, nor how to approach its solution. Here is a picture with a representation (simplify) of the problem:
What it this about:
I have $N$ factories represented as:
$$factory = \{F_1,F_2,F_3,\dots,F_N\}$$
Some of them are colored green, and some are blue. A factory can have a maximum of $1$ machine. There are even a few that don't have any machine at all. In this universe, there are only $M$ type of machines, say: $$machines=\{T_1,T_2,T_3,\dots,T_M\}$$
Every factory $F_i$ with a machine $T_j$ is producing some amount of money $X_{ij}$ per unit of time. That is: $$P\big(F_i(T_j)\big)=X_{ij},\;\;\;i\in[1,n],\;\;\;j\in[1,M].$$
Note that factories only work with two possible machine types. That is, they are restricted to the type that is currently in use and the one detailed in the request. Not all combinations are possible.
Now, in the picture, some factories are colored green and some others are colored blue. The green ones have submitted a request for a machine replacement. This type of request always assumes the change will increase the productivity of the factory (say, from $20$usd to $50$usd per unit of time). Moving a machine from factory $j$ to factory $k$ will have a cost of: $$C(F_j,F_k)=Z_{j,k},\;\;\;i,j\in[1,n].$$
Elements of the problem:
- Optimally all requests have to be fulfilled (but not required).
- Machines going to a green factory can come from both blue and green factories.
- Changing a machine in a green factory implies that the old machine is available for the remaining requests.
The problem:
- I need to find wich is the best way to rearrange the machines in order to maximize my gain, where gain is a cost function $G$ repesented by (function in progres): $$G=\sum_{l,p}\bigg[P\big(F_l(T_p)\big)-P\big(F_l(T_l)\big)\bigg] - \sum_{l,p}C(F_l,F_p)$$ where the term $P\big(F_l(T_p)\big)$ represents the new production (with the change) and $P\big(F_l(T_l)\big)$ is the old production of each factory $l$ and $p$ involved in the movings.
The image is showing some possible movements (but not all) and certainly, not the best. So the problem would be: which are the best arrows...
1- Is this a Bin packing Problem? If so, which variation of the problem?. From my understanding, That kind of problem involves maximizing the number of objects inside a fixed size. Maybe this problem is something like maximizing the gain (instead of a fixed size) where the objects are the machines. Is this reasonable?
2- If not, which type of problem it is?
Thanks in advance!
You can formulate this as a linear assignment problem, equivalently, a maximum-weighted matching problem in a bipartite graph. There is one left node for each factory that has an old machine, and there is one right node for each factory that requests a new machine. There is a directed arc from left node $\ell$ to right node $p$ if the old machine at factory $\ell$ is eligible to be moved to factory $p$, with weight $P(F_l(T_p))-P(F_l(T_l)) - C(F_l,F_p)$. These arcs include zero-weight arcs from left $\ell$ to right $\ell$ that correspond to factory $\ell$ keeping its old machine. Each left node uses exactly one outgoing arc, and each right node uses at most one incoming arc. You can use a linear assignment solver, a network flow solver, or a linear programming solver.