Limiting behavior of the stochastic sequential assignment problem

Golshid Baharian, Sheldon H. Jacobson

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)321-330
Number of pages10
JournalNaval Research Logistics
Volume60
Issue number4
DOIs
StatePublished - Jun 2013

Keywords

  • hidden Markov chain
  • sequential assignment
  • stationary policy

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Limiting behavior of the stochastic sequential assignment problem'. Together they form a unique fingerprint.

  • Cite this