Problem definition

The sections below detai lthe “complete” problem. Other problem variants are the “basic” and “minimized hold time” variants, which are discussed afterwards.

Given

_images/explanatory.svg

Data on buffers e.g.

indices names volumes use start times use_durations
n \hbox{--} U_{n} t_{\mathit{USE},n}^{*} \Delta t_{\mathit{USE},n}
0 Buffer #1 5825.23 62.86 39.16
1 Buffer #2 10214.75 79.63 25.5
2 Buffer #3 13995.95 17.6 61.7
3 Buffer #4 14619.52 74.28 44.19
4 Buffer #5 4504.94 29.73 36.0
5 Buffer #6 16361.95 5.5 38.78
6 Buffer #7 3464.09 38.25 57.93
7 Buffer #8 13387.42 11.35 36.55
8 Buffer #9 1064.93 61.21 45.84
9 Buffer #10 1654.58 34.88 22.03
10 Buffer #11 23631.53 26.26 37.99
11 Buffer #12 11546.57 94.15 56.41

Data on available vessels

indices names volumes costs
m \hbox{--} V_{m} c_{m}
0 1000 L 1000.0 63.10
1 2000 L 2000.0 95.64
2 3000 L 3000.0 121.98
3 4000 L 4000.0 144.96
4 5000 L 5000.0 165.72
5 6000 L 6000.0 184.88
6 8000 L 8000.0 219.71
7 10000 L 10000.0 251.19
8 12000 L 12000.0 280.23
9 16000 L 16000.0 333.02
10 18000 L 18000.0 357.41
11 20000 L 20000.0 380.73
12 22000 L 22000.0 403.14
13 25000 L 25000.0 435.28
14 30000 L 30000.0 485.59

And some additional parameters:

parameter symbol value
process cycle time (h) T 96.0
prep pre duration (h) \Delta t_{\mathit{PREP,PRE}} 12.0
prep post duration (h) \Delta t_{\mathit{PREP,POST}} 1.5
transfer duration (h) \Delta t_{\mathit{TRANSFER}} 2.0
hold pre duration (h) \Delta t_{\mathit{HOLD,PRE}} 8.0
hold post duration (h) \Delta t_{\mathit{HOLD,POST}} 1.5
minimum hold duration (h) \Delta t_{\mathit{HOLD,MIN}} 12.0
maximum hold duration (h) \Delta t_{\mathit{HOLD,MAX}} 60.0
vessel minimum fill ratio f_{\mathit{MINUSE}} 0.3
maximum prep utilization f_{\mathit{MAXUSE}} 0.8
max slots P 5

Support formulae:

m \in \mathcal{M}; \quad \mathcal{M} = \left\{ 0, 1, 2, \ldots, m, \ldots, \left( M - 1 \right) \right\}

n \in \mathcal{N}; \quad \mathcal{N} = \left\{ 0, 1, 2, \ldots, n, \ldots, \left( N - 1 \right) \right\}

p \in \mathcal{P}; \quad \mathcal{P} = \left\{ 0, 1, 2, \ldots, p, \ldots, \left( P - 1 \right) \right\}

M = |\mathcal{M}|

N = |\mathcal{N}|

P = |\mathcal{P}|

t_{\mathit{USE},n} = t_{\mathit{USE},n}^{*} \enspace \text{mod} \enspace T \quad \forall n \in \mathcal{N}

V_{\mathit{MAX}} = \text{max} \left( V_{m} \enspace \forall m \in \mathcal{M} \right)

\Delta t_{\mathit{PREP}} = \Delta t_{\mathit{PREP,PRE}} + \Delta t_{\mathit{TRANSFER}} + \Delta t_{\mathit{PREP,POST}}

Minimize

The total (relative) cost of buffer preparation vessels

\boldsymbol{Z} = \sum_{m \in \mathcal{M}} \sum_{p \in \mathcal{P}} c_m \boldsymbol{y}_{mp}

Subject to

Each buffer must be prepared in a defined slot

\sum_{p \in \mathcal{P}} \boldsymbol{x}_{np} = 1 \quad \forall n \in \mathcal{N}

Each slot may contain at most one vessel

\sum_{m \in \mathcal{M}} \boldsymbol{y}_{mp} \le 1 \quad \forall p \in \mathcal{P}

Each vessel must be sufficiently large to prepare allocated buffers

U_{n} \boldsymbol{x}_{np} - \sum_{m \in \mathcal{M}} V_{m} \boldsymbol{y}_{mp} \le 0 \quad \forall n \in \mathcal{N}, \enspace \forall p \in \mathcal{P}

Each vessel must be sufficiently small to prepare allcoated buffers

V_{\mathit{MAX}} \boldsymbol{x}_{np} + f_{\mathit{MINFILL}} \sum_{m \in \mathcal{M}} V_{m} \boldsymbol{y}_{mp} \le U_{n} + V_{\mathit{MAX}} \quad \forall n \in \mathcal{N}, \enspace \forall p \in \mathcal{P}

Each preapration vessel must have a utilization below the maximum utilization limit

\Delta t_{\mathit{PREP}} \sum_{n \in \mathcal{N}} \boldsymbol{x}_{np} \le f_{\mathit{UTIL}} T \quad \forall p \in \mathcal{P}

The total duration in each hold vessel must be less than the cycle time

\begin{aligned} \boldsymbol{z}_{n} \le T - \Delta t_{\mathit{HOLD,PRE}} - \Delta t_{\mathit{TRANSFER}} - \Delta t_{\mathit{USE},n} - \Delta t_{\mathit{HOLD,POST}}\\ \quad \forall n \in \mathcal{N} \end{aligned}

Buffer preparation procedures mustn’t clash with one another

\begin{split} \begin{alignedat}{11} 2&\boldsymbol{w}_{nkp} {}-{} &&\boldsymbol{x}_{np} {}-{} && \boldsymbol{x}_{kp} {}&&\le{} &{}-{} 2\\ &\boldsymbol{w}_{nkp} {}-{} &&\boldsymbol{x}_{np} {}-{} && \boldsymbol{x}_{kp} {}&&\ge{} &{}-{} 1\\ \end{alignedat} \end{split} \quad \begin{split} \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n, \enspace \forall p \in \mathcal{P} \end{split}

\begin{split} \begin{alignedat}{2} T \boldsymbol{q}_{n} - \boldsymbol{z}_{n} &\ge - t_{\mathit{USE},n}\\ T \boldsymbol{q}_{n} - \boldsymbol{z}_{n} &\le - t_{\mathit{USE},n} + T\\ \end{alignedat} \end{split} \quad \forall n \in \mathcal{N}

\begin{split} \begin{alignedat}{2} -T \boldsymbol{q}_{n} + T \boldsymbol{r}_{n} + \boldsymbol{z}_{n} &\le t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}}\\ -T \boldsymbol{q}_{n} + T \boldsymbol{r}_{n} + \boldsymbol{z}_{n} &\ge t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}} - T\\ \end{alignedat} \quad \forall n \in \mathcal{N} \end{split}

\begin{split} \begin{alignedat}{2} T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n} - \boldsymbol{z}_{n} &\le -t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}}\\ T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n} - \boldsymbol{z}_{n} &\ge -t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}} + T\\ \end{alignedat} \quad \forall n \in \mathcal{N} \end{split}

\begin{split} \begin{alignedat}{8} &&\boldsymbol{r}_{n} && {}+{} &&\boldsymbol{s}_{n} && {}-{} &&\boldsymbol{u}_{n} &\ge 0\\ &&\boldsymbol{r}_{n} && {}+{} &&\boldsymbol{s}_{n} && {}-{} &2&\boldsymbol{u}_{n} &\le 0\\ \end{alignedat} \quad \forall n \in \mathcal{N} \end{split}

\begin{split} \begin{aligned} T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} - 2T \boldsymbol{u}_{n} + 2T \boldsymbol{v}_{nk} + 2T \sum_{p \in \mathcal{P}} \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\ \le t_{\mathit{USE},n} - t_{\mathit{USE},k} - \Delta t_{\mathit{PREP}} + 4T \end{aligned}\\ \begin{aligned} T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} + 2T \boldsymbol{u}_{n} + 2T \boldsymbol{v}_{nk} - 2T \sum_{p \in \mathcal{P}} \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\ \ge t_{\mathit{USE},n} - t_{\mathit{USE},k} + \Delta t_{\mathit{PREP}} - 2T \end{aligned}\\ \begin{aligned} T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} - T \boldsymbol{r}_{n} + 2T \boldsymbol{u}_{n} + 2T \sum_{p \in \mathcal{P}} \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\ \le t_{\mathit{USE},n} - t_{\mathit{USE},k} - \Delta t_{\mathit{PREP}} + 4T \end{aligned}\\ \begin{aligned} T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n} - 2T \boldsymbol{u}_{n} - 2T \sum_{p \in \mathcal{P}} \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\ \ge t_{\mathit{USE},n} - t_{\mathit{USE},k} + \Delta t_{\mathit{PREP}} - 4T \end{aligned}\\ \begin{aligned} \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n \end{aligned}\\ \end{split}

Where

The following decision variables are specified.

\boldsymbol{q}_{n} \in \left\{0, 1\right\} \quad \forall n \in \mathcal{N}

\boldsymbol{r}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}

\boldsymbol{s}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}

\boldsymbol{u}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}

\boldsymbol{v}_{nk} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n

\boldsymbol{w}_{nkp} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n, \enspace \forall p \in \mathcal{P}

\boldsymbol{x}_{np} \in \left\{ 0, 1 \right\} \quad \forall n \in \mathcal{N}, \enspace \forall p \in \mathcal{P}

\boldsymbol{y}_{mp} \in \left\{ 0, 1 \right\} \quad \forall m \in \mathcal{M}, \enspace \forall p \in \mathcal{P}

\Delta t_{\mathit{HOLD,MIN}} \le \boldsymbol{z}_{n} \le \Delta t_{\mathit{HOLD,MAX}}; \quad \boldsymbol{z}_{n} \in \mathbb{R} \quad \forall n \in \mathcal{N}

Variant Problems

Basic

The “basic” variant omits the buffer preparation scheduling constraints and as such does not compute a workable schedule. It merely calculates the vessels required to maintain the specified utilization ratio at minimum cost.

Minimized Hold Time

The “minimized hold time” variant involves two rounds of optimization. Firstly, the “complete” problem is solved, resulting in a minimum cost.

Next, the optimum (minimized) cost is set as a constraint:

Z^{\prime} = \min \boldsymbol{Z} \label{eq.Zprime}

\sum_{m \in \mathcal{M}} \sum_{p \in \mathcal{P}} c_m \boldsymbol{y}_{mp} = Z^{\prime}

Then the problem is re-run with the following objective to be minimized:

\boldsymbol{Y} = \sum_{n \in \mathcal{N}} \boldsymbol{z}_{n}

Nomenclature

Symbol Description
\boldsymbol{a}_{nk} buffers n and k prepared in same vessel (binary)
c_{m} (relative) cost of vessel m
f_{\mathit{MAXUSE}} buffer maximum use duration ratio
f_{\mathit{MINFILL}} vessel minimum fill ratio
f_{\mathit{MINUSE}} buffer minimum use duration ratio
f_{\mathit{UTIL}} preparation slot maximum utilisation ratio
k secondary buffer index \left( k \in \mathcal{N}, k \ne n \right)
m vessel size index \left( m \in \mathcal{M} \right)
n buffer index \left( n \in \mathcal{N} \right)
p slot index \left( p \in \mathcal{P} \right)
\boldsymbol{q}_{n} the buffer n hold operation crosses the single-cycle boundaries (binary)
\boldsymbol{r}_{n} \boldsymbol{t}_{\mathit{LOWER},n} occurs before \boldsymbol{t}_{\mathit{PREP},n} in the single-cycle window (binary)
\boldsymbol{s}_{n} \boldsymbol{t}_{\mathit{UPPER},n} occurs after \boldsymbol{t}_{\mathit{PREP},n} in the single-cycle window (binary)
\boldsymbol{t}_{\mathit{LOWER},n} lower bound of feasible scheduling region for all buffers k > n with respect to buffer n
\boldsymbol{t}_{\mathit{PREP},k} preparation reference time for buffer k
\boldsymbol{t}_{\mathit{PREP},n} preparation reference time for buffer n
\boldsymbol{t}_{\mathit{UPPER},n} upper bound of feasible scheduling region for all buffers k > n with respect to buffer n
t_{\mathit{USE},n} buffer n time of first use, normalised
t_{\mathit{USE},n}^{*} buffer n time of first use, un-normalised
\Delta t_{\mathit{FEAS}} maximum feasible buffer use duration
\Delta t_{\mathit{HOLD,MAX}} maximum allowable buffer hold duration
\Delta t_{\mathit{HOLD,MIN}} minimum allowable buffer hold duration
\Delta t_{\mathit{HOLD,POST}} duration of post-use operations in buffer hold procedures
\Delta t_{\mathit{HOLD,PRE}} duration of operations prior to receiving buffer in buffer hold procedures
\Delta t_{\mathit{PREP}} total duration of buffer preparation procedures
\Delta t_{\mathit{PREP,POST}} duration of operations post transferring out buffer in buffer preparation procedures
\Delta t_{\mathit{PREP,PRE}} duration of operations prior to transferring out buffer in buffer preparation procedures
\Delta t_{\mathit{USE},n} duration of use of buffer n
\Delta t_{\mathit{TRANSFER}} duration of transfers from buffer preparation vessel to buffer hold vessel
\boldsymbol{u}_{n} feasible scheduling window for buffer k with respect to buffer n does not cross cycle boundary (binary)
\boldsymbol{v}_{nk} feasible scheduling window for buffer k with respect to buffer n occurs before buffer n preparation procedure (binary)
\boldsymbol{w}_{nkp} distinct buffers n and k are both made in slot p (binary)
\boldsymbol{x}_{np} buffer n is prepared in slot p (binary)
\boldsymbol{y}_{mp} a vessel of size m is in slot p (binary)
\boldsymbol{z}_{n} buffer n hold duration
M number of vessel sizes
\mathcal{M} set of vessel sizes
N number of buffers
\mathcal{N} set of buffers
P number of slots
\mathcal{P} set of slots
T process cycle time (start–to–start duration)
U_{n} volume of buffer n to be prepared
V_{m} maximum working volume of vessel size m
V_{\mathit{MAX}} largest maximum working volume of available vessel sizes
\boldsymbol{Y} secondary objective; sum of buffer hold times, given minimal total vessel cost
\boldsymbol{Z} primary objective; total vessel cost
Z^{\prime} minimal total vessel cost