An efficient algorithm for allocating paged, drum-like storage

Cody and Coffman have studied the problem of distributing a set of a equal-size records among the sectors of a drum-like storage device so as to minimize the average rotational latency cost. This paper is an extension of that work. We employ the same model but a different latency delay function. Motivated by the NP-completeness of the general problem and the fact that an arbitrary assignment can have an expected latency cost almost twice that of an optimal assignment, we propose and analyze a fast heuristic whose performance compares favorably with that of an optimal algorithm.