2
$\begingroup$

I am working with a kind of a reconfigurable process planning, meaning that the same machine can have different configurations and perform multiple operations. Each machine has an initial configuration that can be changed according to the needs. The process plan has a given sequence, each machine $w$ can assume one position $j$ on the process plan.

My question is, how to create a constraint to ensure that if in the first occurrence of a given machine $w$ its configuration $c$ is different from its initial configuration $c_o$ there will be a cost of changing configuration?

I just need to ensure the cost of changing configuration between the first occurrence of a given machine in the process plan, because the change of configuration within the same machine between two consecutive process plan positions is stated by the binary variable presented below:

  • $Y_w{_c}_{c'j-1j}=1$ if a machine $w$ changes its configuration from $c$ to $c'$ between positions $j-1$ and $j$, 0 otherwise

I am also using the following binary variable:

  • $X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a configuration $c$ at process plan position $j$, 0 otherwise

and the parameter:

  • $IC_w{_c}_{O}=1$ if configuration $c$ is the initial configuration of machine $w$, 0 otherwise

Where:

$j$: process plan positions

$w$:machines

$c_w$: configuration $c$ of machine $w$

$p$: operations

Could someone help me?

$\endgroup$

2 Answers 2

4
$\begingroup$

I think you do need some variable that keeps track of the configuration a machine is in at a given process plan position. This could be a variable $C_{wcj}$ that is $1$ if machine $w$ is in configuration $c$ at process plan position $j$.

Then the following three constraints give you that:

  • Each machine is in exactly one configuration at each process plan position
  • The configuration of a machine stays the same unless we change the configuration
  • A process can only be run on a machine that has the correct configuration

$$ \begin{align} \sum_c C_{wcj} &= 1 & \forall w,j\\ C_{wcj} &= C_{wc(j-1)} + \sum_{c'}Y_{wc'c(j−1)j} - \sum_{c'}Y_{wcc'(j−1)j} &\forall w,c,j\\ X_{pwcj} &\leq C_{wcj} &\forall p,w,c,j \end{align} $$

In this setting you can naturally set the initial configuration of the machine by setting $C_{wc_w0} = IC_{wcO}$.

I hope I understood your problem correctly and this helps.

$\endgroup$
2
  • $\begingroup$ many thanks for your quick reply and for taking your time to help me. It worked exactly as I need ! :) $\endgroup$
    – campioni
    Dec 1, 2020 at 16:46
  • $\begingroup$ Just in case someone else is also interested in this model. To set the initial configuraion of machines, I added a constraint to force Cwo to be equal to the initial configuration IC when j==0. $\endgroup$
    – campioni
    Dec 1, 2020 at 16:47
1
$\begingroup$

Let binary variable $Z_w$ indicate whether the first occurrence of machine $w$ is different than its initial configuration. Here's a derivation of linear constraints via conjunctive normal form, without introducing any additional variables: $$ \bigvee_{c \not= c_0} \bigvee_j \left(\bigvee_p X_{p,w,c,j} \land \bigwedge_{k<j} \bigwedge_q \bigwedge_d \lnot X_{q,w,d,k}\right) \implies Z_w \\ \lnot \left[\bigvee_{c \not= c_0} \bigvee_j \left(\bigvee_p X_{p,w,c,j} \land \bigwedge_{k<j} \bigwedge_q \bigwedge_d \lnot X_{q,w,d,k}\right)\right] \lor Z_w \\ \left[\bigwedge_{c \not= c_0} \bigwedge_j \left(\bigwedge_p \lnot X_{p,w,c,j} \lor \bigvee_{k<j} \bigvee_q \bigvee_d X_{q,w,d,k}\right)\right] \lor Z_w \\ \left[\bigwedge_{c \not= c_0} \bigwedge_j \bigwedge_p \left(\lnot X_{p,w,c,j} \lor \bigvee_{k<j} \bigvee_q \bigvee_d X_{q,w,d,k}\right)\right] \lor Z_w \\ \bigwedge_{c \not= c_0} \bigwedge_j \bigwedge_p \left(\lnot X_{p,w,c,j} \lor \bigvee_{k<j} \bigvee_q \bigvee_d X_{q,w,d,k} \lor Z_w\right) \\ 1 - X_{p,w,c,j} + \sum_{k<j} \sum_q \sum_d X_{q,w,d,k} + Z_w \ge 1 \quad \text{for $c \not= c_0, j, p$} \\ X_{p,w,c,j} \le \sum_{k<j} \sum_q \sum_d X_{q,w,d,k} + Z_w \quad \text{for $c \not= c_0, j, p$} \\ $$

If each machine can have at most one configuration at a time, you can strengthen as follows: $$\sum_{c \not= c_0} X_{p,w,c,j} \le \sum_{k<j} \sum_q \sum_d X_{q,w,d,k} + Z_w \quad \text{for all $j, p$} $$

If each machine can also perform at most one operation at a time, you can further strengthen as follows: $$\sum_p \sum_{c \not= c_0} X_{p,w,c,j} \le \sum_{k<j} \sum_q \sum_d X_{q,w,d,k} + Z_w \quad \text{for all $j$}$$

An interpretation of the linear constraints is:

"If machine $w$ is in configuration $c\not= c_0$ at position $j$ then either it is in some configuration at an earlier position or the first occurrence is different than its initial configuration."

$\endgroup$
2
  • $\begingroup$ I tried what SimonT suggested me and it worked well for my problem. But thank you for taking your time to help me. $\endgroup$
    – campioni
    Dec 1, 2020 at 17:03
  • $\begingroup$ @campioni I updated my answer just now with explicit constraints. If my assumptions are correct, you need only one binary variable per machine and only one constraint per machine and position. $\endgroup$
    – RobPratt
    Dec 1, 2020 at 17:23

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.