Fractional Bamboo Trimming and Distributed Windows Scheduling

This paper studies two related scheduling problems: fractional bamboo trimming and distributed windows scheduling. In the fractional bamboo trimming problem, we are given n bamboos with different growth rates and cut fractions. At the end of each day, we can cut a fraction of one bamboo. The goal is to design a perpetual schedule of cuts to minimize the height of the tallest bamboo ever. For this problem, we present a 2-approximation algorithm. In addition, we prove upper bounds on the approximation factors of well-known algorithms Reduce-Max and Reduce-Fastest(x) for this problem. In the closely related windows scheduling problem, given a multiset of positive integers \(W = \{w_1, ..., w_n\}\) , we want to schedule n pages on broadcasting channels such that the time interval between any two consecutive appearances of the i-th page ( \(1 \le i \le n\) ) is at most \(w_i\) . The goal of this problem is to minimize the number of channels. We provide an algorithm for the windows scheduling problem that uses at most \(\left\lceil \frac{d(W) + 1}{0.75} \right\rceil \) channels, where \(d(W) = \sum _{i=1}^{n}{\frac{1}{w_i}}\) . When \(d(W) \le 46\) , our algorithm guarantees a smaller upper bound on the number of channels than the best-known algorithm in the literature. We also describe the first approximation algorithm for the windows scheduling problem in a distributed setting, where input data is partitioned among a set of m machines. Furthermore, we introduce patterns of some multisets with \(d(W) \le 1\) for which windows scheduling on one channel (i.e., pinwheel scheduling) is impossible.