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
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:
https://lup.lub.lu.se/record/7fc24267-259c-45e5-83d7-3b316e462262
- author
- Levcopoulos, Christos
LU
; Lingas, Andrzej
LU
; Gąsieniec, Leszek
; Klasing, Ralf
; Min, Jie
and Radzik, Tomasz
- organization
- publishing date
- 2017-01-11
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Lecture Notes in Computer Science (LNCS) : In: Steffen B., Baier C., van den Brand M., Eder J., Hinchey M., Margaria T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science, vol 10139. Springer, Cham - In: Steffen B., Baier C., van den Brand M., Eder J., Hinchey M., Margaria T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science, vol 10139. Springer, Cham
- volume
- 10139
- pages
- 12 pages
- publisher
- Springer
- conference name
- 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2017
- conference location
- Limerick, Ireland
- conference dates
- 2017-01-16 - 2017-01-20
- 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
- 2024-03-17 07:26:09
@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) : In: Steffen B., Baier C., van den Brand M., Eder J., Hinchey M., Margaria T. (eds) SOFSEM 2017: Theory and Practice of Computer Science. SOFSEM 2017. Lecture Notes in Computer Science, vol 10139. Springer, Cham}},
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}},
doi = {{10.1007/978-3-319-51963-0_18}},
volume = {{10139}},
year = {{2017}},
}