Advanced

Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)

Levcopoulos, Christos LU ; Lingas, Andrzej LU ; Gąsieniec, Leszek; Klasing, Ralf; Min, Jie and Radzik, Tomasz (2017) 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2017 In Lecture Notes in Computer Science (LNCS) 10139. p.229-240
Abstract
A garden G is populated by n≥1
n≥1 bamboos b1,b2,...,bn
with the respective daily growth rates h 1 ≥h 2 ≥⋯≥h n
h1≥h2≥⋯≥hn. It is assumed that the initial heights of bamboos are zero. The robotic gardener or simply a robot maintaining the bamboo garden is attending bamboos and trimming them to height zero according to some schedule. The Bamboo Garden Trimming Problem, or simply BGT, is to design a perpetual schedule of cuts to maintain the elevation of bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced with different frequencies, by a robot which can service only one machine during a visit. The objective is to design a perpetual schedule of servicing the... (More)
A garden G is populated by n≥1
n≥1 bamboos b1,b2,...,bn
with the respective daily growth rates h 1 ≥h 2 ≥⋯≥h n
h1≥h2≥⋯≥hn. It is assumed that the initial heights of bamboos are zero. The robotic gardener or simply a robot maintaining the bamboo garden is attending bamboos and trimming them to height zero according to some schedule. The Bamboo Garden Trimming Problem, or simply BGT, is to design a perpetual schedule of cuts to maintain the elevation of bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced with different frequencies, by a robot which can service only one machine during a visit. The objective is to design a perpetual schedule of servicing the machines which minimizes the maximum (weighted) waiting time for servicing.

We consider two variants of BGT. In discrete BGT the robot is allowed to trim only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next one and this time is defined by a weighted network of connections.

For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel scheduling problem, we obtain also a 2-approximation and even a closer approximation for more balanced growth rates. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h 1 /h n )) and O(logn)

.
(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science (LNCS)
volume
10139
pages
12 pages
publisher
Springer
conference name
43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2017
external identifiers
  • scopus:85010682314
ISBN
978-3-319-51962-3
978-3-319-51963-0
DOI
10.1007/978-3-319-51963-0_18
language
English
LU publication?
yes
id
7fc24267-259c-45e5-83d7-3b316e462262
date added to LUP
2017-02-09 20:09:34
date last changed
2018-04-29 04:35:53
@inproceedings{7fc24267-259c-45e5-83d7-3b316e462262,
  abstract     = {A garden G is populated by n≥1 <br/>n≥1 bamboos  b1,b2,...,bn<br/> with the respective daily growth rates h 1 ≥h 2 ≥⋯≥h n  <br/>h1≥h2≥⋯≥hn. It is assumed that the initial heights of bamboos are zero. The robotic gardener or simply a robot maintaining the bamboo garden is attending bamboos and trimming them to height zero according to some schedule. The Bamboo Garden Trimming Problem, or simply BGT, is to design a perpetual schedule of cuts to maintain the elevation of bamboo garden as low as possible. The bamboo garden is a metaphor for a collection of machines which have to be serviced with different frequencies, by a robot which can service only one machine during a visit. The objective is to design a perpetual schedule of servicing the machines which minimizes the maximum (weighted) waiting time for servicing.<br/><br/>We consider two variants of BGT. In discrete BGT the robot is allowed to trim only one bamboo at the end of each day. In continuous BGT the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next one and this time is defined by a weighted network of connections.<br/><br/>For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel scheduling problem, we obtain also a 2-approximation and even a closer approximation for more balanced growth rates. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h 1 /h n ))  and O(logn) <br/><br/>.<br/>},
  author       = {Levcopoulos, Christos and Lingas, Andrzej and Gąsieniec, Leszek and Klasing, Ralf and Min, Jie and Radzik, Tomasz},
  booktitle    = {Lecture Notes in Computer Science (LNCS)},
  isbn         = {978-3-319-51962-3},
  language     = {eng},
  month        = {01},
  pages        = {229--240},
  publisher    = {Springer},
  title        = {Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)},
  url          = {http://dx.doi.org/10.1007/978-3-319-51963-0_18},
  volume       = {10139},
  year         = {2017},
}