Doubly Stochastic Sequential Assignment Problem

Arash Khatibi, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


This article introduces the Doubly Stochastic Sequential Assignment Problem (DSSAP), an extension of the Sequential Stochastic Assignment Problem (SSAP), where sequentially arriving tasks are assigned to workers with random success rates. A given number of tasks arrive sequentially, each with a random value coming from a known distribution. On a task arrival, it must be assigned to one of the available workers, each with a random success rate coming from a known distribution. Optimal assignment policies are proposed for DSSAP under various assumptions on the random success rates. The optimal assignment algorithm for the general case of DSSAP, where workers have distinct success rate distribution, has an exponential running time. An approximation algorithm that achieves a fraction of the maximum total expected reward in a polynomial time is proposed. The results are illustrated by several numerical experiments.

Original languageEnglish (US)
Pages (from-to)124-137
Number of pages14
JournalNaval Research Logistics
Issue number2
StatePublished - Mar 1 2016


  • online matching
  • optimal policy
  • sequential assignment

ASJC Scopus subject areas

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


Dive into the research topics of 'Doubly Stochastic Sequential Assignment Problem'. Together they form a unique fingerprint.

Cite this