A Resource Allocation Problem in a Random Environment

We consider a resource allocation problem in which various parameters of the model change according to independent random environment Markov processes. There are a finite number of activities that each require a resource, and resources arrive according to a Poisson process. Both activities and resources have values associated with them and the return from allocating a resource to an activity is the product of the activity value and the resource value. Activity values are known ahead of time but the values of resources are independent random variables from a common distribution and are known only after the arrival of the resource. We wish to assign arriving resources to available activities so as to maximize our total expected return. It is assumed that either there is a single random deadline for all activities, which is the same as discounting the returns, or the activities have independent random deadlines. The model has applications to processor scheduling, selling of assets, and kidney allocation for transplant. We consider the effects on the structure of the optimal policy of allowing parameters to be determined by independent Markov processes. In particular, we permit the resource arrival rate, the activity values, the deadline rates, and the variability of the resource distribution to change. We give conditions under which the total optimal expected return is monotone in the states of the Markov processes. We also show that the total optimal return is increasing and convex in the activity values, decreasing and convex in the deadline rates, and increasing if the variability of the distribution of resource values is increasing.