Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Perpetual maintenance of machines with different urgency requirements

Gasieniec, Leszek ; Klasing, Ralf ; Levcopoulos, Christos LU orcid ; Lingas, Andrzej LU ; Min, Jie and Radzik, Tomasz (2022)
Abstract
A garden G is populated by n≥1 bamboos b1,b2,...,bn with the respective daily growth rates h1≥h2≥⋯≥hn. It is assumed that the initial heights of bamboos are zero. The robotic gardener maintaining the garden regularly attends bamboos and trims them to height zero according to some schedule. The Bamboo Garden Trimming Problem (BGT) is to design a perpetual schedule of cuts to maintain the elevation of the 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 at a time. The objective is to design a perpetual schedule of servicing which... (More)
A garden G is populated by n≥1 bamboos b1,b2,...,bn with the respective daily growth rates h1≥h2≥⋯≥hn. It is assumed that the initial heights of bamboos are zero. The robotic gardener maintaining the garden regularly attends bamboos and trims them to height zero according to some schedule. The Bamboo Garden Trimming Problem (BGT) is to design a perpetual schedule of cuts to maintain the elevation of the 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 at a time. The objective is to design a perpetual schedule of servicing which minimizes the maximum (weighted) waiting time for servicing.
We consider two variants of BGT. In discrete BGT the robot trims 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.
For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel scheduling problem, we derive a 2-approximation algorithm for the general case and a tighter approximation when the growth rates are balanced. A by-product of this last approximation algorithm is that it settles one of the conjectures about the Pinwheel problem. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h1/hn)) and O(logn). (Less)
Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Book/Report
publication status
published
subject
pages
28 pages
DOI
10.48550/arXiv.2202.01567
language
English
LU publication?
yes
additional info
A preliminary version appeared in the proceedings of SOFSEM 2017.
id
7331d644-2cb2-49c6-ab96-be3e5cdb8c0e
date added to LUP
2022-11-17 12:46:43
date last changed
2022-11-17 15:40:25
@techreport{7331d644-2cb2-49c6-ab96-be3e5cdb8c0e,
  abstract     = {{A garden G is populated by n≥1 bamboos b<sub>1</sub>,b<sub>2</sub>,...,b<sub>n</sub> with the respective daily growth rates h<sub>1</sub>≥h<sub>2</sub>≥⋯≥h<sub>n</sub>. It is assumed that the initial heights of bamboos are zero. The robotic gardener maintaining the garden regularly attends bamboos and trims them to height zero according to some schedule. The Bamboo Garden Trimming Problem (BGT) is to design a perpetual schedule of cuts to maintain the elevation of the 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 at a time. The objective is to design a perpetual schedule of servicing which minimizes the maximum (weighted) waiting time for servicing.<br/>We consider two variants of BGT. In discrete BGT the robot trims 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.<br/>For discrete BGT, we show a simple 4-approximation algorithm and, by exploiting relationship between BGT and the classical Pinwheel scheduling problem, we derive a 2-approximation algorithm for the general case and a tighter approximation when the growth rates are balanced. A by-product of this last approximation algorithm is that it settles one of the conjectures about the Pinwheel problem. For continuous BGT, we propose approximation algorithms which achieve approximation ratios O(log(h<sub>1</sub>/h<sub>n</sub>)) and O(logn).}},
  author       = {{Gasieniec, Leszek and Klasing, Ralf and Levcopoulos, Christos and Lingas, Andrzej and Min, Jie and Radzik, Tomasz}},
  language     = {{eng}},
  title        = {{Perpetual maintenance of machines with different urgency requirements}},
  url          = {{http://dx.doi.org/10.48550/arXiv.2202.01567}},
  doi          = {{10.48550/arXiv.2202.01567}},
  year         = {{2022}},
}