Optimal Sizing of Records Used to Store Messages of Various Lengths
研究在存储设备中，使用固定数量的记录长度来存储不同长度消息时，如何选择最优记录长度以最小化期望总存储空间，并提出了一个适用于一般消息长度分布的动态规划算法。
In many computer applications messages of various lengths need to be stored in some storage device. In this paper we examine the problem in which a fixed number of record lengths can be used to store messages. Whenever a message arrives, it is stored in the smallest possible record which is at least as large as the message. If a message cannot be stored in any single record, it is divided into segments and stored in several records of the same length. Each record is accompanied by a header which contains overhead information. Furthermore, in some applications records of the same length are stored in larger units, called blocks. If so, some space may be wasted at the end of a block. The objective is to find the optimal record lengths so that the expected total space used to store a message is minimized A dynamic programming algorithm that finds the optimal record lengths is developed for a general message length distribution. Numerical examples are discussed.