Constraint to handle the machine-configuration's change between initial position and its first occurrence in the process

Question

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?

Answer 1

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.

Answer 2

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."