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.