Optimal project selection: Stochastic knapsack with finite time horizon |
| |
Authors: | L L Lu S Y Chiu Jr" target="_blank">L A CoxJr |
| |
Institution: | 1.AT&T Laboratories,Middletown;2.GTE Laboratories,Waltham;3.Cox Associates,Denver |
| |
Abstract: | A time-constrained capital-budgeting problem arises when projects, which can contribute to achieving a desired target state before a specified deadline, arrive sequentially. We model such problems by treating projects as randomly arriving requests, each with a funding cost, a proposed benefit, and a known probability of success. The problem is to allocate a non-renewable initial budget to projects over time so as to maximise the expected benefit obtained by a certain time, T, called the deadline, where T can be either a constant or a random variable. Each project must be accepted or rejected as soon as it arrives. We developed a stochastic dynamic programming formulation and solution of this problem, showing that the optimal strategy is to dynamically determine ‘acceptance intervals’ such that a project of type i is accepted when, and only when, it arrives during an acceptance interval for projects of type i. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|