×

Bamboo garden trimming problem: priority schedulings. (English) Zbl 1461.90043

Summary: The paper deals with the Bamboo Garden Trimming (BGT) problem introduced in [L. Gąsieniec et al., Lect. Notes Comput. Sci. 10139, 229–240 (2017; Zbl 1444.90053)]. The problem is difficult to solved due to its close relationship to Pinwheel scheduling. The garden with \(n\) bamboos is an analogue of a system of \(n\) machines that have to be attended (e.g., serviced) with different frequencies. During each day, bamboo \(b_i\) grows an extra height \(h_i,\) for \(i = 1, \ldots, n\) and, on the conclusion of the day, at most one bamboo has its entire height cut. The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. The contribution in this paper is twofold, and is both theoretical and experimental. In particular, the focus is on understanding what has been called priority schedulings, i.e., cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to \(H = \sum_{i = 1}^n h_i\). 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. As the first result, it is proved that, for any distribution of integer growth rates \(h_1, \ldots, h_n\) and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, the focus is on the so-called \(\mathtt{ReduceMax}\) strategy, a greedy priority scheduling that each day cuts the tallest bamboo, regardless of the growth rates distribution. \(\mathtt{ReduceMax}\) is known to provide a \(O(\log n)\)-approximation, with respect to the lower bound \(H\). One of the main results achieved is that, if \(\mathtt{ReduceMax}\) stabilises in a round-robin type cycle, then it guarantees 2-approximation. Furthermore, preliminary results are provided relating the structure of the input instance, in terms of growth rates, and the behavior of \(\mathtt{ReduceMax}\) when applied to such inputs. Finally, a conjecture that \(\mathtt{ReduceMax}\) is 2-approximating for the BGT problem is claimed, hence an extended experimental evaluation was conducted to support the conjecture and to compare \(\mathtt{ReduceMax}\) with other relevant scheduling algorithms. The obtained results show that \(\mathtt{ReduceMax}\): (i) provides 2-approximation in all considered inputs; and (ii) always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven.

MSC:

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1444.90053

Software:

PESPLib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gąsieniec, L.; Klasing, R.; Levcopoulos, C.; Lingas, A.; Min, J.; Radzik, T.; Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors); SOFSEM 2017: Theory and Practice of Computer Science, Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, 16-20 January 2017: Berlin, Germany 2017; Volume Volume 10139 ,229-240. · Zbl 1444.90053
[2] Holte, R.; Mok, A.; Rosier, L.; Tulchinsky, I.; Varvel, D.; The pinwheel: A real-time scheduling problem; Proceedings of the 22nd Annual Hawaii International Conference on System Sciences: ; Volume Volume 2 ,693-702.
[3] Fishburn, P.C.; Lagarias, J.C.; Pinwheel Scheduling: Achievable Densities; Algorithmica: 2002; Volume 34 ,14-38. · Zbl 1016.68007
[4] Alshamrani, S.; Kowalski, D.R.; Gąsieniec, L.; How Reduce Max Algorithm Behaves with Symptoms Appearance on Virtual Machines in Clouds; Proceedings of the 2015 International Conference on Cloud Computing (ICCC): ; ,1703-1710.
[5] Gąsieniec, L.; Klasing, R.; Martin, R.; Navarra, A.; Zhang, X.; Fast periodic graph exploration with constant memory; J. Comput. Syst. Sci.: 2008; Volume 74 ,802-822. · Zbl 1149.68048
[6] Kosowski, A.; Navarra, A.; Graph Decomposition for Memoryless Periodic Exploration; Algorithmica: 2012; Volume 63 ,26-38. · Zbl 1241.05114
[7] D’Emidio, M.; Di Stefano, G.; Frigioni, D.; Navarra, A.; Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane; Inf. Comput: 2018; Volume 263 ,57-74. · Zbl 1407.68531
[8] D’Emidio, M.; Frigioni, D.; Navarra, A.; Explore and repair graphs with black holes using mobile entities; Theor. Comput. Sci.: 2015; Volume 605 ,129-145. · Zbl 1330.68222
[9] Ntafos, S.; On gallery watchmen in grids; Inf. Process. Lett.: 1986; Volume 23 ,9-102. · Zbl 0609.68048
[10] Urrutia, J.; Art gallery and illumination problems; Handbook of Computational Geometry: Amsterdam, The Netherlands 2000; ,973-1027. · Zbl 0941.68138
[11] Collins, A.; Czyzowicz, J.; Gąsieniec, L.; Kosowski, A.; Kranakis, E.; Krizanc, D.; Martin, R.; Morales Ponce, O.; Optimal Patrolling of Fragmented Boundaries; Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures: New York, NY, USA 2013; ,241-250.
[12] Czyzowicz, J.; Gąsieniec, L.; Kosowski, A.; Kranakis, E.; Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds; Algorithms—ESA 2011, Proceedings of the 19th Annual European Symposium, Saarbrücken, Germany, 5-9 September 2011: Berlin, Germany 2011; Volume Volume 6942 ,701-712. · Zbl 1260.68397
[13] Chuangpishit, H.; Czyzowicz, J.; Gąsieniec, L.; Georgiou, K.; Jurdzinski, T.; Kranakis, E.; Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits; SOFSEM 2018: Theory and Practice of Computer Science, Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, 29 January-2 February 2018: Berlin, Germany 2018; Volume Volume 10706 ,367-380. · Zbl 1445.68031
[14] Serafini, P.; Ukovich, W.; A Mathematical Model for Periodic Scheduling Problems; SIAM J. Discret. Math.: 1989; Volume 2 ,550-581. · Zbl 0676.90030
[15] Chan, M.Y.; Chin, F.Y.L.; General schedulers for the pinwheel problem based on double-integer reduction; IEEE Trans. Comput.: 1992; Volume 41 ,755-768.
[16] Chan, M.Y.; Chin, F.Y.L.; Schedulers for larger classes of pinwheel instances; Algorithmica: 1993; Volume 9 ,425-462. · Zbl 0778.90023
[17] Hsueh, C.; Lin, K.; An Optimal Pinwheel Scheduler Using the Single-number Reduction Technique; Proceedings of the 17th IEEE Real-Time Systems Symposium: ; ,196-205.
[18] Holte, R.; Rosier, L.; Tulchinsky, I.; Varvel, D.; Pinwheel scheduling with two distinct numbers; Theor. Comput. Sci.: 1992; Volume 100 ,105-135. · Zbl 0764.90046
[19] Lin, S.S.; Lin, K.J.; A Pinwheel Scheduler for Three Distinct Numbers with a Tight Schedulability Bound; Algorithmica: 1997; Volume 19 ,411-426. · Zbl 0898.68005
[20] Romer, T.H.; Rosier, L.E.; An algorithm reminiscent of euclidean-gcd for computing a function related to pinwheel scheduling; Algorithmica: 1997; Volume 17 ,1-10. · Zbl 0864.68006
[21] Baruah, S.K.; Lin, S.-S.; Pfair scheduling of generalized pinwheel task systems; IEEE Trans. Comput.: 1998; Volume 47 ,812-816. · Zbl 1391.90241
[22] Baruah, S.K.; Cohen, N.K.; Plaxton, C.G.; Varvel, D.A.; Proportionate progress: A notion of fairness in resource allocation; Algorithmica: 1996; Volume 15 ,600-625. · Zbl 0848.68020
[23] Mok, A.; Rosier, L.; Tulchinski, I.; Varvel, D.; Algorithms and complexity of the periodic maintenance problem; Microprocess. Microprogram.: 1989; Volume 27 ,657-664.
[24] Anily, S.; Glass, C.A.; Hassin, R.; The scheduling of maintenance service; Discret. Appl. Math.: 1998; Volume 82 ,27-42. · Zbl 0897.90119
[25] Anily, S.; Glass, C.A.; Hassin, R.; Scheduling maintenance services to three machines; Ann. Oper. Res.: 1999; Volume 86 ,375-391. · Zbl 0921.90087
[26] Bender, M.A.; Fekete, S.P.; Kröller, A.; Mitchell, J.S.B.; Liberatore, V.; Polishchuk, V.; Suomela, J.; The Minimum Backlog Problem; Theor. Comput. Sci.: 2015; Volume 605 ,51-61. · Zbl 1330.68350
[27] Bodlaender, M.H.L.; Hurkens, C.A.J.; Kusters, V.J.J.; Staals, F.; Woeginger, G.J.; Zantema, H.; Cinderella versus the Wicked Stepmother; TCS 2012: Theoretical Computer Science, Proceedings of the IFIP Theoretical Computer Science Conference, Amsterdam, The Netherlands, 26-28 September 2012: Berlin, Germany 2012; Volume Volume 6942 ,57-71. · Zbl 1362.91011
[28] Chrobak, M.; Csirik, J.; Imreh, C.; Noga, J.; Sgall, J.; Woeginger, G.J.; The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts; Automata, Languages and Programming, Proceedings of the 28th International Colloquium on Automata, Languages, and Programming, Crete, Greece, 8-12 July 2001: Berlin, Germany 2001; Volume Volume 2076 ,862-874. · Zbl 0986.68006
[29] D’Emidio, M.; Di Stefano, G.; Navarra, A.; Priority Scheduling in the Bamboo Garden Trimming Problem; SOFSEM 2019: Theory and Practice of Computer Science, Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, 27-30 January 2019: Berlin, Germany 2019; Volume Volume 11376 ,136-149. · Zbl 1444.90052
[30] Hardy, G.H.; Ramanujan, S.; Asymptotic formulas in combinatorial analysis; Proc. Lond. Math. Soc.: 1918; Volume 17 ,75-115. · JFM 46.0198.04
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.