Online algorithms for the Linear Tape Scheduling Problem

Abstract

Even in today's world of increasingly faster storage technologies, magnetic tapes continue to play an essential role in the market. Yet, they are often overlooked in the literature, despite the many changes made to the underlying tape architecture since they were conceived. In this article, we introduce the LINEAR TAPE SCHEDULING PROBLEM (LTSP), which aims to identify scheduling strategies for read and write operations in single-tracked magnetic tapes that minimize the overall response times for read requests. Structurally, LTSP has many similarities with versions of the Travelling Repairman Problem and of the Dial-a-Ride Problem restricted to the real line. We investigate several properties of LTSP and show how they can be explored in the design of algorithms for the online version of the problem. Computational experiments show that the resulting strategies deliver very satisfactory scheduling plans, which in most cases are clearly superior (potentially differing by one order of magnitude) to those produced by a strategy currently used in the industry.