Scheduling of process manufacturing with setup times

Question

Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

Problem Formulation

The problem consists of

• Sequence of consecutive time intervals $t\in\{1,\dots,n_t\}$, each with start and end $(s_t,e_t)$ and length $l_t=e_t-s_t$. Consecutive means $e_{t}=s_{t+1}$ for all $t\in\{1,\dots,n_t-1\}$.
• List of type of goods that are being produced: $j\in \{1,...,n_j\}$
• Demand of each type of good per time interval $d_{j,t}$.
• List of production lines $i\in{1,\dots,n_i}$
• Availability of production lines per time interval $a_{i,t}$. $a_{i,t}$ is binary - whether available or not.
• Manufacturing speed per production line per type goods $v_{i,j}$.
• Setup time from one type of goods to another one $u_{j,j'}$.
• Price for using a production line (leasing based), counted per minute $c_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

• The setup time can be shorter or longer or equal to the length of the intervals
• It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
• The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

Example

There are two production lines, i.e., $n_i = 2$ and there are two types of goods, i.e. $n_j=2$.

We have two intervals, i.e. $n_t=2$, each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

• $d_{1,1}=1.1$
• $d_{1,2}=1$
• $d_{2,1}=1$
• $d_{2,2}=0.5$

The of running the production lines are:

• $c_{1} =c_{2} = 1$ USD/minute

All possible setup times are 30 minutes, i.e.:

• $u_{j,j'}=0.5$ for all $j,j'$ where $j\neq j'$.

The speeds are:

• $v_{1,1}=1.1$
• $v_{1,2}=1.5$
• $v_{2,1}=1$
• $v_{2,2}=1$

Obviously, the demand is met if the first line is producing the first type of goods at both intervals and the second line is producing the second type. The cost is 204.55. See the solution here:

However, it might be tempting to switch them. Line 1 is much more efficient for the second type of goods (1.5). If there would be no setup time, we would have the cost 180 USD. However, this is not possible.

Question

What is the algorithm to schedule this manufacturing process optimally?

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,...).

Ideas fo far

• If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
• An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).

Answer 1

We use the index $k$ for time such that $k \in [s_1, e_{n_t}]$

We introduce the following variables:

$\ell^{i,k}$ - line $i$ is leased at line $k$

$\alpha^{i,k}_{j,j'}$ - binary indicator for line $i$ is switching from $j$ to $j'$ at time $k$.

$p^{i,k}_j$ - binary indicator for line $i$ is producing good $j$ at time $k$.

$h^{i,j}_j$ - binary indicator that line $i$ is waiting to produce good $j$ at time $k$

$g^{i,k}_j$ - generated amount for line $i$ for good $j$ at time $k$ (either $v_{i,j}$ or $0$)

Then goal is to minimize $\sum_{i,k} c_i \ell^{i,k}$ subject to constraints:

Constraints for every $i,k$:

• can only switch to 1 good at a time: $\textrm{at-most-1} \alpha^{i,k}_{j,j'}$
• can only make 1 good at a time: $\textrm{at-most-1} p^{i,k}_j$
• can only hold for 1 good at a time: $\textrm{at-most-1} h^{i,k}_j$
• if producing, not switching: $\bigvee_j p^{i,k}_j \rightarrow \neg \bigwedge_{j,j'} \alpha^{i,k}_{j,j'}$
• leasing iff producing or switching: $\ell^{i,k} \leftrightarrow \bigvee_{j,j'} \alpha^{i,k}_{j,j'} \vee \bigvee_j p^{i,k}_j$
• not leasing implies holding for some good: $ \neg \ell^{i,k} \Rightarrow \bigvee_j h^{i,k}_j$

Constaints for every $i,k,j$:

• Generating only if producing: $$p^{i,k}_j \rightarrow g^{i,k}_j = v_{i,j}$$ $$\neg p^{i,k}_j \rightarrow g^{i,k}_j = 0$$
• when stopping producing, it must immediately hold for same good or switch to another good (for $k < e_{n_t}$): $p^{i,k}_j \wedge \neg p^{i,k+1}_j \Rightarrow h^{i,k+1}_j \vee \bigvee_{j'} \alpha^{i,k+1}_{j,j'}$
• if producing or holding at $k+1$ must have been producing, holding, or switching at $k < e_{n_t}$: $p^{i,k+1}_j \vee h^{i,k+1}_j \Rightarrow p^{i,k}_j \vee h^{i,k}_j \vee \bigvee_{j'} \alpha^{i,k}_{j',j}$

Constraints for every $i,k < e_{n_t},j,j'$:

• when switching, it must switch long enough: $(p^{i,k}_j \vee h^{i,k}_j) \wedge \alpha^{i,k+1}_{j,j'} \Rightarrow \bigwedge_{k'=k+2}^{\min(k+u_{j,j'}, e_{n,t})} \alpha^{i,k'}_{j,j'}$

Constraints for every $d_{j,t}$:

• $\sum_{k=s_t}^{e_t} \sum_i g^{i,k}_j \geq d_{j,t}$