2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Thank you so much! This works perfectly :) Is there any place which has a list of such kinds of tricks? Or a particularly useful and practical Linear Programming textbook that I could read? $\endgroup$ – Daniel P Jun 22 '17 at 14:15
  • $\begingroup$ Not sure if this formulation is discussed, but a good book is H.P.Williams, "Model buidling in Mathematical Programming", Wiley. $\endgroup$ – Erwin Kalvelagen Jun 22 '17 at 18:23
  • $\begingroup$ Thanks, I'll check it out. Also, since this is a MILP, will the solution it finds be the global optimal? If not, is there a way to run it a few times to at least get a couple of locally optimal solutions? $\endgroup$ – Daniel P Jun 22 '17 at 19:44
  • $\begingroup$ MIP finds global optimal solutions (unless you stop it prematurely, eg on a time or iteration limit or on an allowed gap). $\endgroup$ – Erwin Kalvelagen Jun 23 '17 at 0:16
  • $\begingroup$ I have run into a problem. This method is able to capture mold changes whenever a machine goes from not running a particular part to running it (e.g. going from running part B to part A, or going from running nothing to Part A). However, there are times when we run a part one day, don't run it the next day, then run it the third day. (For example, we try to not run on Saturday as often as possible). Since we leave the molds inside the machine when the machine is not in use, this is not a mold change. However, it is counted as one using this method. Do you have any suggestions? Thanks. $\endgroup$ – Daniel P Jul 27 '17 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.