244
Views
8
CrossRef citations to date
0
Altmetric
Original Articles

The sequential stochastic assignment problem with random success rates

, , &
Pages 1169-1180 | Received 01 Dec 2011, Accepted 01 Dec 2013, Published online: 28 Jul 2014
 

Abstract

Given a finite number of workers with constant success rates, the Sequential Stochastic Assignment problem (SSAP) assigns the workers to sequentially arriving tasks with independent and identically distributed reward values, so as to maximize the total expected reward. This article studies the SSAP, with some (or all) workers having random success rates that are assumed to be independent but not necessarily identically distributed. Several assignment policies are proposed to address different levels of uncertainty in the success rates. Specifically, if the probability density functions of the random success rates are known, an optimal mixed policy is provided. If only the expected values of these rates are known, an optimal expectation policy is derived.

Appendix

Notation

  • n: finite number of workers to be assigned to tasks

  • m: number of workers with random success rates

  • {Xi, i = 1, 2, …, n}: set of task values

  • {pj, j = 1, 2, …, nm}: set of fixed success rates (shorthand {pj})

  • {Qk, k = 1, 2, …, m}: set of random success rates (shorthand {Qk})

  • : set of pdfs of random success rates (shorthand )

  • {Dk, k = 1, 2, …, m}: set of domains of pdfs

  • {Aj, j = 1, 2, …, nm + 1}: set of ranking intervals

  • {A*j, j = 1, 2, …, nm + 1}: set of ranking intervals

  • j, j = 1, 2, …, nm + 1}: set of ranking probabilities

Additional information

Notes on contributors

Arash Khatibi

Arash Khatibi is a Ph.D. candidate in Industrial and Systems Engineering at the University of Illinois at Urbana–Champaign. Prior to joining the University of Illinois, he received his M.Sc. in Electrical Engineering from Delft University of Technology, Delft, The Netherlands, in 2011 and his B.Sc. in Electrical Engineering from Sharif University of Technology, Tehran, Iran, in 2009. His research interests include stochastic optimization and applied probability.

Golshid Baharian

Golshid Baharian is a Ph.D. candidate in Industrial Engineering at the University of Illinois at Urbana–Champaign. She has a B.Sc. in Industrial Engineering from University of Tehran, Iran. Her research interests include dynamic stochastic optimization, applied probability, and queueing theory.

Estelle R. Kone

Estelle Kone has a Ph.D. in Industrial & Systems Engineering from the University of Illinois at Urbana-Champaign. She has a B.Sc. in Industrial Engineering from Université de Technologie de Troyes and an M.Sc. in Industrial Engineering from State University of New York at Buffalo. Her research interests include network security, data fusion, and stochastic processes.

Sheldon H. Jacobson

Sheldon H. Jacobson is a Professor in the Department of Computer Science at the University of Illinois at Urbana–Champaign. He has a B.Sc. and M.Sc. in Mathematics from McGill University and a Ph.D. in Operations Research from Cornell University. His research interests span theory and practice, covering decision making under uncertainty and discrete optimization modeling and analysis, with applications in aviation security, health care, and sports. From 2012–2014, he was on leave from the University of Illinois, serving as the Program Director for Operations Research in the Division of Civil, Mechanical and Manufacturing Innovation at the National Science Foundation.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.