We consider the online scheduling problem for sorting bu ers on a line metric. This problem
is motivated by an application to disc scheduling. The input to this problem is a sequence of
requests. Each request is a block of data to be written on a speci ed track of the disc. The disc
is modelled as a number of tracks arranged on a line. To write a block on a particular track, the
scheduler has to bring the disc head to that track. The cost of moving the disc head from a track
to another is the distance between those tracks. A sorting bu er that can store at most k request
at a time is available to the scheduler. This bu er can be used to rearrange the input sequence.
The objective is to minimize the total cost of head movement while serving the requests. On a
disc with n uniformly-spaced tracks, we give a randomized online algorithm with a competitive
ratio of O(log3 n) against an oblivious adversary. This algorithm also yields a competitive ratio
of (k)
By: Vinayaka Pandit, Rohit Khandekar
Published in: RI05008 in 2005
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
;
Questions about this service can be mailed to reports@us.ibm.com .