Limiting behavior of the stochastic sequential assignment problem
Abstract
The stochastic sequential assignment problem (SSAP) considers how to allocate available distinct workers to sequentially arriving tasks with stochastic parameters such that the expected total reward obtained from the sequential assignments is maximized. Implementing the optimal assignment policy for the SSAP involves calculating a new set of breakpoints upon the arrival of each task (i.e., for every time period), which is impractical for large‐scale problems. This article studies two problems that are concerned with obtaining stationary policies, which achieve the optimal expected reward per task as the number of tasks approaches infinity. The first problem considers independent and identically distributed (IID) tasks with a known distribution function, whereas in the second problem tasks are derived from r different unobservable distributions governed by an ergodic Markov chain. The convergence rate of the expected reward per task to the optimal value is also obtained for both problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 12, 2013
- Source ID
- 10.1002/nav.21536
Entities
People
- Golshid Baharian
- Sheldon H. Jacobson
Organizations
- Air Force Office of Scientific Research
- National Science Foundation