Optimal Sequential Assignments with Random Arrival Times

A problem is considered where jobs arrive at random times and assume random values, or importance. These must be assigned to a fixed set of men whose qualities are different but known. As each job arrives, its value is observed and the decision-maker must decide which man, if any, to assign to this job. If a job arrives at time t and its value is observed to be x, then by assigning man i with quality p_i, a reward r(t)p_ix is received, where r(t) is a discount function. The object is to find an assignment policy which maximizes the expected reward from the available men. The problem is analyzed for different arrival distributions and for different discount functions, but in all cases, the optimal policies are shown to have fairly simple forms, independent of the actual qualities of the men, the p_i's. Other interpretations of the model, besides the men and jobs interpretation, are also given. The paper concludes with a similar model which does not, however, include time as an explicit parameter.