Using Opensolver on MS Excel, I am trying to create a schedule for a factory. There are $n$ parts and $m$ machines. I modeled the schedule as a large binary decision matrix, where there is a binary variable determining if a specific part is being run on a specific machine. For example:
| M T W R F
_______________________
part 1 | 1 0 1 1 0
|
part 2 | 0 0 0 0 1
would indicate that, on this particular machine:
- part 1 is being run on Monday, Wednesday, and Thursday
- part 2 is being run on Friday.
There is a constraint that each part can only be run on one machine at a time, and each machine can only run one part at a time.
Whenever a machine goes from producing one part to producing a different part, i.e., the decision variables change from $0$ to $1$, the machine needs a "mould change". I need to keep track of those, because the factory can only have $k$ mould changes a day, so a schedule with more than $k$ mould changes a day is not admissible.
However, I am unable to think of a linear way to express this. And I really want to use a linear solver, since it is much faster and I can ensure the solution is a global minimum of my objective function (which is based on things such as if part $n$ is being run on its "preferred" machine, making sure no orders are late, and number of mould changes).
The best I have been able to come up with so far is (where i is index of which day it is): Number of Mould Changes for one day = $(N1_i - N1_{i-1})(N1_i)$. This is correct and it works, (if $1\to0$, then = 0, if $0\to1$, then $= 1$, if $0\to0$, then = 0, if $1\to1$, then $= 0)$, but the problem is it is not linear. Which is:
$$(\sum ((n_i - n_{i-1})*n_i)) \le k $$
For all n jobs in one day
In other words, I have 2 binary variables x,y, and I am summing all instances of $x^2 - xy$
Is there a way to make this linear, or just a different way of figuring this out that didn't occur to me? Or am I stuck with having to use non-linear analysis? The most important thing for me is that it works on a linear solver, preferably on Excel but I can learn something else if necessary. If I have to change the entire way this is set up in order to make it linear, I am 100% fine with that.
Here is standard way of formulating the start of a run. Let $x_{i,t} \in \{0,1\}$ indicate when part $i$ is produced. Then introduce another binary variable $y_{i,t} \in \{0,1\}$ indicating a start of a run. Then we can say:
$$ \begin{align} &y_{i,t} \ge x_{i,t}-x_{i,t-1} & & \text{start of run: mold change}\\ &\sum_{i} y_{i,t} \le k \>\> \forall t && \text{limit daily mold changes} \end{align} $$