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