Optimal and asymptotically optimal decision rules for sequential screening and resource allocation
Luc Pronzato · IEEE Transactions on Automatic Control · 2001
We consider the problem of maximizing the expected sum of n variables X/sub k/ chosen sequentially in an i.i.d. sequence of length N. It is equivalent to the following resource allocation problem: n machines have to be allocated to N jobs of value X/sub k/ (k=1,...,N) arriving sequentially, the ith machine has a (known) probability p/sub i/ to perform the job successfully and the total expected reward must be maximized. The optimal solution of this stochastic dynamic-programming problem is derived when the distribution of the X/sub k/s is known: the optimal threshold for accepting X/sub k/, or allocating the ith machine to job k, is given by a backward recurrence equation. This optimal solution is compared to the simpler (but suboptimal) open-loop feedback-optimal solution for which the threshold is constant, and their asymptotic behaviors are investigated. The asymptotic behavior of the optimal threshold is used to derive a simple open-loop solution, which is proved to be asymptotically optimal (N/spl rarr//spl infin/ with n fixed) for a large class of distributions for X/sub k/.