Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-27T08:01:22.740Z Has data issue: false hasContentIssue false
  • English
  • Français

The Stochastic Sequential Assignment Problem With Random Deadlines

Published online by Cambridge University Press:  27 July 2009

Rhonda Righter
Rhonda Righter
Affiliation:
Department of Electrical Engineering and Computer Science University of California Berkeley, California 94720
Get access Rights & Permissions [Opens in a new window]

Extract

Resources are to be allocated sequentially to activities to maximize the total expected return, where the return from an allocation is the product of the value of the resource and the value of the activity. The set of activities and their values are given ahead of time, but the resources arrive according to a Poisson process and their values are independent random variables that are observed upon arrival. It is assumed that either there is a single random deadline for all activities, which is the same as discounting the returns, or the activities have independent random deadlines. The model has applications machine scheduling, packet switching, and kidney allocation for transplant. It is known that the optimal policy in the discounted case has a very simple form that does not depend on the activity values. We show that this is also true when the deadlines are independent and in this case the solution can expressed in terms of solutions to single activity models. These results also hold when there are batch arrivals of resources. The effects of pooling separate identical systems with a single activity into a combined system is investigated for both models. When activities have independent deadlines it is optimal to reject a resource in the combined system if and only if it is optimal to reject it in the single activity system. However, when returns are discounted, it is sometimes optimal to accept a resource in the combined system that would be rejected in the single activity system.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 1 , Issue 2 , April 1987 , pp. 189 - 202
Copyright
Copyright © Cambridge University Press 1987

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

Agrawala, A. K., Coffman, E. G. Jr, Garey, M. R., and Tripathi, S. K. (1984). A stochastic optimal algorithm minimizing exponential flow times on uniform processors. IEEE Trans. on Computers, C-33(4): 351–356.CrossRefGoogle Scholar
Albright, C. and Derman, C. (1972). Asymptotic optimal policies for the stochastic sequential assignment problem. Mgmt. Sci. 19(1): 46–51.CrossRefGoogle Scholar
Albright, C. (1977). A Bayesian approach to a generalized house selling problem. Mgmt. Sci. 24(4): 432–440.CrossRefGoogle Scholar
Albright, S. (1976). A Markov chain version of the secretary problem. Naval Res. Log. Quarterly 23(1): 151–159.CrossRefGoogle Scholar
Albright, S. C. (1974). Optimal sequential assignments with random arrival times. Mgmt. Sci. 21(1): 60–67.CrossRefGoogle Scholar
David, I. and Yechiali, U. (1985). A time-dependent stopping problem with application to live organ transplants. Opns. Res. 33(3): 491–504.CrossRefGoogle ScholarPubMed
Derman, C., Lieberman, C., and Ross, S. (1975). A stochastic sequential allocation model. Opns. Res. 23: 1120–1130.CrossRefGoogle Scholar
Elfving, G. (1967). A persistency problem connected with a point process. J. Appl. Prob. 4: 77–89.CrossRefGoogle Scholar
Hardy, G. H., Littlewood, J. E., and Polya, G. (1934). Inequalities, Cambridge University Press.Google Scholar
Marx, J. (1980). Improving the success of kidney transplants. Science 209(8): 673–674.CrossRefGoogle ScholarPubMed
Mucci, A. G. (1978). Existence and explicit determination of optimal stopping times. Stoch. Proc. and Appl. 8: 33–38.CrossRefGoogle Scholar
Nakai, T. (1985). Studies on sequential stochastic assignment problems. Ph.D. Thesis, Faculty of Engineering Science, Osaka University, Japan.Google Scholar
Nakai, T. (1986). A sequential stochastic assignment problem in a partially observable Markov chain. Math, of O. R. 11(2): 230–240.Google Scholar
Righter, R. L. (1986). Analysis of sequential stochastic assignment problems. Ph.D. Thesis, University of California, Berkeley.Google Scholar
Saario, V. (1985). Limiting properties of the discounted house-selling problem. Eur. J. Opnl. Res. 20: 206–210.CrossRefGoogle Scholar
Sakaguchi, M. (1976). Optimal stopping problems for randomly arriving offers. Math. Japan. 21: 201–217.Google Scholar
Sakaguchi, M. (1984). A sequential stochastic assignment problem with an unknown number of jobs. Math. Japon. 29(2): 141–152.Google Scholar
Sakaguchi, M. (1984). A sequential stochastic assignment problem associated with a nonhomogeneous Markov process. Math. Japon. 29(1): 13–22.Google Scholar
Sakaguchi, M. (1986). Best choice problems for randomly arriving offers during a random lifetime. Math. Japon. 31(1): 107–117.Google Scholar
Terasaki, P., Opelz, G., and Mickey, M. (1981). Clinical kidney transplants. Cellular Immunology 62(2): 277–286.CrossRefGoogle ScholarPubMed