A stochastic assignment problem |
| |
Authors: | David T. Wu Sheldon M. Ross |
| |
Affiliation: | Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, California |
| |
Abstract: | There are n boxes with box i having a quota value Balls arrive sequentially, with each ball having a binary vector attached to it, with the interpretation being that if Xi = 1 then that ball is eligible to be put in box i. A ball's vector is revealed when it arrives and the ball can be put in any alive box for which it is eligible, where a box is said to be alive if it has not yet met its quota. Assuming that the components of a vector are independent, we are interested in the policy that minimizes, either stochastically or in expectation, the number of balls that need arrive until all boxes have met their quotas. © 2014 Wiley Periodicals, Inc. 62:23–31, 2015 |
| |
Keywords: | sequential assignment problem dynamic programming stochastic optimization stochastic process modeling probability online optimization |
|
|