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.