Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T20:30:34.606Z Has data issue: false hasContentIssue false
  • English
  • Français

A Sequential Assignment Match Process with General Renewal Arrival Times

Published online by Cambridge University Press:  27 July 2009

Israel David
Israel David
Affiliation:
Department of Industrial Engineering and Management, Ben-Gurion University of the Negev, Beer Sheva 84105, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

This work studies sequential assignment match processes, in which random offers arrive sequentially according to a renewal process, and when an offer arrives it must be assigned to one of given waiting candidates or rejected. Each candidate as well as each offer is characterized by an attribute. If the offer is assigned to a candidate that it matches, a reward R is received; if it is assigned to a candidate that it does not match, a reward r ≤ R is received; and if it is rejected, there is no reward. There is an arbitrary discount function, which corresponds to the process terminating after a random lifetime. Using continuoustime dynamic programming, we show that if this lifetime is decreasing in failure rate and candidates have distinct attributes, then the policy that maximizes total expected discounted reward is of a very simple form that is easily determined from the optimal single-candidate policy. If the lifetime is increasing in failure rate, the optimal policy can be recursively determined: a solution algorithm is presented that involves scalar rather than functional equations. The model originated in the study of optimal donor-recipient assignment in live-organ transplants. Some other applications are mentioned as well.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 9 , Issue 3 , July 1995 , pp. 475 - 492
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Abramowitz, M. & Stegun, I. (1972). Handbook of mathematical functions. Washington, DC: U.S. Department of Commerce, National Bureau of Standards.Google Scholar
2.Albright, S.C. (1974). Optimal sequential assignments with random arrival times. Management Science 21: 60–67.CrossRefGoogle Scholar
3.Assaf, D. & Levikson, B. (1991). Optimal advertising policy for selling a single asset. Probability in the Engineering and Informational Sciences 5: 89–100.CrossRefGoogle Scholar
4.Barlow, R.E. & Proschan, F. (1975). Statistical theory of reliability and life testing. New York: Holt, Rinehart and Winston.Google Scholar
5.David, I. & Yechiali, U. (1990). Sequential assignment match processes with arrival of candidates and offers. Probability in the Engineering and Informational Sciences 4: 413–430.CrossRefGoogle Scholar
6.David, I. & Yechiali, U. (1995). One-attribute sequential assignment match processes in discrete time. Operations Research (to appear).CrossRefGoogle Scholar
7.Derman, C., Lieberman, G.J., & Ross, S.M. (1972). A sequential stochastic assignment problem. Management Science 18: 349–355.CrossRefGoogle Scholar
8.Elfving, G. (1967). A persistency problem connected with a point process. Journal of Applied Probability 4: 77–89.CrossRefGoogle Scholar
9.Hildebrand, F.B. (1965). Methods of applied mathematics, 2nd ed.Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
10.Jennings, J.B. (1973). Blood bank inventory control. Management Science 19: 637–645.CrossRefGoogle Scholar
11.Karlin, S. (1962). Stochastic models and optimal policy for selling an asset. In Arrow, K.J. & Scarf, H. (eds.), Studies in applied probability and management science. Stanford, CA: Stanford University Press, pp. 148–158.Google Scholar
12.Lippman, S.A. & McCalt, J.J. (1976). The economics of job search: A survey. Economic Inquiry 14: 155–189.CrossRefGoogle Scholar
13.Righter, R. (1987). The stochastic sequential assignment problem with random deadlines. Probability in the Engineering and Informational Sciences 1: 189–202.CrossRefGoogle Scholar
14.Righter, R. (1990). Stochastically maximizing the number of successes in a sequential assignment problem. Journal of Applied Probability 27: 351–364.CrossRefGoogle Scholar
15.Ross, S.M. (1983). Introduction to stochastic dynamic programming. New York: Academic Press.Google Scholar
16.Weatherford, L.R. & Bodily, S.E. (1993). A taxonomy and research overview of perishable asset revenue management, overbooking and pricing. Operations Research 40: 831–844.CrossRefGoogle Scholar