Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T23:24:50.383Z Has data issue: false hasContentIssue false
  • English
  • Français

Sequential stochastic assignment problem with time-dependent random success rates

Part of: Stochastic processes Discrete mathematics in relation to computer science

Published online by Cambridge University Press:  09 December 2016

Golshid Baharian ,
Arash Khatibi  and
Sheldon H. Jacobson
Golshid Baharian*
Affiliation:
University of Montreal
Arash Khatibi*
Affiliation:
University of Illinois at Urbana-Champaign
Sheldon H. Jacobson*
Affiliation:
University of Illinois at Urbana-Champaign
*
* Postal address: CHU Sainte Justine, University of Montreal, 3175 Chemin de la Cote Sainte-Catherine, Montreal, Québec, H3T 1C5, Canada. Email address: golshidb@gmail.com
** Postal address: Department of Computer Science, University of Illinois at Urbana-Champaign, 201 North Goodwin Avenue, Urbana, IL 61801, USA.
** Postal address: Department of Computer Science, University of Illinois at Urbana-Champaign, 201 North Goodwin Avenue, Urbana, IL 61801, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The sequential stochastic assignment problem (SSAP) allocates distinct workers with deterministic values to sequentially arriving tasks with stochastic parameters to maximize the expected total reward. In this paper we study an extension of the SSAP, in which the worker values are considered to be random variables, taking on new values upon each task arrival. Several SSAP models with different assumptions on the distribution of the worker values and closed-form expressions for optimal assignment policies are presented.

Keywords

Sequential stochastic assignmentoptimal policy

MSC classification

Primary: 60G20: Generalized stochastic processes
Secondary: 68R01: General

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 4 , December 2016 , pp. 1052 - 1063
Copyright
Copyright © Applied Probability Trust 2016 

References

[1] Albright, S. C. (1974).A Markov-decision-chain approach to a stochastic assignment problem.Operat. Res. 22,61–64.Google Scholar
[2] Albright, S. C. (1974).Optimal sequential assignments with random arrival time.Manag. Sci. 21,60–67.Google Scholar
[3] Albright, S. C. (1977).A Bayesian approach to a generalized house selling problem.Manag. Sci. 24,432–440.CrossRefGoogle Scholar
[4] Albright, S. C. and Derman, C. (1972).Asymptotic optimal policies for the stochastic sequential assignment problem.Manag. Sci. 19,46–51.CrossRefGoogle Scholar
[5] Baharian, G. and Jacobson, S. H. (2013).Limiting behavior of the stochastic sequential assignment problem.Naval Res. Logistics 60,321–330.CrossRefGoogle Scholar
[6] Derman, C.,Lieberman, G. J. and Ross, S. M. (1972).A sequential stochastic assignment problem.Manag. Sci. 18,349–355.CrossRefGoogle Scholar
[7] Khatibi, A.,Baharian, G.,Behzad, B. and Jacobson, S. H. (2015).Extensions of the sequential stochastic assignment problem.Math. Meth. Operat. Res. 82,317–340.CrossRefGoogle Scholar
[8] Khatibi, A.,Baharian, G.,Kone, E. R. and Jacobson, S. H. (2014).The sequential stochastic assignment problem with random success rates.IIE Trans. 46,1169–1180.Google Scholar
[9] Nikolaev, A. G. and Jacobson, S. H. (2010).Stochastic sequential decision-making with a random number of jobs.Operat. Res. 58,1023–1027.CrossRefGoogle Scholar
[10] Nikolaev, A. G.,Jacobson, S. H. and McLay, L. A. (2007).A sequential stochastic security system design problem for aviation security.Transportation Sci. 41,182–194.Google Scholar
[11] Righter, R. (1987).The stochastic sequential assignment problem with random deadlines.Prob. Eng. Inf. Sci. 1,189–202.CrossRefGoogle Scholar
[12] Su, X. and Zenios, S. A. (2005).Patient choice in kidney allocation: a sequential stochastic assignment model.Operat. Res. 53,443–455.Google Scholar