Stochastic Sequential Assignment Problems

随机顺序分配问题

• 批准号: 1233337
• 负责人: Sheldon Ross
• 金额: $ 24.78万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-09-15 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1233337&HistoricalAwards=false
• 关键词: Stochastic; Sequential; Assignment; Problems

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.

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