  Magnetic tapes have been playing a key role as means for storage of digital
data for decades, and their unsurpassed cost-effectiveness still make them the
technology of choice in several industries, such as media and entertainment.
Tapes are mostly used for cold storage nowadays, and therefore the study of
scheduling algorithms for read requests tailored for these devices has been
largely neglected in the literature. In this article, we investigate the Linear
Tape Scheduling Problem (LTSP), in which read requests associated with files
stored on a single-tracked magnetic tape should be scheduled in a way that the
sum of all response times are minimized. LTSP has many similarities with
classical combinatorial optimization problems such as the Traveling Repairmen
Problem and the Dial-a-Ride Problem restricted to the real line; nevertheless,
significant differences on structural properties and strict time-limit
constraints of real-world scenarios make LTSP challenging and interesting on
its own. In this work, we investigate several properties and algorithms for
LTSP and some of its extensions. The results allowed for the identification of
3-approximation algorithms for LTSP and efficient exact algorithms for some of
its special cases. We also show that LTSPR, the version of the problem with
heterogeneous release times for requests, is NP-complete. OLTSP, the online
extension of LTSPR, does not admit c-competitive algorithms for any constant
factor c, but we nevertheless introduce an algorithm for the problem and show
through extensive computational experiments on synthetic and real-world
datasets that different embodiments of the proposed strategy are
computationally efficient and over-perform by orders of magnitude an algorithm
being currently used by real-world tape file systems.
