# Bamboo Garden Trimming Problem: Priority Schedulings +
## 1 Introduction  
This paper deals with a perpetual scheduling problem in which \(n\) machines, denoted later as _bamboos_, need to be attended with possibly known and likely different frequencies. In other words, some machines may have to be attended more often than others. This problem was proposed andstudied by [1] under the name of Bamboo Garden Trimming (BGT) problem. Given is a collection (garden) of \(n\) bamboos \(b_{1}\), \(b_{2}\),..., \(b_{n}\) along with respective daily growth rates \(h_{1}\), \(h_{2}\),..., \(h_{n}\) greater than 0. The authors of [1] assumed that, initially, the height of each bamboo is set to zero, whereas in this paper bamboos are allowed to start with arbitrary heights. The robotic gardener maintaining the garden trims one bamboo per day to height zero according to some predefined schedule. The main goal in BGT is to design perpetual schedules of cuts which keep the height of the tallest ever bamboo as low as possible. The main constraints are that the gardener is allowed to cut exactly one (of their choice) bamboo at the end of each day and is not allowed to attend the garden at any other times. Once the gardener has decided which bamboo to trim at the end of the current day (which corresponds to one round in the schedule), the action of actual trimming is instantaneous. Different variants of the problem have been defined [1], but, in its \"easiest\" representation, all data are available to the gardener, i.e., one knows how many bamboos form the garden and for each bamboo what is the daily growth rate. Hence, one may think about trimming strategies that consider all the data, or simply choosing the bamboo to be trimmed according with the current status of the garden. The problem reveals a combinatorial beauty, also related to the easiness of its definition that rapidly allows to start thinking about trimming strategies. As a first thought, it usually appears surprising that that the problem comes out to be of difficult resolution. This further motivates the design of different and efficient trimming strategies, varying on the usage of the available data. Moreover, the interest to this problem comes from its close relation with fundamental scheduling problems, e.g., _Pinwheel_ scheduling. The Pinwheel problem [2] is defined as follows. Given a set \(V=f_{1},f_{2},\ldots,f_{n}\) of positive integers called _Pinwheel frequencies_, one is asked to create an infinite sequence \(S\) of indices drawn from the set 1, 2,..., \(n\), such that, any sub-sequence of \(f_{i}\in V\) consecutive elements in \(S\) includes at least one index \(i\). The density of set \(V\) is defined as \(D=\sum_{i=1}^{n}\frac{1}{f_{i}}\) and it is known that instances having density \(D>1\) cannot be scheduled. An example of input instance for the Pinwheel problem is shown in Figure 1.  
In [2], it has been shown that Pinwheel is NP-hard assuming succinct representation of the problem, whereas it can be efficiently solved when the Pinwheel frequencies are powers of 2 and the density is at most 1 [1,3]. In [1], a 2-approximation algorithm for BGT, based on the resolution of the Pinwheel problem in the special case where frequencies are powers of 2 and the density is at most 1, has been introduced. In more details, given an instance of BGT with rates \(\{h_{1},h_{2},\ldots,h_{n}\}\), one can create a parametrical instance \(I(\delta)\) of Pinwheel with frequencies  
\[f_{i}=\left\lfloor(1+\delta)\frac{H}{h_{i}}\right\rfloor,\text{ for }i=1,2, \ldots,n\text{ and for any }\delta>0\]  
Figure 1: An example of input instance for the Pinwheel problem where \(V=(2,4,7)\) and hence \(D=1/2+1/4+1/7\approx 0.89\). and prove that a (feasible) solution to \(I(\delta)\) implies a \((1+\delta)\)-approximation schedule for the original BGT instance. In particular, one can set \(\delta=1\) and round frequencies to closest power of two to obtain an instance of Pinwheel having power of two frequencies and density \(D\leq 1\), that can be scheduled efficiently by a greedy algorithm.