Optimal project selection: Stochastic knapsack with finite time horizon
- PDF / 250,054 Bytes
- 6 Pages / 595 x 842 pts (A4) Page_size
- 45 Downloads / 198 Views
#1999 Operational Research Society Ltd. All rights reserved. 0160-5682/99 $12.00 http://www.stockton-press.co.uk/jor
Optimal project selection: Stochastic knapsack with ®nite time horizon LL Lu1, SY Chiu2 and LA Cox Jr3 1
AT&T Laboratories, Middletown,
2
GTE Laboratories, Waltham and 3Cox Associates, Denver
A time-constrained capital-budgeting problem arises when projects, which can contribute to achieving a desired target state before a speci®ed deadline, arrive sequentially. We model such problems by treating projects as randomly arriving requests, each with a funding cost, a proposed bene®t, 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 bene®t 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: capital budgeting; project selection; on-line selection rule; stochastic dynamic programming
Introduction Often, even the largest companies face strategic threats or opportunities that can only be well managed by achieving some target state before time runs out. If the available time is too short to permit rational analysis, crisis management may be required. If the time frame is somewhat longer, a sustained effort to achieve the target may be required, with priorities being carefully set and frequently revised to make the greatest possible use of new information as it becomes available. This paper addresses resource allocation in this second context Ð careful deliberation with time pressure to reach a goal. Well-known pragmatic dif®culties that make project selection challenging include the following: Success uncertainty (unknown rewards): Whether (or how well) a project will succeed, both technically and in the market, may be uncertain. Changing opportunities (randomly arriving opportunities): The opportunity of funding a project may be uncertain. New projects are continually being proposed throughout the year, stimulated by changes in technology and market opportunities that might help the company to achieve its goal. Need for quick funding decisions (on-line decision): The organisations proposing projects lack a comprehensive view of all project activities company-wide. It is essential for top management to give the organization prompt
Correspondence: Dr LL Lu, AT&T Laboratories, 200 Laurel Avenue, Room D5-3D19, Middletown, New Jersey 07748, USA. E-mail: [email protected]
accept=revise=reject decisions, since such feedback helps to coordinate their activities. Combinatorial complexity: The costs and bene®ts from different projects may interact. The fourth of these dif®culties can be par
Data Loading...
