2
$\begingroup$

Given is the following problem: There are $N$ items that have to be processed in given intervals over a year. For example, item $i_1$ is processed about every 14 days, item $i_2$ is processed monthly. The actual processing intervals are flexible, but they should be as close to the given intervals as possible. During holidays, no items are processed. Processing item $i$ takes $t_i$ hours and every day, only 8 hours are available for processing. The task is to determine when each item $i$ should be processed.

I believe this task could be solved with integer programming. Hence, I created a model, but I failed to link the missing parts together (see below). My primary questions are:

  • Is integer programming suitable for this task?
  • Are there already known problems that have a similar setting (e.g., traveling sales person) that can serve as a basis for this task?
  • How would you define the model?

To show that I actually thought about this problem, I will describe my model and my issues with this model in the following. My model uses the following variables:

  • $x_{ijk} \in \lbrace 0, 1 \rbrace$ with $x_{ijk} = 1$ iff item $i$ is processed the $k$th time at day $j$
  • $y_{ik} \in \mathbb{N}_0$: day when item $i$ is processed the $k$th time
  • $z_{il} \in \mathbb{N}_0$: how much the $l$th interval diverges from the optimal interval

Here, I represent dates as numbers in $[0, 365)$, where 0 corresponds to January, 1st. In the following, $i$ refers to items, $j$ refers to days, $k$ refers to an index (the $k$th time processing), unless otherwise stated.

My objective is to minimize the total divergence from the optimal intervals $z$:

$$ \sum_i^N \sum_l^{K_i - 1} z_{ik} \rightarrow \min $$ where $K_i$ is the number an item $i$ is processed throughout a year (e.g., 12, if item $i$ is processed monthly).

Then, I defined the following constraints:

  • An item is processed at most once a day: $\sum_k^{K_i} x_{ijk} \leq 1 \; \forall i, j$
  • An item must be processed the $k$th time at some day: $\sum_j^{365} x_{ijk} = 1 \; \forall i, k$
  • No processing on holidays: $\sum_i^N \sum_k^{K_i} x_{ijk} = 0 \; \forall j \in H$ (the set of holidays)
  • Maximum 8 hours per day: $\sum_i^N \sum_k^{K_i} x_{ijk} \cdot t_i \leq 8 \; \forall j$
  • Range of $y$: $0 \leq y_{ik} \leq 365 \; \forall i, k$
  • $k+1$th processing occurs after $k$th processing: $y_{i(k + 1)} \geq y_{ik} + 1 \; \forall i, k$
  • Bind $y$ and $z$: $z_{ik} \geq y_{i(k+1)} - y_{ik} - z_{ik} \; \wedge \; z_{ik} \geq -(y_{i(k+1)} - y_{ik} - z_{ik}) \; \forall i, k$

However, a constraint that binds $x$ and $y$ is still missing. I believe that this constraint should state that $x_{ijk} = 1$ iff $y_{ik} = j$ for all $i, j, k$. Something like $x_{ijk} \implies y_{ijk}$ is quite straightforward, but the other direction seems to be more difficult. Furthermore, I think that the numbers of variables might be too high, e.g., $x_{ij}$ could be sufficient, and lastly, I am not sure whether there are other issues with this model. Hence, I'd like to get some suggestions on this.

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Yes, integer programming is a natural choice. You can link $x$ and $y$ via $$\sum_j j x_{i,j,k} = y_{i,k}$$

An alternative formulation is to use network flow in a time-space network with a node $(i,j)$ for each item $i$ and day $j$ (just omit holidays), a directed arc from $(i,j)$ to $(i,j')$ with $j < j'$, source node $(s,0)$, and sink node $(t,366)$. Let binary arc variable $w_{i,j,j'}$ indicate whether item $i$ is scheduled on days $j$ and $j'$ and not on any days in between. Let $\ell_i$ be the desired length of the processing interval for item $i$. The problem is to minimize $$\sum_{i,j,j'} |j'-j-\ell_i| w_{i,j,j'}$$ subject to \begin{align} \sum_{i,j,j'} w_{i,j,j'} - \sum_{i,j',j} w_{i,j',j} &= \begin{cases} 1 &\text{if $(i,j)=(s,0)$} \\ -1 &\text{if $(i,j)=(t,366)$} \\ 0 &\text{otherwise} \end{cases} &&\text{for all $(i,j)$} \tag1\\ \sum_{j,j'} w_{i,j,j'} &= K_i+1 &&\text{for all $i$} \tag2\\ \sum_{i,j,j'} t_i w_{i,j,j'} &\le 8 &&\text{for all $j>0$} \tag3\\ \end{align} Constraint $(1)$ is the flow balance constraint for each node. Constraint $(2)$ enforces processing item $i$ a total of $K_i$ times. Constraint $(3)$ enforces the daily processing hours limit.

$\endgroup$
1
  • $\begingroup$ Thank you, Rob, I'll try it as soon as possible! :) $\endgroup$ Commented Dec 21, 2020 at 1:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.