I have a Mixed Integer Linear Problem where I want to schedule the production of different orders ($O$) in which in each order, there is only one product ($P$) produced.
Each order can be produced once at a time, and between two orders, there is a certain time that has to be scheduled for cleaning the production line. The time depends on which product was produced before, and which product will be produced after. E.g.: if I produce green apple juice and then red apple juice, the cleaning time is set to 20 minutes. However, if grapes juice is produced after green apple juice the time increases to 35 minutes.
I am modeling the production considering the following variables:
$X_{o, d, h}$ is a binary variable that equals to 1 if the order o is produced in the day d at the hour h, and 0 otherwise.
$c_{d, h}$ is a binary variable that equals to 1 if the line is being cleaned in the day $d$ at the hour $h$, and 0 otherwise.
$y_{d, h}$ is a binary variable that equals to 1 if the line not being used (no production nor cleaning) in the day $d$ at the hour $h$, and 0 otherwise.
I also have a matrix $C$ that has the cleaning times between each pair of products. We can also asume to have $C$ for the time to clean between orders, as it is a simple transformation.
I want to create the constraints for the cleaning part. If any order is produced, then cleaning must happen (without stops) for the time specified in matrix $C$, which depends on which product/order that was produced before, and which product/order was produced after.
I got to formulate the mandatory start of cleaning by adding these constraints:
$$c_{d,h} \geq x_{o,d,h-1} - x_{o,d,h}$$ $$x_{o,d,h} + c_{d,h} + y_{d,h} = 1$$
However, this just makes one block of cleaning, and there have to be as many blocks as refered to matrix $C$, which depends on which product was produced before and which product is produced after. Any ideas on how to tackle this?
You can model this as an asymmetric traveling salesman problem (ATSP) with a dummy depot node, a node for each order, and $C$ as the arc cost matrix. Arcs to and from the depot have zero cost. See https://communities.sas.com/t5/Mathematical-Optimization/Job-Shop-Scheduling-Problem/m-p/783190
For a compact MILP formulation, search for Miller-Tucker-Zemlin (MTZ).