Date: 03/06/07 (Algorithms)    Keywords: no keywords

I’ve been trying to solve a problem, and it seems like the sort of problem someone has probably solved already. I would be grateful if anyone can point me in the right direction. This is a practical problem, but I’ll state it here in abstract form.

There are N “request queues.” Requests arrive at random. The rates of arrival are not known but may be assumed to vary slowly. At any particular time, the number of requests currently in each queue can be determined.

There are M “server pools.” Each pool has a maximum number of requests it can service simultaneously. The maximums differ from pool to pool and change over time. At any given time the maximum for each pool is known, and it may be assumed that these maximums change slowly compared to the rate at which requests are serviced.

The length of time required to service a request is random. It may be assumed to be independent of which request queue and server pool are involved.

There is an N by M matrix of non-negative numbers which represent the “worth” of servicing requests from each of the queues in each of the server pools. The value of servicing a request is equal to the worth of servicing the request in the server pool to which it is assigned depreciated according to the length of time the request has waited before being serviced. The depreciation is geometric, with a half-life which is the same for all requests in a queue but may be different for different queues. The worth values and half-lives are specified beforehand and do not change.

The problem is to determine an algorithm for assigning requests to server pools that will tend to maximize the total service value. When a server pool opening arises, there may be several non-empty queues for which the server pool has non-zero worth; it is not obvious how to tell which request is best to satisfy and which requests should be left for a later opening in a different server pool. The solution only needs to be “good,” not optimal; but it must avoid notably inefficient behavior in degenerate cases (such as a queue receiving no requests for an extended period of time, or a server pool having a maximum capacity of zero).

Source: http://community.livejournal.com/algorithms/90089.html