Extensions of the sequential stochastic assignment problem

The sequential stochastic assignment problem (SSAP) allocates N workers to N IID sequentially arriving tasks so as to maximize the expected total reward. This paper studies two extensions of the SSAP. The first one assumes that the values of any two consecutive tasks are dependent on each other while the exact number of tasks to arrive is unknown until after the final arrival. The second extension generalizes the first one by assuming that the number of workers is also random. Optimal assignment policies for both problems are derived and proven to have the same threshold structure as the optimal policy of the SSAP.