The sequential stochastic assignment problem with random success rates

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.

Keywords:

• Sequential decision-making
• stochastic processes
• assignment policy

Appendix

Notation

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

• m: number of workers with random success rates

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

• {p_j, j = 1, 2, …, n − m}: set of fixed success rates (shorthand {p_j})

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

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

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

• {A_j, j = 1, 2, …, n − m + 1}: set of ranking intervals

• {A*_j, j = 1, 2, …, n − m + 1}: set of ranking intervals

• {π_j, j = 1, 2, …, n − m + 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.