Article ID: | iaor1989893 |
Country: | United States |
Volume: | 37 |
Issue: | 1 |
Start Page Number: | 99 |
End Page Number: | 110 |
Publication Date: | Feb 1990 |
Journal: | Naval Research Logistics |
Authors: | Henig Mordechai I., Simchi-Levi David |
Keywords: | programming: dynamic |
A project is made of several tasks which can be executed in parallel. Each task is associated with performance cost and failure probability. If all tasks succeed a reward is obtained. We suggest a dynamic programming algorithm to solve the problem of scheduling the tasks in order to maximize the expected discounted profit. We show that the general problem is NP-complete, but that there are cases where the dynamic programming algorithm is polynomially bounded.