We consider the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is NP-hard due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines which have to be attended (e.g., serviced) with different frequencies. During each day, bamboo bi grows an extra height hi for i=1,…,n and, on the conclusion of the day, at most one bamboo is cut all its current height. The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. Our contribution is twofold, and is both theoretical and experimental. In particular, we focus on understanding what we call priority schedulings, i.e. cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to (formula Presented). Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely. We prove that for any distribution of integer growth rates h1,…,hn and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, we focus on the so-called ReduceMax strategy, a greedy priority scheduling which each day cuts the tallest bamboo, regardless of the growth rates distribution. ReduceMax is known to provide a O(log n) -approximation, w.r.t. the lower bound H. We prove that, if ReduceMax stabilises in a round-robin type cycle, then it guarantees 2-approximation. We conjecture that ReduceMax is 2-approximating for the BGT problem, hence we conduct an extended experimental evaluation, on all bounded in size integer instances of BGT, to support our conjecture and to compare ReduceMax with other relevant scheduling algorithms. Our results show that ReduceMax provides 2-approximation in such instances, and it always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven.
Priority scheduling in the Bamboo garden trimming problem
Navarra A.
2019
Abstract
We consider the Bamboo Garden Trimming (BGT) problem introduced in [Gąsieniec et al., SOFSEM’17]. The problem is NP-hard due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines which have to be attended (e.g., serviced) with different frequencies. During each day, bamboo bi grows an extra height hi for i=1,…,n and, on the conclusion of the day, at most one bamboo is cut all its current height. The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. Our contribution is twofold, and is both theoretical and experimental. In particular, we focus on understanding what we call priority schedulings, i.e. cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to (formula Presented). Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely. We prove that for any distribution of integer growth rates h1,…,hn and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, we focus on the so-called ReduceMax strategy, a greedy priority scheduling which each day cuts the tallest bamboo, regardless of the growth rates distribution. ReduceMax is known to provide a O(log n) -approximation, w.r.t. the lower bound H. We prove that, if ReduceMax stabilises in a round-robin type cycle, then it guarantees 2-approximation. We conjecture that ReduceMax is 2-approximating for the BGT problem, hence we conduct an extended experimental evaluation, on all bounded in size integer instances of BGT, to support our conjecture and to compare ReduceMax with other relevant scheduling algorithms. Our results show that ReduceMax provides 2-approximation in such instances, and it always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
