2
$\begingroup$

I am working on a scheduler for a manufacturing plant. I have currently set it up so the decision variables are set up as binary variables:

$x_{m,p,s}$ = 1 if machine m is running part p on shift s

However, that is binary and so either the machine produces its maximum parts per shift that shift or none at all. It would be ideal for the scheduler to be able to produce a value in-between 0 and the maximum (for reasons of minimizing unnecessary inventory). I figure there are two ways to do it, and just am not sure which is better without trying both and would like to know if there is a standard way to formulate this.

Let $y_{m,p,s}$ - Number of parts to be made on machine m for part p at shift s, such that $0 \le y_{m,p,s} \le \text{PartsPerShift}_p$

OPTION 1:
Set $y_{m,p,s}$ as a continuous (or integer) variable with constraints based on $x_{m,p,s}$: \begin{align} y_{m,p,s} &\ge 0 \\ y_{m,p,s} &\le \text{PartsPerShift}_p x_{m,p,s} \end{align}

OPTION 2:
Set $x_{m,p,s}$ constraints based on $y_{m,p,s}$: \begin{align} x_{m,p,s} = 0 &\quad \text{if $y_{m,p,s} = 0$} \\ x_{m,p,s} = 1 &\quad \text{if $y_{m,p,s} > 0$} \end{align}

As far as I can tell, the benefit of having $x_{m,p,s}$ as a constraint based on $y_{m,p,s}$ is that there are fewer decision variables overall (half as many), however this would involve a large rework of the model as it stands.

Improve this question
$\endgroup$
5
  • $\begingroup$ It looks like both options have the same variables. Or in option 2 do you mean that you will calculate $x$ as a postprocessing step after the solver returns $y$? $\endgroup$
    – RobPratt
    Sep 10 at 0:40
  • $\begingroup$ What I mean is which formulation of constraints makes more sense, between the first option (including your answer's suggestion to have $y_{m,p,s}$ > $x_{m,p,s}$ ) such that $x$ is an unconstrained binary variable and $y$ is a continuous variable with constraints based on $x$, or have $y$ as a continuous variable with only an upper/lower bound and $x$ as being calculated based on $y$ using logical constraints during the model's runtime. $x$ needs to be calculated during solving as other variables (# workers, for e.x.) are calculated using it. $\endgroup$
    – Dano
    Sep 10 at 15:14
  • 1
    $\begingroup$ OK, so you are asking whether big-M constraints or indicator constraints are more efficient. The answer, as often in MILP, is that it depends. Worth trying both. In fact, some implementations of indicator constraints will automatically transform to big-M under the hood. $\endgroup$
    – RobPratt
    Sep 10 at 17:55
  • $\begingroup$ Fair enough. Thanks for parsing through my question - still learning through the technical phrases to use to explain what I mean. Marked your answer as correct. Do you have any recommended resources to read more about this? $\endgroup$
    – Dano
    Sep 10 at 19:08
  • 1
    $\begingroup$ Glad to help. I added the indicator-constraints tag, and looking at those questions might aid your understanding. $\endgroup$
    – RobPratt
    Sep 10 at 21:23

1 Answer 1

Reset to default
3
$\begingroup$

If you need both $x$ and $y$ in the model, a third option is to enforce \begin{align} y_{m,p,s} &\ge x_{m,p,s} \\ y_{m,p,s} &\le \text{PartsPerShift}_p x_{m,p,s} \end{align} This modification to option 1 yields the same behavior you described in option 2. Without this change, option 1 allows $x_{m,p,s}=1$ with $y_{m,p,s}=0$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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