Near-optimal heuristics for an assignment problem in mass storage

Abstract

This paper deals with the assignment of items to an array based on access probabilities so that the expected access time is minimized. The only necessary condition for optimality known to date is that of pairwise majorization. This condition, however, is far from being sufficient. Procedures are developed (1) to enumerate all configurations that satisfy this condition and (2) to obtain tight lower bounds for the optimal solution. An algorithm based on stepwise minimization is proposed and is demonstrated to give near-optimal performance. Numerical results are presented to show that the heuristics yield an actual cost within 0.8 % of the optimal regardless of the underlying distribution and the array size. Furthermore, this algorithm only depends on the ranking of access frequencies and not on the exact values. © 1975 Plenum Publishing Corporation.