The Sequential Stochastic Assignment Problem (SSAP) deals with assigning sequentially arriving tasks with stochastic parameters to workers with fixed success rates. The reward of each assignment is the product of the worker's success rate and the task value assigned to the worker. The objective is to maximize the total expected reward.
This dissertation studies several variations of SSAP by relaxing the main assumptions. The first part assumes that the workers' success rates are random values coming from a known distribution. The second part relaxes the assumption that the value of sequentially arriving elements are independently drawn from a known distribution and uses the well-known Secretary Problem to derive constant-competitive algorithms for SSAP with tasks having a random arrival order.
The third part uses the linear programming technique to derive bounds on the performance of optimal policy for several variations of SSAP. In addition to deriving bounds on performance of optimal policies, the linear programming technique can be used to formulate extensions of the problem as linear programs by simple changes in the objective function and constraints of the basic formulation.
The last part relaxes the assumption that at most one task must be assigned to each worker in SSAP and proposes assignment policies for the problem with each worker performing multiple tasks. This problem is studied under various models for the task duration and the task values.