出版社：Institute for Operations Research and the Management Sciences (INFORMS), Applied Probability Society
摘要：The sequential stochastic assignment problem (SSAP) assigns sequentially arriving tasks with stochastic parameters (coming from a known distribution) to workers with fixed success rates so as to maximize the total expected reward. This paper studies the generalized SSAP (GSSAP), an extension of SSAP with no prior information on task values. GSSAP is described as a generalization of the secretary problem, in which the set of selected elements in the secretary problem are assigned to distinct positions in GSSAP. The weighted secretary problem is used to design two deterministic and one randomized algorithm for GSSAP. The proposed algorithms have a threshold structure: the first few stages of the problem are used as a training phase to compute thresholds. These thresholds are then used to assign tasks to workers after the training phase. These algorithms provide intuitive models to assign tasks arriving in the training phase to workers. Although the expected reward achieved by the deterministic algorithms has a better lower bound, the randomized algorithm provides fairness by assigning each task to any of the workers with equal probability.
