A system S is formed of n >= 1 machines m_1, m_2, ..., m_n which needs to be visited andmaintained on regular basis. Each machine m_i has a maintenance indicator x_i which isincremented daily by a fixed term h_i, where h_1 \ge ... \ge h_m.Every day an engineer is allowed to visit and maintain exactly one machine and in turnto reset the relevant indicator to 0. Perpetual maintenance of machines (PMM) problemrefers to the design of perpetual schedules with the goal of keeping maintenance indicatorsas low as possible. The problem is hard due to its close relationship to Pinwheel scheduling.

We present several greedy scheduling algorithms including a simple 4-approximationalgorithm and by exploring the relationship to Pinwheel scheduling we obtain 2-approximationand further (1+e)-approximation for balanced maintenance terms h_1,...,h_m.We also consider a spatial variant of PMM for which we propose approximation algorithmswith ratios O(log(h_1/h_n)) and O(log n).

We conclude with the most recent results and open problems related to PMM.

Prof Leszek Antoni Gasieniec, PhD (1994) in Computer Science, Warsaw University, Poland. Postdocs at Université du Québec à Hull in Canada (94-95), and Max-Planck Institut für Informatik in Saarbruecken, Germany (95-97). He has been with the University of Liverpool since October 1997 becoming full professor in 2003. He was the Head of Computer Science Department in years 2012-2015. The main research strand of Prof Gasieniec’s research explorations is in the design and analysis of efficient algorithms for combinatorial problems, with a special interest in Distributed Algorithms, Networks, and Search Problems.

His research was funded by EPSRC, MRC, BBSRC, Royal Academy of Engineering, Royal Society, and British Council. He is a member of the EPSRC College, the panel for the Royal Society’s Newton International Fellowships, and he reviewed grant proposals for the Canadian, Dutch, French, Greek, Hong Kong, Israeli and Polish national scientific foundations. Prof Gasieniec has published about 150 research positions in the top quality computing journals and the proceedings of the leading international conferences in the field. He edited three volumes in Theoretical Computer Science devoted to selected papers from FCT’03,’13 and SIROCCO’06 and contributed three entries to Springer Encyclopedia of Algorithms. He was on the Award Committee for the Prize for Innovation in Distributed Computing in 2009. He is on the editorial board of Theoretical Computer Science, Journal of Discrete Algorithms (Elsevier) and LMS Journal of Computation and Mathematics. He regularly serves on PCs for the top conferences in the field including ESA’10, IPDPS’11,’12,’13,’14,'17 ICALP’13,’14, and’15, PODC'08 and PC Chair for FCT’13 and ALGOSENOSRS '15 and '16. He organised a number of research meetings including the largest European conference on Algorithms ALGO 2010. He is also a successful PhD supervisor.