### 3.7.71. Cumulative longest hole problems

A constraint that can use some filtering based on the longest closed and open hole problems Β [BeldiceanuCarlssonPoder08]. We follow the presentation from the previous paper. Before presenting the longest closed open holeΒ scheduling problems, let us first introduce some notation related to the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi \pi °\pi \pi Ί\pi },\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\right)$ constraint that will be used within the context of the longest closed and open hole problems.

Here, $\mathrm{\pi \pi °\pi \pi Ί\pi }$ is a collection of tasks, and for a task $t\beta \mathrm{\pi \pi °\pi \pi Ί\pi }$, $t.\mathrm{\pi \pi \pi \pi \pi \pi }$, $t.\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ and $t.\mathrm{\pi \pi \pi \pi \pi \pi }$ denote respectively its start, duration and height, while $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }\beta {\mathrm{\beta €}}^{+}$ is the height of the resource. The constraint is equivalent to finding an assignment $s:\mathrm{\pi \pi °\pi \pi Ί\pi }.\mathrm{\pi \pi \pi \pi \pi \pi }\beta {\mathrm{\beta €}}^{+}$Without loss of generality we assume the earliest start of each task to be greater than or equal to 0. that solves the cumulative placement of $\mathrm{\pi \pi °\pi \pi Ί\pi }$ of maximum height $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$, i.e.:

$\beta i\beta \mathrm{\beta €}:{\mathrm{Ο}}_{s}\left(i\right)=\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }-P\left(\mathrm{\pi \pi °\pi \pi Ί\pi },i\right)\beta ₯0$

where the coverage $P\left(\mathrm{\pi \pi °\pi \pi Ί\pi },i\right)$ by $\mathrm{\pi \pi °\pi \pi Ί\pi }$ of instant $i\beta \mathrm{\beta €}$ is:

$P\left(\mathrm{\pi \pi °\pi \pi Ί\pi },i\right)=\underset{t\beta \mathrm{\pi \pi °\pi \pi Ί\pi }\beta £t.\mathrm{\pi \pi \pi \pi \pi \pi }\beta €i

We are now in position to define the longest closed and open hole problems. Given a quantity $\mathrm{Ο}\beta {\mathrm{\beta €}}^{+}$ of slack (i.e.Β the difference between the available space and the total area of the tasks to place), the longest closed hole problem is to find the largest integer ${\mathrm{\pi \pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}\left(\mathrm{\pi \pi °\pi \pi Ί\pi }\right)$ for which there exists a cumulative placement $s$ of a subset of tasks ${\mathrm{\pi \pi °\pi \pi Ί\pi }}^{\text{'}}\beta \mathrm{\pi \pi °\pi \pi Ί\pi }$ of maximum height $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$, such that the resource area that is not occupied by $s$ on interval $\left[0,{\mathrm{\pi \pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}\right)$ does not exceed the maximum allowed slack value $\mathrm{Ο}$:

$\underset{i=0}{\overset{{\mathrm{\pi \pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}-1}{\beta }}{\mathrm{Ο}}_{s}\left(i\right)\beta €\mathrm{Ο}.$

The longest open hole problem is to find the largest integer ${\mathrm{\pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}\left(\mathrm{\pi \pi °\pi \pi Ί\pi }\right)$ for which there exists a cumulative placement $s$ of a subset of tasks ${\mathrm{\pi \pi °\pi \pi Ί\pi }}^{\text{'}}\beta \mathrm{\pi \pi °\pi \pi Ί\pi }$ of maximum height $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }$ and an interval $\left[{i}^{\text{'}},{i}^{\text{'}}+{\mathrm{\pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}\right)\beta \mathrm{\beta €}$ of length ${\mathrm{\pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}$, such that the resource area that is not occupied by $s$ on $\left[{i}^{\text{'}},{i}^{\text{'}}+{\mathrm{\pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}\right)$ does not exceed the maximum allowed slack value $\mathrm{Ο}$:

$\underset{i={i}^{\text{'}}}{\overset{{i}^{\text{'}}+{\mathrm{\pi \pi \pi \pi ₯}}_{\mathrm{Ο}}^{\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }}-1}{\beta }}{\mathrm{Ο}}_{s}\left(i\right)\beta €\mathrm{Ο}.$

As an example, consider seven tasks of respective size $11\Gamma 11$, $9\Gamma 9$, $8\Gamma 8$, $7\Gamma 7$, $6\Gamma 6$, $4\Gamma 4$, $2\Gamma 2$. PartΒ (A) of FigureΒ 3.7.20 provides a cumulative placement corresponding to the longest open hole problem according to $\mathrm{\pi »\pi Έ\pi Ό\pi Έ\pi }=11$ and $\mathrm{Ο}=0$. The longest open hole ${\mathrm{\pi \pi \pi \pi ₯}}_{0}^{11}\left(\left\{11\Gamma 11,9\Gamma 9,8\Gamma 8,7\Gamma 7,6\Gamma 6,4\Gamma 4,2\Gamma 2\right\}\right)=17$ since:

• The task $8\Gamma 8$ cannot contribute since a gap of 3 cannot be filled by the unique candidate the task $2\Gamma 2$.

• The task $6\Gamma 6$ can also not contribute since a gap of 5 cannot be completely filled by the candidates $4\Gamma 4$ and $2\Gamma 2$.

The longest close hole ${\mathrm{\pi \pi \pi \pi \pi ₯}}_{0}^{11}\left(\left\{11\Gamma 11,9\Gamma 9,8\Gamma 8,7\Gamma 7,6\Gamma 6,4\Gamma 4,2\Gamma 2\right\}\right)=15$: it corresponds to the longest time interval on which the resource is saturated by the illustrated placement and such that one bound of the interval does not intersect any tasks.

Second, consider a task of size $3\Gamma 2$. PartΒ (B) of FigureΒ 3.7.20 provides a cumulative placement corresponding to the longest open hole problem according to $\mathrm{Ο΅}=11$ and $\mathrm{Ο}=20$. The longest open hole ${\mathrm{\pi \pi \pi \pi ₯}}_{20}^{11}\left(\left\{3\Gamma 2\right\}\right)=2$.

FigureΒ 3.7.21 provides examples of the longest closed hole when we have 15 squares of sizes $1,2,\beta ―,15$ and a zero slack. PartsΒ (A), (B),...,(O) respectively give a solution achieving the longest closed hole for a gap of $1,2,\beta ―,15$. For comparison, FigureΒ 3.7.22 provides the same examples of the longest open hole with zero slack.