Optimal project selection: Stochastic knapsack with finite time horizon

A time-constrained capital-budgeting problem arises when projects, which ca n contribute to achieving a desired target state before a specified deadlin e, arrive sequentially. We model such problems by treating projects as rand omly arriving requests, each with a funding cost, a proposed benefit, and a known probability of success. The problem is to allocate a non-renewable i nitial 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 a s soon as it arrives. We developed a stochastic dynamic programming formula tion 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 f or projects of type i.