Stochastic Sequential Assignment Problems

这个项目将利用动态规划来开发解决问题的方法，在这些问题中，顺序到达的工作要么被拒绝，要么被分配给当前未分配的工人。在一般模型中，一项任务的最终报酬将由一个任意函数决定，该函数取决于工作和工人的特点。特殊情况下，如奖励是二元的，当一份工作分配给一个合格的工人时，奖励为1，将被考虑。将考虑当每个工人都被分配时问题就结束的模型，以及工人在随机时间后返回重新分配的模型。在返回工人的情况下，假设每个工人完成一项工作所需时间的概率分布，并在假设这些分布已知和未知的情况下分析问题。结果将在可能的情况下确定最佳策略，否则将确定好的启发式策略。模拟技术，使用创新的方差减少思想，将被用来分析政策的表现。该项目将对如何解决和近似具有多维状态空间的动态规划问题产生重要见解。如果成功，该研究将影响许多重要的应用领域。例如，在医疗保健领域，工人可能是等待器官移植的病人，而工作可能是到达的器官。该模型也等同于假设一个组织有职位需要填补，每个顺序到达的求职者都有一个向量，向组织提供分配该候选人到不同职位的值。

This project will utilize dynamic programming to develop approaches for solving problems wheresequentially arriving jobs can either be rejected or assigned to a currently unassigned worker. Inthe general model the resulting reward from an assignment will be determined by an arbitraryfunction that depends on both the characteristics of the job and the worker. Particular cases,such as where the reward is binary, yielding a reward of 1 when a job is assigned to a qualifiedworker, will be considered. Models where the problem ends when each worker has been assignedand ones where workers return for reassignment after a random time will be considered. In thecase of returning workers, probability distributions for the time it takes each worker to completea job are assumed, and problems will be analyzed both when these distributions are assumedknown and when they are unknown. Results will determine optimal policies when possible, goodheuristic policies otherwise. Simulation techniques, using innovative variance reduction ideas,will be used to analyze the performance of policies. The project will will yield important insightsas to how to solve and approximate dynamic programming problems having multidimensionalstate spaces.If successful, the research will impact many important application areas. For examples, in health care, workers might be patients waiting for organ transplants, and jobs could be arriving organs. The model is also equivalent to one thatassumes that an organization has jobs to fill, with each sequentially arriving job seeker havinga vector giving the values to the organization of assigning that candidate to the different jobs.