I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes), allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.

The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.

In the case that not all requests can be satified with the given
memory size I'd like to get a list of allocation that maximizes the
memory allocation, i.e. the sum of the products of used memory size
and time of usage should be maximal (as this would probably maximize performance).

AFAIK, this is the offline dynamic memory allocation problem. Since
the number of requests can be up to 1000 I cannot try all
combinations. Also, AFAIK, the problem is NP complete.

So my question is: Is there an algorithm that computes an optimal
allocation in short time, say a few seconds or a minute (probably not
since NP completeness), and otherwise, is there an algorithm that
computes a good approximation in that time frame?

If have thought about variants of First-Fit and Best-Fit but I don't
know in which order to process the requests. Since I know all
requests in advance, I could sort by size first and then by allocation
time or vice-versa. If sorting by size, is ascending or descending
order better? Or are there better approaches?

Steve

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)