×

Generalized sequential stochastic assignment problem. (English) Zbl 1442.90092

Summary: The sequential stochastic assignment problem (SSAP) assigns sequentially arriving tasks with stochastic parameters (coming from a known distribution) to workers with fixed success rates so as to maximize the total expected reward. This paper studies the generalized SSAP (GSSAP), an extension of SSAP with no prior information on task values. GSSAP is described as a generalization of the secretary problem, in which the set of selected elements in the secretary problem are assigned to distinct positions in GSSAP. The weighted secretary problem is used to design two deterministic and one randomized algorithm for GSSAP. The proposed algorithms have a threshold structure: the first few stages of the problem are used as a training phase to compute thresholds. These thresholds are then used to assign tasks to workers after the training phase. These algorithms provide intuitive models to assign tasks arriving in the training phase to workers. Although the expected reward achieved by the deterministic algorithms has a better lower bound, the randomized algorithm provides fairness by assigning each task to any of the workers with equal probability.

MSC:

90B36 Stochastic scheduling theory in operations research
60G40 Stopping times; optimal stopping problems; gambling theory
62L15 Optimal stopping in statistics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albright SC (1974) Optimal sequential assignment with random arrival time. Management Sci. 21(1):60-67.Link, Google Scholar · Zbl 0304.90054
[2] Albright SC, Derman C (1972) Asymptotic optimal policies for stochastic sequential assignment problem. Management Sci. 19(1):46-51.Link, Google Scholar · Zbl 0255.90022
[3] Babaioff M, Dinitz M, Gupta A, Immorlica N, Talwar K (2009) Secretary problems: Weights and discounts. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’09 (Society for Industrial and Applied Mathematics, Philadelphia), 1245-1254.Google Scholar · Zbl 1422.68336
[4] Buchbinder N, Jain K, Singh M (2013) Secretary problems via linear programming. Math. Oper. Res. 39(1):190-206.Google Scholar · Zbl 1305.90344
[5] Chow YS, Moriguti S, Robbins H, Samuels SM (1964) Optimal selection based on relative rank. Israel J. Math. 2(2):81-90.Google Scholar · Zbl 0149.14402
[6] Derman C, Lieberman GJ, Ross SM (1972) A sequential stochastic assignment problem. Management Sci. 18(7):349-355.Link, Google Scholar · Zbl 0238.90054
[7] Enns EG (1970) The optimum strategy for choosing the maximum of n independent random variables. Unternehmensforschung 14(1):89-96.Google Scholar · Zbl 0193.18102
[8] Freeman PR (1983) The secretary problem and its extensions: A review. Internat. Statist. Rev. 51(2):189-206.Google Scholar · Zbl 0516.62081
[9] Gershkov A, Moldovanum B (2010) Efficient sequential assignment with incomplete information. Games Econom. Behav. 68(1):144-154.Google Scholar · Zbl 1197.90277
[10] Gianini J, Samuels SM (1976) The infinite secretary problem. Ann. Probab. 4(3):418-432.Google Scholar · Zbl 0341.60033
[11] Glasser KS, Holzsager R (1983) The d choice secretary problem. Comm. Statist. 2(3):177-199.Google Scholar · Zbl 0589.62072
[12] Goel G, Nikzad A, Singla A (2014) Allocating tasks to workers with matching constraints: Truthful mechanisms for crowdsourcing markets. Proc. 23rd Internat. Conf. World Wide Web (ACM, New York), 279-280.Google Scholar
[13] Kennedy DP (1986) Optimal sequential assignment. Math. Oper. Res. 11(4):619-626.Link, Google Scholar · Zbl 0612.90073
[14] Khatibi A, Jacobson SH (2014) Doubly stochastic sequential assignment problem. Naval Res. Logist. 63(2):124-137.Google Scholar · Zbl 1411.90202
[15] Khatibi A, Baharian G, Kone ER, Jacobson SH (2014) The sequential stochastic assignment problem with random success rates. IIE Trans. 46(11):1169-1180.Google Scholar
[16] Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’05 (Society for Industrial and Applied Mathematics, Philadelphia), 630-631.Google Scholar · Zbl 1297.68268
[17] Lindley DV (1961) Dynamic programming and decision theory. Appl. Statist. 10(1):39.Google Scholar · Zbl 0114.34904
[18] Nikolaev AG, Jacobson SH (2010) Stochastic sequential decision-making with a random number of jobs. Oper. Res. 58(4P1):1023-1027.Abstract, Google Scholar · Zbl 1231.90270
[19] Oveis Gharan S, Vondrák J (2011) On variants of the matroid secretary problem. Demetrescu C, Halldórsson MM, eds. Algorithms - ESA 2011. Lecture Notes in Computer Science, vol. 6942 (Springer, Berlin, Heidelberg), 335-346.Google Scholar · Zbl 1307.68100
[20] Presman EL, Sonin IM (1972) The best choice problem for a random number of objects. Theory Probab. Appl. 17(4):657-668.Google Scholar · Zbl 0296.60031
[21] Rasmussen WT, Pliska SR (1975) Choosing the maximum from a sequence with a discount function. Appl. Math. Optim. 2(3):279-289.Google Scholar
[22] Sakaguchi M (1978) Dowry problems and ola policies. Rep. Statist. Appl. Res. JUSE 25:124-128.Google Scholar · Zbl 0416.62058
[23] Smith MH (1975) A secretary problem with uncertain employment. J. Appl. Probab. 12(03):620-624.Google Scholar · Zbl 0313.60033
[24] Su X, · Zbl 1165.90547
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.