Stochastic scheduling in an in-forest

Consider a problem of scheduling activities of a research and development project, where precedence relations of the activities constituting the project are represented by edges of an in-forest. Each activity is characterized by two parameters: a cost for attempting that activity and a probability that attempting the activity will lead to successful completion. The problem is to find a policy for attempting activities that minimizes the expected cost incurred until termination (successful completion of the project or the first activity failure). The main result of the paper is the design of an efficient algorithm to determine an optimal sequence in which to attempt the activities; a result which is established for linear and exponential utility functions. It is also shown that, unlike the related problem with out-forest precedence relations, there need not exist an optimal policy that is based on an index-rule for determining priority of edges by evaluating their successors.