About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.