Online Algorithms for the Linear Tape Scheduling Problem. Cardonha, C. & Real, L. V. In
Online Algorithms for the Linear Tape Scheduling Problem [link]Paper  abstract   bibtex   
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 by the literature, despite the many changes in the underlying tape architecture since they were first presented. 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 Traveling Repairmen 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.
@inproceedings {icaps16-138,
    track    = {​Main Track},
    title    = {Online Algorithms for the Linear Tape Scheduling Problem},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13032},
    author   = {Carlos Cardonha and  Lucas Villa Real},
    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 by the literature, despite the many changes in the underlying tape architecture since they were first presented. 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 Traveling Repairmen 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.},
    keywords = {Scheduling,Online/real-time planning and scheduling,Complexity analysis}
}
Downloads: 0