Linear/Integer Programming: Scheduling task with regular intervals 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.
 A: 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.
