2019-07-02

Title: Online scheduling in magnetic tapes

Speaker: Carlos Cardonha (IBM Research Brazil)

Location: LIP, meeting room M7 3rd floor

Schedule: 14:30

Abstract: Magnetic tapes have been playing a key role as means for storage of digital data for decades, and their unsurpassed cost-effectiveness still makes 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.

Mini-bio: Carlos Cardonha is a Research Staff Member at the Natural Resources Optimization group at IBM Research Brazil, with a Ph.D. in Mathematics (T.U. Berlin) and with a Bachelor’s and a Master’s degree in Computer Science (Universidade de São Paulo). His primary research interests are mathematical programming and theoretical computer science, with focus on the application of techniques in mixed integer linear programming, combinatorial optimization, and algorithms design and analysis to real-world and/or operations research problems.