3.7.68. 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 πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ(πšƒπ™°πš‚π™Ίπš‚,π™»π™Έπ™Όπ™Έπšƒ) constraint that will be used within the context of the longest closed and open hole problems.

Here, πšƒπ™°πš‚π™Ίπš‚ is a collection of tasks, and for a task tβˆˆπšƒπ™°πš‚π™Ίπš‚, t.πš˜πš›πš’πšπš’πš—, t.πšπšžπš›πšŠπšπš’πš˜πš— and t.πš‘πšŽπš’πšπš‘πš denote respectively its start, duration and height, while π™»π™Έπ™Όπ™Έπšƒβˆˆβ„€ + is the height of the resource. The constraint is equivalent to finding an assignment s:πšƒπ™°πš‚π™Ίπš‚.πš˜πš›πš’πšπš’πš—β†’β„€ + 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 πšƒπ™°πš‚π™Ίπš‚ of maximum height π™»π™Έπ™Όπ™Έπšƒ, i.e.:

βˆ€iβˆˆβ„€:Οƒ s (i)=π™»π™Έπ™Όπ™Έπšƒ-P(πšƒπ™°πš‚π™Ίπš‚,i)β‰₯0

where the coverage P(πšƒπ™°πš‚π™Ίπš‚,i) by πšƒπ™°πš‚π™Ίπš‚ of instant iβˆˆβ„€ is:

P(πšƒπ™°πš‚π™Ίπš‚,i)=βˆ‘ tβˆˆπšƒπ™°πš‚π™Ίπš‚βˆ£t.πš˜πš›πš’πšπš’πš—β‰€i<t.πš˜πš›πš’πšπš’πš—+t.πšπšžπš›πšŠπšπš’πš˜πš— t.πš‘πšŽπš’πšπš‘πš

We are now in position to define the longest closed and open hole problems. Given a quantity Οƒβˆˆβ„€ + 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 π‘™π‘π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ (πšƒπ™°πš‚π™Ίπš‚) for which there exists a cumulative placement s of a subset of tasks πšƒπ™°πš‚π™Ίπš‚ ' βŠ†πšƒπ™°πš‚π™Ίπš‚ of maximum height π™»π™Έπ™Όπ™Έπšƒ, such that the resource area that is not occupied by s on interval [0,π‘™π‘π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ ) does not exceed the maximum allowed slack value Οƒ:

βˆ‘ i=0 π‘™π‘π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ -1 Οƒ s (i)≀σ.

The longest open hole problem is to find the largest integer π‘™π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ (πšƒπ™°πš‚π™Ίπš‚) for which there exist a cumulative placement s of a subset of tasks πšƒπ™°πš‚π™Ίπš‚ ' βŠ†πšƒπ™°πš‚π™Ίπš‚ of maximum height π™»π™Έπ™Όπ™Έπšƒ and an interval [i ' ,i ' +π‘™π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ )βŠ‚β„€ of length π‘™π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ , such that the resource area that is not occupied by s on [i ' ,i ' +π‘™π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ ) does not exceed the maximum allowed slack value Οƒ:

βˆ‘ i=i ' i ' +π‘™π‘šπ‘Žπ‘₯ Οƒ π™»π™Έπ™Όπ™Έπšƒ -1 Οƒ s (i)≀σ.

As an example, consider seven tasks of respective size 11Γ—11, 9Γ—9, 8Γ—8, 7Γ—7, 6Γ—6, 4Γ—4, 2Γ—2. PartΒ (A) of FigureΒ 3.7.16 provides a cumulative placement corresponding to the longest open hole problem according to π™»π™Έπ™Όπ™Έπšƒ=11 and Οƒ=0. The longest open hole π‘™π‘šπ‘Žπ‘₯ 0 11 ({11Γ—11,9Γ—9,8Γ—8,7Γ—7,6Γ—6,4Γ—4,2Γ—2})=17 since:

  • The task 8Γ—8 cannot contribute since a gap of 3 cannot be filled by the unique candidate the task 2Γ—2.

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

The longest close hole π‘™π‘π‘šπ‘Žπ‘₯ 0 11 ({11Γ—11,9Γ—9,8Γ—8,7Γ—7,6Γ—6,4Γ—4,2Γ—2})=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Γ—2. PartΒ (B) of FigureΒ 3.7.16 provides a cumulative placement corresponding to the longest open hole problem according to Ο΅=11 and Οƒ=20. The longest open hole π‘™π‘šπ‘Žπ‘₯ 20 11 ({3Γ—2})=2.

Figure 3.7.16. Examples for illustrating the longest closed and open holes problems
ctrs/lmax_example

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

Figure 3.7.17. Examples of longest closed holes for various gaps
ctrs/longest_closed_hole
Figure 3.7.18. Examples of longest open holes for various gaps
ctrs/longest_open_hole